今年拿了第一屆培正數學邀請賽中四組最後一題給labmate玩玩。Recap一次題目：
設n和m為正整數，並符合 n/m = 0.666（取至三位有效數字）。求n的最小值。
Labmates們隨意說了一些方法：
1) Binary Search. 易知 m = 100不可行，而m=500可行。那麼就試m=(100+500)/2=300。m=300不可行的話就試m=(300+500)=400，可行的話就試m=(100+300)=200，如此類推。
2) Continued Fraction.我也不知怎樣簡介。就看wiki好了。
我想這兩個方法均不可行。你們知道為甚麼嗎？
2 則留言:
For case 1,
Give him an counterexample is easy to explain why Binary search not work.
Ask him to check for m=499 and m=501
both m=499 and m=501 不可行 but m=500 可行
>m=300不可行的話就試m=(300+500)=400
so he cannot exclude the solution is in btw 100 ~ 300.
Yes, I gave a similar explaination to them also.
張貼留言