プログラミング入門第８回講義問題 1 任意の整数 v (v>0) は 2 のベキ乗の組み合せで表現できる。例えば整数 13 は以下のように分解できる。 13 ＝ 8＋4＋1 ＝ 23＋22＋20 2 の 0 乗から 2 の 9 乗までの値は以下の通りである。 1 2 4 8 16 32 64 128 256 512 以下の処理の流れに従って、キーボードから入力された整数 v（1〜511 の範囲とする）を 2 のベキ乗の組み合わせに分解するプログラムのフローチャートを書きなさい。また、作成したフローチャートにもとづき、プログラムを書きなさい。 1. 2 の 0 乗から 2 の 9 乗までの値を順に作り、配列に格納する 2. この配列のすべての要素の値を 1 行に出力する 3. 1 から 511 までの整数をキーボードから入力する 4. 入力された数を、配列の要素値（2 のべき乗の値）を用いて分解し、結果を出力する [実行例 1] (下線付きの太字はキーボードからの入力を示す) % ./a.out 1 2 4 8 16 32 64 128 ←注：2 のベキ乗の値の出力 256 512 ←注：1 から 511 までの整数の入力 13 13>>8 4 ←注：分解処理の結果の出力 1 [実行例 2] % ./a.out 1 2 4 8 16 32 64 128 256 512 511 511 >> 256 128 64 32 16 8 4 2 [実行例 3] % ./a.out 1 2 4 16 16 >> 16 8 16 32 64 128 256 512 1 ヒント：キー入力された値が変数 v に、また 2 のベキ乗の値は配列 data に入っているとする。 1. v の値が配列要素の何番目と何番目の要素の値の間に入るのか、配列の後ろから「比較」する 2. ある i に対し（data[i] > v）かつ（data[i-1] <= v）であれば、data[i-1] を v から分解した値として「出力」し、v から data[i-1] を引く 3. 新しい v に対して上記の「比較」と「出力」を継続する