基本情報技術者 2009年 秋期 午後 問09
次のCプログラムの説明及びプログラムを読んで、設問1，2に答えよ。
〔プログラムの説明〕
C言語では整数型の変数に格納できる値には上限がある。これを超える正の整数（以下、正の多倍長整数という）の入出力と加算を行うプログラムである。
(1) 正の多倍長整数は、次に示すMP型の構造体を用いて表現する。
typedef struct{
int length;
long data[ARRAY_MAX];
}MP;
正の多倍長整数を、下位から9けたずつに切り分けて、構造体MPのメンバである配列dataの要素番号の小さい方から順番に値を格納する。例えば、46284059827463859201283844157134007652918723147641という整数の場合、図のとおりになる。
構造体のメンバlengthには、実際に値を格納した要素数を入れる。図の場合は6である。
(2) 関数の仕様は、次のとおりである。
void set(MP *num, const char str[]);
引数：num MP型の構造体で表現された多倍長整数
str 文字列で表現された多倍長整数であって、1～9の数字で始まる。
機能：文字列で与えられた多倍長整数strを変換して、MP型の構造体numに格納する。numのメンバdataは、変換後の数値を格納するのに十分な要素数が確保されているものとする。
返却値：なし
void print(const MP *num);
引数：num MP型の構造体で表現された多倍長整数
機能：多倍長整数を出力する。
返却値：なし
void add(const MP *a, const MP *b, MP *c);
引数：a, b, c MP型の構造体で表現された多倍長整数であり、cは、a及びbではないものとする。
機能：二つの多倍長整数a, bの和を多倍長整数cに格納する。cのメンバdataは、加算処理を行うのに十分な要素数が確保されているものとする。
返却値：なし
(3) 次のライブラリ関数を用いる。
size_t strlen(const char *s);
機能：sが指す文字列の長さを計算する。
返却値：終端を示すナル文字に先行する文字の個数を返す。
設問1：
問題文を見る プログラム中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：str_idx != 0
イ：str_idx < 0
ウ：str_idx <= 0
エ：str_idx > 0
オ：str_idx >= 0
bに関する解答群
ア：i < NUM_DIGIT
イ：i < NUM_DIGIT && str_idx <= 0
ウ：i < NUM_DIGIT && str_idx >= 0
エ：i < NUM_DIGIT || str_idx <= 0
オ：i < NUM_DIGIT || str_idx >= 0
cに関する解答群
ア：%= 10
イ：*= 10
ウ：+= 10
エ：-= 10
オ：/= 10
dに関する解答群
ア：i = 0; i <= num->length - 1; i++
イ：i = 0; i <= num->length - 2; i++
ウ：i = num->length - 1; i >= 0; i--
エ：i = num->length - 2; i >= 0; i--
模範解答
a：オ、b：ウ、c：イ、d：エ
解説
解答の導き方
このプログラムでは、長い整数を9けたずつに分けて扱います。配列は、同じ種類の値を番号で区別して並べておく入れ物です。構造体は、複数の項目をひとまとめにして扱う型です。この問題では、MP型の構造体に、使った配列要素の数と、9けたごとの値を格納します。
まず、set関数は文字列の右端から数字を読み、9けたずつ配列に格納します。
- 文字列の長さは、strlen(str)で分かります。文字列の添字は先頭が0なので、最後の文字の添字は「文字列の長さ−1」です。したがって、str_idxは文字列の右端の位置を表します。
- str_idxが0なら、まだ先頭の文字を読んでいません。そこで、添字が0のときも処理する必要があります。読み終えるとstr_idxは−1になるため、文字が残っている間の条件は「str_idx >= 0」です。よって、aにはオが入ります。
- 1回の内側のループでは、最大9文字を読みます。一方、最後のまとまりは9けた未満の場合もあります。そのため、「9文字に達していないこと」と「読む文字が残っていること」の両方を満たす条件にします。bにはウが入ります。
- mulは、右端の数字から順に掛ける数です。最初は1で、次の桁では10、その次は100となるよう、数字を1つ読むたびに10倍します。したがって、cはイの「*= 10」です。
この動きを、問題文にある数値で見ると、右から最初の9けたは723147641です。その次の9けたは007652918で、数値として配列に格納すると7652918になります。次のまとまりをdata[2]、さらに次をdata[3]というように格納します。これを続け、すべての文字を読み終えたところで、使った要素数をnum->lengthに設定します。
次に、print関数は、最も大きい位のまとまりから順に出力します。最も大きい位は先頭に不要な0を付けないため、最初にnum->data[num->length - 1]を出力しています。その次は、ひとつ下の要素からdata[0]までを出力します。
各まとまりは9けたで表示する必要があります。たとえば、値が7652918なら、出力時に007652918と表示します。書式「%09ld」は、値を少なくとも9けたで表示し、足りない桁を0で埋める指定です。すでに出力した最後の要素を除き、ひとつ下の要素から0番目まで順に進めるので、dにはエが入ります。
誤りやすいポイント
- aで「str_idx > 0」とすると、添字が0の文字を処理できません。文字列の先頭の数字も読む必要があります。
- aで「str_idx != 0」とすると、str_idxが−1になっても条件を満たし続けます。文字列の範囲外を読もうとするため、正しくありません。
- bは、9けたに達していないことだけでなく、読む文字が残っていることも確認します。二つの条件を同時に満たす必要があるので、論理積「&&」を使います。
- cでmulに10を足すと、桁の重みが1、11、21のように変わってしまいます。次の桁の重みは10倍にするため、掛け算が必要です。
- dで0番目から順に出力すると、整数の下位から上位へ表示されてしまいます。また、最も大きい位のまとまりをもう一度出力しないよう、開始位置はlength−2です。
FAQ
Q: 最後のまとまりが9けたに満たないときは、set関数でどう処理しますか？
A: str_idxが0の文字を読み取ったあと、str_idxが−1になります。内側のループはそこで終わり、読み取った分だけを最後のまとまりとして格納します。
A: str_idxが0の文字を読み取ったあと、str_idxが−1になります。内側のループはそこで終わり、読み取った分だけを最後のまとまりとして格納します。
Q: 途中のまとまりを9けたにそろえるのは、なぜですか？
A: たとえば、あるまとまりの値が7652918でも、前後のまとまりとの境目を保って整数全体を表示するには007652918と出力する必要があるためです。最も大きい位だけは、整数の先頭に余分な0が付かないよう、9けたにそろえません。
A: たとえば、あるまとまりの値が7652918でも、前後のまとまりとの境目を保って整数全体を表示するには007652918と出力する必要があるためです。最も大きい位だけは、整数の先頭に余分な0が付かないよう、9けたにそろえません。
Q: 配列の要素数を表すlengthには、何を格納しますか？
A: 実際に値を格納した要素の個数です。最後に使った要素の番号ではありません。たとえば、要素番号0から5まで使った場合、lengthは6です。
A: 実際に値を格納した要素の個数です。最後に使った要素の番号ではありません。たとえば、要素番号0から5まで使った場合、lengthは6です。
関連キーワード: 多倍長整数、配列、構造体、桁区切り、ゼロ埋め
設問2：
問題文を見る プログラムの動作について、次の記述中のに入れる正しい答えを、解答群の中から選べ。
関数addを用いて以下の(1)に示す二つの多倍長整数を加算する場合、プログラム中のα部分はe回実行され、β部分はf回実行される。また、以下の(2)に示す二つの多倍長整数を加算する場合、β部分はg回実行される。
e～gに関する解答群
ア：0
イ：1
ウ：2
エ：3
オ：4
カ：5
キ：6
ク：7
模範解答
e：オ、f：イ、g：エ
解説
解答の導き方
このプログラムでは、多倍長整数を下位のけたから9けたずつに分け、配列に格納します。加算も下位のまとまりから順に進みます。あるまとまりの合計が NUM_DIGIT_TH_POWER_OF_TEN の 1000000000 以上になると、次のまとまりへ繰り上がります。
まず、加算の繰返し回数を確認します。プログラムでは、二つの整数のうち長い方のまとまり数を i_max に設定しています。繰返しの中では、各まとまりについて繰上がりが必要かどうかを判定します。したがって、αの箇所に関わる判定は、まとまりの数だけ行われます。
(1) の場合
一つ目の整数は4まとまり、二つ目の整数は3まとまりです。よって、繰返しは4回です。αの箇所に関わる判定も4回行われるため、e は4です。
次に、各まとまりの合計を下位から確認します。二つ目の整数にないまとまりは、値が0だと考えます。
i=2 の合計は 1000000000 以上なので、次のまとまりに繰り上がります。βの箇所は繰上がりを設定する処理なので、この場合に1回実行されます。したがって、f は1です。
(2) の場合
一つ目の整数は6まとまり、二つ目の整数は5まとまりです。下位から順に足し、前のまとまりから繰り上がりがあれば、その分も加えます。
i=0、i=1、i=3 で合計が 1000000000 以上になり、次のまとまりへ繰り上がります。βの箇所はそのたびに実行されるため、g は3です。
誤りやすいポイント
- αの箇所に関わる判定回数と、繰上がりの回数を混同しないようにします。判定は各まとまりで行いますが、繰上がりが発生するとは限りません。
- βの箇所は、繰上がりが発生した場合に実行されます。合計が 1000000000 以上になるまとまりを数えます。
- 加算は、配列の要素番号が小さい下位側から行います。設問の数値が左から右へ並んでいるときは、右端のまとまりから確認します。
- 前のまとまりから繰り上がった 1 は、次のまとまりの合計に加えます。たとえば (2) の i=1 では、i=0 からの繰上がりも加算しています。
FAQ
Q: 合計が 1000000000 以上になったら、なぜ 1000000000 を引くのですか？
A: 一つのまとまりに格納するのは9けた分です。1000000000 分を次のまとまりに繰り上げ、今のまとまりには残りの値を格納するためです。
A: 一つのまとまりに格納するのは9けた分です。1000000000 分を次のまとまりに繰り上げ、今のまとまりには残りの値を格納するためです。
Q: βの箇所で次のまとまりに設定される値は何ですか？
A: 繰上がりがある場合は、次のまとまりを表す配列要素に 1 を設定します。繰上がりがない場合は 0 を設定します。
A: 繰上がりがある場合は、次のまとまりを表す配列要素に 1 を設定します。繰上がりがない場合は 0 を設定します。
Q: 二つの整数のまとまり数が違う場合は、どのように加算しますか？
A: まとまりの数が少ない方に存在しない部分は 0 として扱い、まとまりの数が多い方の最後まで加算します。
A: まとまりの数が少ない方に存在しない部分は 0 として扱い、まとまりの数が多い方の最後まで加算します。
関連キーワード: 多倍長整数、配列、加算、繰上がり、基数
