2011年1月30日日曜日

算数オリンピック 教室1-Q1


このエントリーをはてなブックマークに追加


http://www.sansu-olympic.gr.jp/class1/q1.html

に挑戦。
A0=1999,     B0=0
A1=A0-A0/2,  B1=B0+A0/2
A2=A1+B1/3,  B2=B1-B1/3
A3=A2-A2/4,  B3=B2+A2/4

n=偶 An=A(n-1) + B(n-1)/(n+1), Bn=(1-1/(n+1))B(n-1)
n=奇 An=(1-1/(n+1))A(n-1),     Bn=B(n-1)+A(n-1)/(n+1)

覚えたての再起処理でよゆーw かとか思って、
(defun beakera (n)
        (cond
          ((= n 0) 1999)
          ((evenp n) (+ (beakera (- n 1)) (/ (beakerb (- n 1)) (+ n 1))))
          ((oddp  n) (* (- 1 (/ 1 (+ n 1))) (beakera (- n 1))))
          (t nil)))

(defun beakerb (n)
        (cond
          ((= n 0) 0)
          ((evenp n) (* (- 1 (/ 1 (+ n 1))) (beakerb (- n 1))))
          ((oddp  n) (+ (beakerb (- n 1)) (/ (beakera (- n 1)) (+ n 1))))
          (t nil)))
とか書いて、REPLで (beakera 1999) としたら固まった。。。ポカーン


アレ?と思って手で解いてみると。。。
A0=1999=t,   B0=0

A1=A0-A0/2,  B1=B0+A0/2
  =t/2         =t/2

A2=A1+B1/3, B2=B1-B1/3
  =t/2+t/6    =t/2-t/6
  =2t/3       =t/3

A3=A2-A2/4,  B3=B2+A2/4
  =2t/3-t/6    =t/3+t/6
  =t/2         =t/2

A4=A3+B3/5,  B4=B3-B3/5
  =t/2+t/10    =t/2-t/10
  =3t/5        =2t/5

A5=A4-A4/6,  B5=B4+A4/6
  =A3t/5-t/10  =2t/5+t/10
  =t/2         =t/2

って、奇数回目は必ず同じ数になるのか。
ということで、1999回目は奇数回目なので答えは1999/2

これをプログラムで効率よく解くにはどうすればよいんだろう??

算数恐るべし。。。
そして自分の頭のへぼさに絶望。。

0 件のコメント:

コメントを投稿