東京大学 情報理工学系研究科 電子情報学専攻 2026年1月実施 専門 第3問

标签：

• Tokyo-University
• Binary-Search

Author

瑞穂

Description

(1) Write the pseudo code of binary search, with no recursion.

(2) Calculate the result of $\sqrt{2}$ using (1)'s pseudo code, with $\delta$ (error) less than 0.01.

(3) Write the pseudo code of binary search, with recursion.

Given formular $\sqrt{2}=1+\frac{1}{1+\frac{1}{1+...}}$, and series $r_n=1+\frac{1}{1+r_{n-1}}$,

(4) Prove (a) $r_{2n} \leq \sqrt{2} \leq r_{2n+1}$, and (b) $\frac{r_{n+2}-r_{n+1}}{r_{n+1}-r_{n}}=\frac{-1}{2r_{n}+3}$. Also calculate $\sqrt{2}$ with $\delta < 0.001$.

(5) Given function $y=x^2-2$, calculate $\sqrt{2}$ via Newton method, and the initial point is $x=2$, $\delta<0.0001$.