for文を用いた階乗の計算

Question

前提

C言語を学び始めています。
「2 の 1 乗から 8 乗までを計算し表示するプログラムを作成しなさい。」と演習問題において、解答が以下のソースコードのようになっていました。

iについてはfor文で「printf("2の%d乗=」の部分が1~8の間で徐々に増えていくところまでは理解出来てるんですが、なぜxが2の階乗で増えて行くのか理解出来ていません。

少し噛み砕いて教えていただけると助かります。

該当のソースコード

int main(void)
{
    int x = 1;
    int i;

    for (i = 1; i <= 8; i++)
    {
        x = x * 2;
        printf("2の%d乗=%d\n", i, x);
    }
}```

Comments

[LouiS0616]

重箱の隅ですが、階乗ではなく累乗だと思います。

[fana]

何が問題点なのかが不明瞭に思えます．

「べき乗（or 累乗）とは何か？」とか「i番目の項はi-1番目の項に2を掛ければ求まるよね」みたいな内容の回答が既に付いていますが，不明点はそこらへんの話に関するものですか？
それとも，コード内にある

> x = x * 2;

っていう記述がそもそもどういうことなのかわからん（→から，このプログラムの動作が把握できない），っていうような事柄の側ですか？

[tetsu1231]

回答ありがとうございます
そもそもfor文がxにもかかっているということが分かってなかったです
for文の中ではiが一つずつ増えていくという計算式が書かれているのに、何でxが影響受けるんだろうという基本的なことが疑問でした。。

[jimbe]

影響があるのは for によって「 x = x * 2 ( と printf) が 8 回繰り返される」という所です。

Answer 1

まず、コードを理解するよりも「◇の○乗とは何か」を理解した方が早いかもしれません。
ここでは nのm乗を n^m と表現するとします。
このn^mの定義はなんでしょうか。べき乗と呼ばれていて、こちらによると

同じ数をくり返しかけ算したもののことを、累乗と言います。

とありますね。
掛け算としてたとえば 3×10は 3を10回足したものですが、『足したもの』ではなく『かけたもの』がこのべき乗ですね。
ではこのべき乗を計算するときはどのように計算しますか?

たとえば3^10だとどうなるでしょうか。3×3×3×(中略)×3のように3を10回かけたものです。

では、この計算式を質問者さんはどのように解きますか?
つまり 3^10 はどのように計算しますか?

私ならまず 3×3をします。そして結果は9なのでこの結果をノートかなんかに記録しておく。
そして次の ×3 を 先ほど記録した結果と一緒に計算する。つまり 9×3 = 27ですね。
ということで先ほど記録した数字(9)を(27)に更新する。
さらに ×3 をする。27×3 = 81 なので、先ほど記録更新した (27) を (81)に更新する。
…とこれを最後まで繰り返す。そうすると最終的に3^10の結果が求まる。

記録を X とすると、

X = 3 * 3
X = X * 3
X = X * 3
...
X = X * 3

のようになるはずです。
最初の X = 3 * 3 以外は常に X = X * 3 という式になっています。
で、最初の X = X * 3 も Xの初期値を1と仮定すると X = 1, X = X * 3, X = X * 3が成り立ちます。
ということは X の初期値を1としていたなら、X = X * 3という式が成り立つ。

そして今回求めたいのは2^1, 2^2, 2^3, ... 2^7, 2^8という1乗から8乗までの数列みたいなものですよね。
では、2^1から2^8までを同じく計算してみてください。

2^1 = 2
2^2 = 2 * 2
2^3 = 2 * 2 * 2
2^4 = 2 * 2 * 2 * 2
2^5 = 2 * 2 * 2 * 2 * 2
...
2^8 = 2 * 2  * 2  * 2  * 2  * 2  * 2  * 2

というような計算になるはずです。(面倒なので答えは出しませんが)
よー－－－－－－－く見てください。
何かに気づきませんか？

そう、『nにm乗するとしたら、m が +1 するごとに n が一つ多くかけられている』ですね。
3^1から3^8とかだと3が一つ多くかけられる…ですけど。

たとえば 2^4 は 2^3 にさらに ×2 した値になっているはずです。

つまり n^m としたら、n^m = { n^(m-1) } * n という計算式が成り立つ。
an = { 2^1, 2^2, 2^3, ... 2^8 }という数列とみなすと、前項に ×2 した値になる。
漸化式a(m+1) = am × n となる。(n^mの数列なのでちょっと変更)
つまり、2^1 が求まっていれば 2^1 にさらに ×2 すれば 2^2 になるし、
2^3 が求まっていれば 2^3 に ×2 をすれば 2^4 が求まる。

どのみち 2^1 から 2^8までをそれぞれ求めるのだから、個別に 2^1 を求めて 2^2 を求めて…とやるよりも
『前項(ひとつ前の値)に2をかけていく』だけで それぞれ求まるのでfor文で一気にやっているのです。

一応 2^1 = 2, 2^2 = 2 * 2, 2^3 = 2 * 2 * 2, 2^4 = 2 * 2 * 2 * 2, ... と一つずつ解いてもいいですが、面倒だし前項に2をかければ求まるのだから…ということです。

『2の段(掛け算九九)を列挙すること』の掛け算ではなくべき乗版ってところでしょうか。

Comments

[jimbe]

> 最初の X = X * 3 以外は常に X = X * 3
同じになっちゃってます。

[BeatStar]

本当ですね…すみません修正します

Answer 2

「x = x * 2」の部分が「for」によって、繰り返し実行されているのはわかりますでしょうか。

1回目の実行時は「2 = 1 * 2」になります。
2回目の実行時は、1回目の計算結果を利用するため「4 = 2 * 2」(4 = 1 * 2 * 2)になります。
常に左辺は前回の計算結果が入りますので、3回目は「8 = 4 * 2」(8 = 2 * 2 * 2)になり、結果が2の累乗になっています。

Comments

[Zuishin]

2 の階乗は 2 です。

[Matsumon0104]

> Zuishinさん
ご指摘ありがとうございます。
誤記修正しました。

[tetsu1231]

回答ありがとうございます
そもそもfor文がxにもかかっているということが分かってなかったです
for文の中ではiが一つずつ増えていくという計算式が書かれているのに、何でxが影響受けるんだろうという基本的なことが疑問でした。。

[tetsu1231]

当たり前のこと過ぎることを聞いてるかもなんですが、iとxの関係性についてもう少し教えていただけると幸いです

[Matsumon0104]

iとxに直接的な関係はありません。
iは単純にforのループの終了条件であることと、結果表示時に何回目(何乗)であるかを示すために利用されています。
xは計算結果を保存、次ループの計算式への利用、結果表示するために利用されています。

あえて、関係性を見いだせというのであれば、2の何乗まで計算するかの制御(ループ)といったらいいでしょうか。

直接的に関係性がないといったのは、例えば、iの値が下記のように10ずつ加算されるようなforのプログラムでも出力される計算結果(x)は変わりません。(結果表示部のi乗の部分は変わる)

// iの制御を変えてみる
for (int i = 1; i < 100; i += 10) {
x = x * 2;
printf("2の%d乗=%d\n", i, x);
}

// 計算結果(右辺:x)はiの影響を受けないので、変わらない
2の1乗=2
2の11乗=4
2の21乗=8
2の31乗=16
2の41乗=32
・
・

[episteme]

for ( iで示した回数だけ以下を繰り返す ) {
　x を2倍しろ
}
..なにがわからんですか?

[BeatStar]

(基礎すら理解していない可能性が濃厚…)

[tetsu1231]

@Matsumon0104さん
丁寧に解説していただき、ありがとうございます。
「iは単純にforのループの終了条件であることと、結果表示時に何回目(何乗)であるかを示すために利用されています。xは計算結果を保存、次ループの計算式への利用、結果表示するために利用されています。」
という解説と、10ずつ加算されるようなforのプログラムの説明がリンクし、よく理解出来ました。

何が分かってないのか言語化出来ていないところから、根気強く丁寧に解説していただき誠にありがとうざいました。