CS50 problem set 2+3 作業回顧
Published in
3 min readOct 20, 2017
迴圈 (loop) 與遞回 (recursion)
pset2 作業 crack 本質上就是實作暴力解長度最多為 4 個字元的密碼,直覺上最快是直寫四個迴圈不斷產生a, b … z, aa, ab … 的字串做完 hash 後用 strcmp 比對 crypt 出的 hash 值,peusdo code:
for (int i = 'A' ; i <= 'z' ; i++ )
{
if (isalpha(i)) // 不懂資料結構前的寫法,畢竟中間不是英文的字不多
比對 crypt(i, salt="50") 出來的值是否跟目標相同
for (int j= 'A' ; i <= 'z' ; i++ )
{
... 開始不動大腦重覆刻迴圈 ...
}
}
雖然直覺但應該有更簡潔的寫法,於是在 python 上實作一版遞迴
def alphabet_generator(plain_text, input_hash):
先做一個可能字元的 list
if 字串長度到最大值 (4個字元) 就回傳作完 Null (Base Case)
elif 字串長度為零,base case
把 list 每一個字元出來作 crypt 跟比較
else 開始進遞回
從 list 裡再撈一個字元跟進來的 plain_text 加在一起做 crypt 比較
alphabet_generator(plain_text+j) 進遞迴繼續找 (Recursive Case)
目前對寫出一個有限遞迴的心得大概兩點:
- Base case 要確保遞迴可以被結束
- 進遞迴的參數要想清楚,可以產生預想的組合
pset3 其中一題是實作二分搜尋,在還不熟悉遞回寫法時,可能會寫出以下無效的方式
Bool Binary_search(int value, int values[], int start, int end);
Binary_search(…) {
…
Bool Found = Binary_search(int value, int values[], int start, int end); // recursion case
…
Return True; // found
…
Return False; // not found
}
遞迴函式沒有把回傳值放進去往下遞迴,在途中搜尋到也不會回值搜㝷成功,修改成下面的方式將回傳值代入即可:
Bool Binary_search(int value, int values[], int start, int end, bool found);
這樣一但搜尋成功就會一路將 True值傳上去。
下次寫卡很慘的 pset4 ,誤解作業要求卡五天最後發現其實不用作到太複雜
Reference
Recursive function: https://www.cs.umd.edu/class/fall2002/cmsc214/Tutorial/recursion2.html