0272-2013 名情复 编程 P218

编程语言基础 C语言 位运算 进制转换 递归

C言語における以下の問に答えよ。ただし、\は¥と同じである。

[1] 次のプログラムの出力結果を示せ。

int main(void){
    int a=0Xf123;
    printf("%x\n %x\n", a<<2, a>>4);
    return 0;
}
 

[2] 10進数である3を2進数で表記した文字列を，10進数と見なした場合の値を求める処理過程は以下のステップで構成される。括弧内に適切な文を記述せよ。

1. (1) すると，商1と剰余1を得る。
2. (2) すると，商0と剰余1を得る。
3. (3) なので，操作を終了する。
4. ステップ2)の剰余1と1)の剰余1を左から右へ順に並べた文字列“11”を10進数表記と見なした値11が，求める値である。

[3] 問題[2]を参考にして，$a$ を $n$ 進数で表記した文字列を10進数と見なした場合の値を求めるアルゴリズムを記述した。ただし，$a$ は $0\le a$ なる整数，$n$ は $2\le n\le 9$ なる整数である。括弧内に適切な文を記述せよ。

1. 整数変数$x$に$a$，整数変数$y$に$0$，整数変数$i$に$0$を代入する。
2. (1) れば次へ進む。そうでなければ，$y$を出力して終了する。
3. (2) を整数変数$z$へ代入する。
4. $y$に$y+z\times 10^i$を代入する。
5. (3) を$x$へ代入する。
6. $i$に$i+1$を代入する。
7. 2)へ戻る。

[4] 問題[3]のアルゴリズムを用いて，整数値$x$を$n$進数で表記した文字列を10進数と見なした場合の値を返す関数 fnc1 を C 言語で作成した。プログラムで用いている変数名は問題[3]に対応している。pow(a,b)は整数型変数aとbについて，aのb乗を計算する関数である。下線部に入れるべき式，または式の一部を答えよ。

int fnc1(int x, int n){
    int y=0, i=0, z;
    while( _______(1)_______ ){
        z = _______(2)_______ ;
        y += z*pow( _______(3)_______ ) ;
        x = _______(4)_______ ;
        i++;
    }
    return y;
}

[5] 大きさ$n$の整数型1次元配列aの各要素のうち，整数xと等しくない要素の総和を求める関数 fnc2 を再帰的プログラミングで作成した。関数 fnc2 は，a, n, x を引数として受け取り，演算結果を返す。下線部に入れるべき式，または式の一部を答えよ。ここで，同じ番号の括弧には同じ式，または式の一部が入る。

int fnc2(int a[], int n, int x){
    if(n>0){
        if( _______(1)_______ ){
            return _______(2)_______ + _______(3)_______ ;
        }else{
            return _______(3)_______ ;
        }
    }else{
        return _______(4)_______ ;
    }
}

---

解答：

[1]
変数 $a$ の値は16進数で定義されている。

$$a=0xf123$$
左シフト演算 << 2 は $2^2$ を掛けることと同値である。
$$a\ll 2=0xf123\times 2^2=0x3c48c$$
右シフト演算 >> 4 は $2^4$ で割った商を求めることと同値である。

$$a\gg 4=\lfloor 0xf123/2^4\rfloor =0xf12$$
printf文の書式文字列 "%x\n %x\n" により、2つ目の出力の前にはスペースが入る。
$$\boxed{\begin{array}{rl}& \text{3c48c}\\ & \text{ f12}\end{array}}$$

[2]
10進数を $n$ 進数へ変換する際の短除法のプロセスである。
(1)

$$\boxed{\text{3 を 2 で割る}}$$
(2)
$$\boxed{\text{1 を 2 で割る}}$$
(3)
$$\boxed{\text{商が 0}}$$
[3]
[2] の処理を一般化し、商が0より大きい間、剰余を抽出して順に桁を構築する。
(1)
$$\boxed{x>0}$$
(2)
$$\boxed{x\text{ を }n\text{ で割った剰余}}$$
(3)

$$\boxed{x\text{ を }n\text{ で割った商}}$$
[4]
[3] のアルゴリズムをC言語の演算子で実装する。
(1)
$$\boxed{x>0}$$
(2)
$$\boxed{x\%n}$$
(3)
$$\boxed{10,i}$$
(4)
$$\boxed{x/n}$$
[5]
配列の末尾の要素 a[n-1] から再帰的に判定し和を計算する。要素が x と異なる場合はその要素を足し合わせ、等しい場合は足さない。要素数 $n$ が0のときが再帰の底となる。
(1)
$$\boxed{a[n-1]\ne x}$$
(2)
$$\boxed{a[n-1]}$$
(3)
$$\boxed{\text{fnc2}(a,n-1,x)}$$
(4)
$$\boxed{0}$$

本题涉及C语言的基本编程概念。第一题考查了位运算和格式化输出，左移相当于乘二的次幂，右移相当于除二的次幂，同时需要注意格式字符串中隐藏的空格。第二三四题连贯地考察了进制转换算法及其C语言实现，核心是利用短除法不断取余数作为当前位，利用除法更新商，并在代码中使用取模运算和整除运算代替文字描述。第五题考查了数组上的递归思想，通过将处理前n个元素转化为处理最后一个元素与处理前n-1个元素的组合，当数组大小降为0时返回0作为递归基，从而优雅地实现条件求和逻辑。