% na2015/na_rep01.tex
%
\documentclass[12pt,a4j]{jarticle}
\addtolength{\textheight}{5em}
\addtolength{\topmargin}{-2em}
\pagestyle{empty}
\begin{document}
\begin{center}
{\Large 数値解析\quad ( 塩田 )}
\vspace{1em}\\
2015年10月7日の宿題
\end{center}
\vspace{1em}

\begin{description}

\item[問題 ]
次のプログラムは漸化式
\vspace{-7pt}
$$
a_0 = 1,\quad a_1 = 1,\quad a_{i} = 2 \times a_{i-1} + a_{i-2}\quad (i = 2, 3, \cdots,31)
\vspace{-7pt}
$$
で定義される数列を２通りの方法で計算するプログラムである。

\begin{center}
\fbox{
\begin{minipage}{120mm}
\tt\baselineskip=13pt
\ 1: \#include<stdio.h>\rule{0pt}{20pt}\\
\ 2:\\
\ 3: int f(int i)\{\\
\ 4: \hspace*{24pt}if(i <= 1) return 1;\\
\ 5: \hspace*{24pt}else return 2 * f(i - 1) + f(i - 2);\\
\ 6: \}\\
\ 7: \\
\ 8: int main()\{\\
\ 9: \hspace*{24pt}int a[32], i;\\
10: \\
11: \hspace*{24pt}a[0] = 1; printf("a[ 0] = \%d$\backslash$n", a[0]);\\
12: \hspace*{24pt}a[1] = 1; printf("a[ 1] = \%d$\backslash$n", a[1]);\\
13: \hspace*{24pt}for(i = 2; i < 32; i++)\{\\
14: \hspace*{24pt}\hspace*{24pt}a[i] = 2 * a[i - 1] + a[i - 2];\\
15: \hspace*{24pt}\hspace*{24pt}printf("a[\%2d] = \%d$\backslash$n", i, a[i]);\\
16: \hspace*{24pt}\}\\
17: \\
18: \hspace*{24pt}for(i = 0; i < 32; i++)\\
19: \hspace*{24pt}\hspace*{24pt}printf("a[\%2d] = \%d$\backslash$n", i, f(i));\\
20: \}\\
\end{minipage}
}
\vspace{5pt}
\end{center}

\begin{itemize}
\item[(1) ]
11-16行目の計算方法と，18-19行目の計算方法はどちらの方が計算量が多いか，理由と共に述べよ。
\item[(2) ]
11-16行目の計算方法を，メモリを節約するために配列を使わない形で書き直せ。（出力文は省略して良い。）
\item[(3) ]
{\tt int} 型が4バイトの符号付き整数であるような処理系でこのプログラムを実行した場合，
{\tt a[31]} まで正しい値が出力されるか否か，理由と共に述べよ。
(単に「プログラムを動かしたらこうだった」は不可。)
\end{itemize}
\vfill

\item[提出方法 ]
メールにて shiota@is.kochi-u.ac.jp 宛て。
\begin{itemize}
\item[$\circ$]
件名を「数値解析10月7日の課題」とすること。
\item[$\circ$]
テキストでも、WORD 等のドキュメントでも可。
\end{itemize}
\vfill

\item[提出期限 ]
10月14日(水) 
\end{description}
\end{document}

