Re: [心得] 高考資訊處理心得(收到成績單後)

看板Examination (國家考試)作者hetea (hetea)時間17年前 (2008/09/25 11:15)推噓1(1推 0噓 2→)

留言3則, 3人參與討論串2/2 (看更多)

※ 引述《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)