高考資訊處理心得(收到成績單後) - 考試

※ 引述《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的字串如何用遞迴方式反轉字串

有空可以思考一下。

--