数学I・数学A 第5問

始めに解いたときは何のプログラムか解らなかったので「意味不明のプログラム」とか「背景が不明なので解きづらい」とか書いていたのは私です。今となっては己が不明を恥じるのみ。$X$$N$乗を求めるプログラムですね。

第5問(選択問題)(配点 20)
(1)次の流れ図を考える。ただし,$N$には自然数を入力することとする。
流れ図
$X=2$$N=5$のとき,この流れ図にそって計算すると,$Y$は[ アイ ]となる。

美しさに欠ける流れ図が与えられました。$X=2$$N=5$でこの流れ図に沿って計算してみろと言われてます。えー。
このアルゴリズムに接したことのある方は「あーはいはい。$X$$N$乗を求めるプログラムね」とシタリ顔で頷いて「$2^5 = 32$が答えです。」と直ちに答えが導けます。
私のように何のプログラムか解らなかった人は、コンピュータになったつもりで計算しましょう。このプログラムでどうして$X$$N$乗が求まるかはあとで述べます。
さて変数の変化を見ながら流れ図を追いかけていくと下のようになります。
\begin{displaymath}\begin{array}{c\vert c\vert c\vert c}& X & N & Y \\ \hline......to N/2 & & 0 & \\N = 0\mbox{なので終了} & & & 32\end{array}\end{displaymath}
となって$Y$は32になります。
答 [ アイ ] = 32

また,$X=1$$N=13$のとき,この流れ図にそって計算すると,処理[ $Y$$Y\times X$を代入 ]は[ ウ ]回実行され,処理[ $X$$X^2$を代入 ]は[ エ ]回実行される。

1の13乗を求めるときに[ $Y$$Y\times X$を代入 ]と[ $X$$X^2$を代入 ]は何回実行されるのか?うーむ。これはアルゴリズムを知ってようが知ってまいが処理を追いかけるしかないですね。再びコンピュータ化します。
\begin{displaymath}\begin{array}{c\vert c\vert c\vert c}& X & N & Y \\ \hline......sto N/2 & & 0 & \\N = 0\mbox{なので終了} & & & 1\end{array}\end{displaymath}
[ $Y$$Y\times X$を代入 ]は上の表で「$N$が偶数でない」と書いたところで実行されます。数えて3回実行されることが解ります。
[ $X$$X^2$を代入 ]は「$X \mapsto X*X$」で実行されるので、これも3回です。
答 [ ウ ] = 3、[ エ ] = 3

(2) 次のプログラムを考える。ただし, Nには自然数を入力することとする。また, INT(A) Aをこえない最大の整数を与える関数とする。
    100 INPUT "X=";X
    110 INPUT "N=";N
    120 Y=1
    130 X=X*X
    140 IF N-2*INT(N/2)=0 THEN GOTO 160
    150 Y=Y*X
    160 N=INT(N/2)
    170 IF N=0 THEN GOTO 190
    180 GOTO 140
    190 PRINT "Y=";Y
    200 END
このプログラムを実行し, Xに2, Nに5を入力すると, Y=[ オカ ]と表示される。

「上の流れ図をコーディングしたんだから答は32じゃん」と考えるとハマリます。間抜けなプログラマが間違ったコーディングしちゃってるんですよ。三度コンピュータ化して流れを追いかけると間違いが解ります。 Nが奇数のときだけ150行が実行されるのに留意して追いかければ簡単でしょう。
\begin{displaymath}\begin{array}{c\vert c\vert c\vert c}& X & N & Y \\ \hline......& 4\times 4 = 16 \\160 & & 0 & \\190 & & & 16\end{array}\end{displaymath}
ちょっと表がそっけないけど大丈夫でしょうか。とにかく上のようになって16が表示されます。
答 [ オカ ] = 16

(3) (2)のプログラムを(1)の流れ図の処理を実行するプログラムに書き換えるためには,130行を削除し,[ キ ]行として X=X*Xを追加すればよい。ただし,[ キ ]には次の(0)〜(3)のうちから当てはまるものを選べ。
(0) 115    (1) 145    (2) 155    (3) 175

前の設問で調子に乗って「答は32じゃん」と言っていても、この問題を読めばハマッテることに気付けます。そして おもむろにプログラムを追いかける。私がそうでした。
前の設問で追いかけてれば X=X*Xの位置がおかしいのに気付くでしょう。「$N$は0か?」の条件分岐のあとになければいけないのに、「$Y$に1を代入」のすぐ下にきてます。正しくするためには「$N$は0か?」の下、すなわち170行の下に移せばよいので答は(3)の175です。
答 [ キ ] = 175
間抜けなプログラマがコーディングを間違えたと書きましたが、このプログラマの気持ちは解ります。
寝不足の日に流れ図を見てループをぐるぐる追いかけてたら X=X*Xが上にあっても下にあっても良いような気分になるかもしれません。そして、もし X=X*Xが上にあっても良いのであれば、プログラムはかなりキレイになるのです。こんな感じに
    100 INPUT "X=";X
    110 INPUT "N=";N
    120 Y=1
    130 X=X*X
    140 IF N-2*INT(N/2)<>0 THEN Y=Y*X
    160 N=INT(N/2)
    170 IF N<>0 THEN GOTO 130
    190 PRINT "Y=";Y
    200 END
GOTO文が減って、130から170がキレイなループになります。
まあいくらキレイになってもプログラムが間違ってちゃ話になりません。しかもキレイにしようと思って間違えたのなら130行に飛ばさなきゃいけない GOTOは140行に飛んでるし、140行の IFの処理は汚いしとやっぱり間抜けなプログラマという感じです。
さてプログラマをいじめるのはこの辺にして。何故このプログラムで$X$$N$乗が求まるのか見てきましょう。
例として$x$の13乗を計算することを考えます。単純にやるには
\begin{displaymath}x^{13} = x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x\cdotx\cdot x\cdot x\cdot x\end{displaymath}
$x$を13回掛ければ良いです。コンピュータにやらせれば黙ってやってくれます。「私はこんな単純な仕事するためにこの会社に入ったんじゃありません!」と意見されたりしません。
「文句言う前に結果出せよ!」と言いながらも「まあ確かに単純な仕事やったかもしれんな」と反省した場合には
\begin{displaymath}x^{13} = x \cdot x^6 \cdot x^6\end{displaymath}
とすると簡単に計算できそうな気がしますね。計算量も大幅に減りそうな予感。
さらに続けて
\begin{eqnarray*}x^6 & = & x^3 \cdot x^3 \\x^3 & = & x \cdot x^1 \cdot x^1\end{eqnarray*}
とやってくと計算量さらに減らせます。
実際に、最初のように力まかせにやると$N$に比例した計算時間がかかりますが、工夫して計算すると$\log N$に比例した計算時間になるそうです。13乗ぐらいじゃ効いてきませんが1000乗、10000乗などになると効いてくるでしょう。
で、このように工夫して$X$$N$乗を計算してるのがこのプログラムです。そう思って見直してみれば各々の処理の意味も解るでしょうか。
さて、ここから先は完全に関係ない話。御用とお急ぎのない方だけお進み下さい。
$x$$n$乗を返す関数$pow(x, n)$を考えてみましょう。この関数は再帰的に定義することができます。こんな感じ。
\begin{displaymath}pow(x, n) = \left\{ \begin{array}{ll}1 & (n = 0) \\x\cdot pow(x, n-1) & (n \neq 0)\end{array} \right.\end{displaymath}
右辺にも$pow$が現れるのが「再帰的」ということです。「再帰って何?」という疑問はこの答でしばらく納得してて下さい。
で、これは力任せに$x$$n$乗を求める方法に対応してて、計算時間は$n$に比例します。ちょっと工夫した定義は
\begin{displaymath}pow(x, n) = \left\{ \begin{array}{ll}1 & (n = 0) \\pow......w(x^2, \frac{n-1}{2}) & (n : \mbox{奇数})\end{array} \right.\end{displaymath}
です。これで本当に定義できてるのか2の5乗を計算して確かめてみましょう。
\begin{displaymath}\begin{array}{llllllll}pow(2, 5) & = & 2\cdot pow(2^2, \fr...... & \\& = & 32 & & & & & \\& = & 2^5 & & & & &\end{array}\end{displaymath}
$n$がどんどん減りながら$pow$が再帰的に呼び出されていって、最後$n = 0$のところで止まって帰ってくる感じが解るでしょうか。
この計算を追いかける感じと、問題のプログラムを追いかける感じと似てませんか? 似てるでしょ? ね、似てます。問題のプログラムは、この関数定義をプログラム化したものです。
再帰的な定義をそのままプログラム化すると
    double pow(double x, int n) {
        if (n == 0) return 1;

        if (n % 2 == 0) {
            return pow(x*x, n/2);
        } else {
            return x*pow(x*x, (n-1)/2)
        }
    }
となります。このプログラムを再帰を用いずに書き直します。何でそんなことを考えるかというと、再帰を用いたプログラムは必ずループを用いて書き直すことができるからです。計算機科学の学者さんが証明しました。本屋で計算機科学の本を立ち読みすればどっかに書いてあるはず。
とにかく書き直すと
    double pow(double x, int n) {
        int y = 1;

        while (n != 0) {
            if (n % 2 != 0) {
                y *= x;
                x = x * x;
                n = (n - 1) / 2;
            } else {
                x = x * x;
                n = n / 2;
            }
        }

        return y;
    }
こんな感じでしょうか。一回のループが一回の関数呼び出しに対応します。
これでほぼ問題のプログラムになりました。 (n-1)/2 INTを使って巧いこと処理することにして、 if文の中で重複している処理を外に出すと問題のプログラムにかなり近付きます。そういう工夫をして行番号付きBASICで書いてみます。
    100 INPUT "X=";X
    110 INPUT "N=";N
    120 Y=1
    130 IF N=0 THEN GOTO 180
    140 IF N-2*INT(N/2)<>0 THEN Y=Y*X
    150 N=INT(N/2)
    160 X=X*X
    170 GOTO 130
    180 PRINT "Y=";Y
    190 END
これで問題のプログラムは$X$$N$乗を求めるプログラムだったと納得していただけるでしょうか。
趣味の範疇ですが、問題のプログラムも最後に私が書いたように書くべきだったと主張します。オリジナルはGOTO文使いすぎだし、ループが汚いです。
でも、もっともっと良いのは再帰を用いた関数を出題することです。行番号BASICという制限の中でアルゴリズムに注力するここ数年の出題には敬意を表しますが、出題者の努力だけでは やはり限界があります。
文部科学省の担当者の方に再び平身低頭して申し上げます。高校生に教えるプログラミング言語の再検討をお願い致します。

せぎてつ伝言板
このページの感想をどうぞ!
お名前(匿名OK):

メールアドレス:
最終更新日 : 2001年10月26日(金)
segi@ra2.so-net.ne.jp