0251-2010 名情复 编程 P121

编程语言基础 C语言 排序算法 向量分析

[1] C言語で記述された以下のプログラムの画面出力結果を示せ。

#include <stdio.h>
int main() {
    int a, b;
    a = 1.5; b=9.7;
    printf("%d\n", a++ );
    printf("%d\n", b%a );
    printf("%d\n", b>>2);
    return 0;
}

[2] 関数 maxswap は，サイズ m の整数型配列変数 a と整数型変数 n ( $2\le n\le m$ )を受け取り， a[0], a[1], ..., a[n-1] のうちで最大値を格納する要素の要素番号を整数型変数 imax に代入する。続いて，変数 a の imax 番目の要素と a[n-1] の値を交換する。下線部に記載するべき式，または式の一部を答えよ。

int maxswap( int a[], int n ) {
    int i, imax, max;
    ____(1)____ ;
    for( ____(2)____ ; i++) if( ____(3)____ ) imax = i;
    max = a[imax] ; ____(4)____ a[n-1] = max ;
    return 0;
}

[3] 問題[2]の関数 maxswap を用いて整数型配列変数 a の要素を昇順に並べかえるプログラムを作成した。下線部に記載するべき式，または式の一部を答えよ。

#include <stdio.h>
int maxswap(int a[], int n);
int main() {
    int a[]={1,20,-3,100,5,-6,8,-10}, n=8, i;
    for(i=0; ____(1)____ ) maxswap( ____(2)____ );
    for(i=0; i<n; i++) printf("%d  ", a[i]);
    return 0;
}

[4] 零ベクトルでない2つのn次元ベクトルのなす角度を求めるプログラムを作成した。各ベクトルの値はサイズnの倍精度型実数配列aとbに格納されている。値xの平方根と逆余弦は，それぞれ関数 sqrt(x) と acos(x) で与えられる。括弧内に入れるべき式，または式の一部を答えよ。

#include <stdio.h>
____(1)____
int main() {
    int i, n=3;
    double a[]={1,2,3}, b[]={2,-1,1}, ____(2)____;
    for(i=0; i<n; i++){
        sa += a[i]*a[i];  sb += b[i]*b[i];  prod += a[i]*b[i];
    }
    printf("%lf ", acos(____(3)____) );
    return 0;
}

---

解答：

[1]
変数 $a,b$ は整数型(int)であるため、代入時に小数点以下が切り捨てられる。

$$a=1.5⟹a=1$$ $$b=9.7⟹b=9$$

printf("%d\n", a++ ); について、後置インクリメントであるため $1$ を出力した直後に $a=2$ となる。
printf("%d\n", b%a ); について、剰余演算であるため以下の値を出力する。

$$b(\mathrm{mod}a)⟹9(\mathrm{mod}2)=1$$

printf("%d\n", b>>2); について、右シフト演算は $2^2$ での除算と等価であるため以下の値を出力する。

$$b\gg 2⟹\lfloor 9/2^2\rfloor =2$$ $$\boxed{\begin{array}{rl}& 1\\ & 1\\ & 2\end{array}}$$

[2]
最大値のインデックスを初期化し、配列の要素を走査して最大値を探し、最後に末尾の要素と交換する処理を行う。
(1) 最大値のインデックスを初期化する。
(2) ループの初期化と継続条件を指定する。
(3) 現在の最大値よりも大きい要素を見つけた場合の条件を指定する。
(4) 要素の交換処理を完成させる。

$$\boxed{\begin{array}{rl}(1)& \mathrm{imax}=0\\ (2)& \mathrm{i}=1;\mathrm{i}<\mathrm{n}\\ (3)& \mathrm{a}[\mathrm{i}]>\mathrm{a}[\mathrm{imax}]\\ (4)& \mathrm{a}[\mathrm{imax}]=\mathrm{a}[\mathrm{n}-1];\end{array}}$$

[3]
maxswap 関数を用いて選択ソートを実装し、配列を昇順に並べ替える。未ソート部分の最大値を順次後方に移動させる。

$$\boxed{\begin{array}{rl}(1)& \mathrm{i}<\mathrm{n}-1;\mathrm{i}++\\ (2)& \mathrm{a},\mathrm{n}-\mathrm{i}\end{array}}$$

[4]
$\mathbf{a},\mathbf{b}$ のなす角度 $\theta$ は、内積とノルムを用いて以下のように表される。

$$\cos \theta =\frac{\mathbf{a}\cdot \mathbf{b}}{|\mathbf{a}||\mathbf{b}|}⟹\theta =\arccos \left(\frac{\mathbf{a}\cdot \mathbf{b}}{|\mathbf{a}||\mathbf{b}|}\right)$$

(1) 数学関数 sqrt および acos を使用するため、ヘッダファイルをインクルードする。
(2) 累積和を計算するための変数をゼロで初期化する。
(3) 上記の公式に基づく計算式を記述する。

$$\boxed{\begin{array}{rl}(1)& \#include<math.h>\\ (2)& \mathrm{sa}=0.0,\mathrm{sb}=0.0,\mathrm{prod}=0.0\\ (3)& \mathrm{prod}/\mathrm{sqrt}(\mathrm{sa}\ast \mathrm{sb})\text{または}\mathrm{prod}/(\mathrm{sqrt}(\mathrm{sa})\ast \mathrm{sqrt}(\mathrm{sb}))\end{array}}$$

---

本题主要考察C语言的基础语法以及基本的算法实现。第一题涉及数据类型的隐式转换，浮点数赋值给整型变量时会截断小数部分。同时考察了后置自增运算符的特性，表达式先返回原值再进行加一操作。位运算符右移相当于对原数进行除以二的指定次幂并向下取整的操作。第二题和第三题实现了一个经典的变种选择排序，每次在未排序的序列中找到最大值并将其交换到当前未排序部分的末尾，从而实现数组的升序排列。在填写循环条件时需要注意数组下标的边界问题。第四题则考察了空间几何中向量夹角的求解公式，即通过内积除以两个向量的模长乘积来计算夹角的余弦值，最后利用反余弦函数求出角度，同时测试了对C语言标准数学库的调用和变量初始化的重要性。