※ 引述《hetea (hetea)》之銘言： : 資料結構： : 主力科目，答案都是一翻兩瞪眼，對就是對，錯就是錯， : 在筆者感覺比(系統分析與資訊管理)更明確拿的到分 : 在上一篇中，這一科我列了兩本書，其中當讀完第一本後， : 第二本會讓你功力再精進甚多，(筆者在關務93,高考90) : 如同程式語言，筆者是每一題都做。 : Graphic跟Tree,Sort/Search 都是必看 : 至於recursive程式(因之前為programmer，這部份並沒有困擾)， : 今年考試至少都會出一題。有機會還是要把握一下。 : 要試著從起始條件與終止條件思考。 : 在考試當場寫的程式不一定要最漂亮/優美/效率最好(因為沒時間) : 力求寫出題目要求即可。 有網友問到之前關務的一題遞迴程式怎麼想或如何寫才能得分 題目 試以任一電腦語言（或虛擬碼）以遞迴程式來 計算sin(x)的值。（15 分） 計算sin(x)的公式如下： sin(x)=x-x^3/3! + x^5/5! - x^7/7! + x^9/9! -.... （考慮求值到小數以下第六位） 筆者解題思考的步驟 基本上 至少要能找出規律性 寫出程式雛型(不一定要對)，但是要讓改卷老師知道考生觀念到底會不會 當然有時也會困在找不出規律性，卡很久或造成此題寫不出來 遞迴程式一定需要重覆執行相同的動作 1. 首先找出規則性 2. 這是一個序列,找出其規則 第一項 x 第二項 (-x^3)/(3*2*1) 第三項 x^5 /(5*4*3*2*1) 第四項 ... 可以看出分子 x -> (-x^3) -> x^5 規則為等比級數 -x^2 分母 1 -> (3*2*1) -> (5*4*3*2*1) 為N階乘.但是每次以增加2的等差級數 找出規律性，就能往程式方面著手 3. 接下來就是應用在遞迴程式 i. 回傳值(因為題目有限定在小數點下六位) => 選擇float或是double的精確度都可以適用 ii. 程式名 sin_cal(自己定) iii.參數 (這部份就要思考一下) 要從剛剛的規則分析，找出多少資訊要往下傳 a. x (型態可以為float或double, 當然若寫成int 可能會被扣分) b. 等比跟等差級數的項次(int) (一開始可能只想到這樣，那就先這樣寫) float sin_cal(float x, int exp) iv. 找出終止條件 求值到小數點以下六位 ?? < 0.000001 觀察一下，??就是新增的項次且不用考慮+/-號 新增的項次 float sum=1.0; for(i=1;i<=exp;i++) { sum = sum * x / i; } if(sum<0.000001) return 0;//因為小於0.000001就不用再算了也不加入此項 v. 利用剛剛的數列找出遞迴 因為是數列要相加 所以 else return (sum + sin_cal(x, exp+2)); 此時發現，哇，怎麼沒有正負號 方法a. 在呼叫時，多一個參數去記+/- (再回頭增加參數sign,並把 return ( sum + sin_cal( x, exp+2 )); => return ( sum*sign + sin_cal( x, exp+2 , -1*sign )); 方法b. 計算sum時，把+/-也計算進去 但在終止條件就需要把正負號考慮進去 (否則負數永遠小於0.000001) vi. 最後再把全部程式整理一下 vii.把如何呼叫的部份也說明一下 float x=1.0; //設定x sin_cal( x , 1 , 1); 能寫到什麼程度，就盡量寫，但是要以有把握不寫錯的部份 考試時間不多，不用考慮太難太漂亮的寫法 這個程式，拿來現實上會被complain，但是在考試上是OK的 ----- 遞迴程式 float sin_cal(float x, int exp,int sign) { float sum=1.0; int i; for( i=1 ; i<exp ; i++) { sum = sum * x / i; } if(sum<0.000001) return 0; else return (sin_cal(x,exp+2,-1*sign) + sign*sum); } 呼叫時: sin_cal(1,1,1);//x=1時 sin_cal(0.2,1,1);//x=0.2時 sin_cal(2.1,1,1);//x=2.1時 以上為大致思考過程，希望對大家有所幫助， 若有謬誤之處還請指教、見諒。 最後，筆者覺得有一個遞迴可幫助思考 一個single link list的字串如何用遞迴方式反轉字串 有空可以思考一下。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 119.14.0.193 ※ 編輯: hetea 來自: 119.14.0.193 (09/25 11:16)