「５回目中間テスト課題」
プログラムの最初にNの値を #define N 200 として、求める素数の上限Nの値を設定する。 整数n(>1)が素数であるとは、nを2～nの整数で割ったとき割り切れるのがnのみということである。これをそのまま素数の判別に用いることによって、2～200までの整数に含まれる素数を下記の出力例の通りに表示するプログラムを作成せよ。
============ 出力例 （素数は10個ごとに改行すること）====================
========================================
ここで、Nの値をオブジェクト形式マクロで最初に設定するということは、200という値をそこ以外では使用してはならないことを意味する。また、割り切れる数がそれ自身のみという判別は、n=17の場合では
int i, n = 17;
for (i = 2; n % i; i++) ;
if (i == n) printf("%dは素数です。\n", n);
else printf("%dは素数ではありません。\n", n);
のような判別方法を意味している。 より効率的に求めることも可能であるが、この課題ではこの方法でプログラムを作成すること。
＜解答例＞
#include <stdio.h>
#define N 200
int main(void)
{
printf("2～%dまでの素数を順番に並べると以下のようになります。\n", N);
int i, n, sn=0;
for (n=2; n<=N; n++){
for (i=2; n%i; i++) ;
if (n == i){
printf("%3d, ", n);
sn++;
if (!(sn%10)) printf("\n");
}
}
printf("[End]\n");
printf("%d個の素数があります。\n", sn);
return 0;
}
＜採点基準＞
１０点満点から以下の項目に該当する場合減点
（１）コンパイルエラーで実行できない、素数の出力が無いか間違っている：-3点
以降、プログラムが正常に動作するようになるまでの修正１か所につき-2点
0点以下になった場合は0点
（２）変数の初期化の誤り：-2点
for (n = 1; n <= N; n++){
for (i = 2; n % i; i++) ; //n = 1のときうまくいかない。
（３）マクロでNに設定した素数上限値200をNを使わずに200と記述：-2点
（４）出力表示が指定と異なる
（ａ）軽微 ：-1点 複数-2点（コンマ無し、空行・改行がある、素数位置ずれ）
（ｂ）中程度：-2点 （[End]の出力が無い）
（ｃ）重大 ：-3点、複数-5点（素数１０個ごとに改行無し、個数の出力無し。）
（５）int main( ), voidが無い、return(0);が無い：-1点
（６）不要な{ }や( )の使用：-1点
（７）同じ意味・値を持つ変数を複数個作成、不要なマクロを定義：-1点
（８）簡単に表現できるところを複雑に記述、不要な配列の使用：-1点 （素数10個ごとに改行する部分に多い）
（９）インデント
（ａ）スペース1個程度の１か所のずれ、インデント幅が異なる：-1点
（ｂ）ループや条件式の中身が判別しにくいほどのずれ：－２点
（ｃ）上記のようなずれが複数個所：-3
なお、今回は減点対象としませんでしたが不必要な空行は読みにくいプログラムとなるため、次回からは減点対象と致します。今回の課題程度のプログラムでは空行なしで書くことも多いですが、入れるとしてもせいぜい１行の空行を１～３箇所程度です。論理的な区切りに空行を適切に入れると読みやすいプログラムになりますが、必要以上に入れないように注意しましょう。
今回は、テキスト第７章、基本形を学習します。ここでは以下のようなポイントがあります。
（１）基本型（int, double, char など）、型指定子（signed, unsigned）、ビット単位の演算子
（２）16進数 255 => 0xFF, printf(“%X”, 0xFF); 16進数は、0 1 2 3 4 5 6 7 8 9 A B C D E Fで数字を表す。
（３）整数型の最大値 limits.hヘッダーファイルで定義されている。 #define UCHAR_MAX 255U
「１」整数型の範囲を表示してみましょう。（テキストp.177) 以下のプログラムを実行してみてください。
整数型は扱っている数値の正確（厳密）な表現である反面、表現できる数値の上限、下限が存在します。double型（倍精度浮動小数点型）の方がはるかに広い範囲の数値を表現出来ますが、有効桁数が存在します。
/*
整数型の表現範囲を表示する
*/
#include <stdio.h>
#include <limits.h>
int main(void)
{
printf("char : %d～%d\n", CHAR_MIN, CHAR_MAX);
printf("signed char : %d～%d\n", SCHAR_MIN, SCHAR_MAX);
printf("unsigned char : %d～%d\n", 0, UCHAR_MAX);
printf("short : %d～%d\n", SHRT_MIN, SHRT_MAX);
printf("int : %d～%d\n", INT_MIN, INT_MAX);
printf("long : %ld～%ld\n", LONG_MIN, LONG_MAX);
printf("unsigned short: %d～%d\n", 0, USHRT_MAX);
printf("unsigned : %d～%u\n", 0, UINT_MAX);
printf("unsigned long : %ld～%lu\n",0, ULONG_MAX);
return (0);
}
int型は符号付き整数であり、unsigned int (unsignedと省略可)は符号なし整数です。符号付き整数では最上位ビットが1の場合負の数を表します。符号付き整数の出力変換指定は%dであり、これまでprintf関数等で用いてきました。これに対応する符号なし整数の変換指定は%uです。符号付きと符号なし整数では、それぞれ表現できる数値の範囲が異なります。それを超えると正しい計算が出来なくなります。次のプログラムはそれぞれの最大値に１を加えた場合にどのようになるかを確認するプログラムです。
/*
符号付きと符号なし整数型の最大値に１を加えた結果を確認する
*/
#include <stdio.h>
#include <limits.h>
int main(void)
{
printf("整数型の最大値(intとして表示) :%d\n", INT_MAX);
printf("整数型の最大値 + 1(intとして表示) :%d\n", INT_MAX + 1);
printf("整数型の最大値(unsignedとして表示) :%u\n", INT_MAX);
printf("整数型の最大値 + 1(unsignedとして表示) :%u\n", INT_MAX + 1);
printf("符号なし整数型の最大値(intとして表示) :%d\n", UINT_MAX);
printf("符号なし整数型の最大値 + 1(intとして表示) :%d\n", UINT_MAX + 1);
printf("符号なし整数型の最大値(unsignedとして表示) :%u\n", UINT_MAX);
printf("符号なし整数型の最大値 + 1(unsignedとして表示):%u\n", UINT_MAX + 1);
return (0);
}
（４）sizeof演算子 sizeof(型名)＝＞型名のバイト数（charの何倍か）
「２」sizeof演算子は、もう少し複雑なプログラムを作成するようになるとバイナリファイルの読み書きや配列の動的確保に良く使用します。ここでは基本型のサイズを表示してみましょう。（テキストp.180, List7-3改）
/*
型の大きさを表示する
*/
#include <stdio.h>
int main(void)
{
printf("sizeof(char) ＝ %u\n", (unsigned)sizeof(char));
printf("sizeof(short) ＝ %u\n", (unsigned)sizeof(short));
printf("sizeof(int) ＝ %u\n", (unsigned)sizeof(int));
printf("sizeof(long) ＝ %u\n", (unsigned)sizeof(long));
printf("sizeof(float) ＝ %u\n", (unsigned)sizeof(float));
printf("sizeof(double) ＝ %u\n", (unsigned)sizeof(double));
printf("sizeof(long double) ＝ %u\n", (unsigned)sizeof(long double));
return (0);
}
（５）typedef宣言、ある型名（intやunsignedなど）に別の名前を与える。 （例）typedef unsigned size_t;
typedef宣言は、もう少し後に出てくる構造体宣言に簡潔な名前を与えるときに良く使います。sizeof演算子から返される値は、上の例のように定義されたsize_t型です。
演習問題3Bでは、2重forループを用いて九九の表を作成した。ここでは16進数表示によるこれに対応する表（FFの表）を以下の通りに出力するプログラムを作成せよ。ただしプログラム中の整数値は最後のreturn (0);の部分を除いてすべて16進数で記述すること。
（６）整数接尾語 1=> int, 1L=> long, 1u=> unsigned int
（７）整数の２の補数表現＝＞ 1 － 1 = 0 => 00000001 + 11111111 = 100000000
（８）ビット単位のAND, OR, XOR, NOT ＝＞ &, |, ^, ~
（９）ビット単位のシフト演算子 <<, >>
「３」整数の内部のビットパターンを表示してみましょう。
以下の例では、表示したいビットをシフト演算子>>で最下位ビットに移動した後、1とのビット単位のANDを見ることによってそれが１か0かを判断しています。
#include <stdio.h>
int main (void)
{
int i, x;
printf("整数を入力してください："); scanf("%d", &x);
for (i = 8*sizeof(int) - 1; i >= 0; i--){
putchar(((x >> i) & 1U) ? '1' : '0');
if (!(i%8)) printf(" ");
}
printf("\n");
return 0;
}
「４」ビット単位の論理演算子の動作確認（AND, OR, XOR, NOT）（テキストp.189, List7-6）
/*
unsigned型の論理積・論理和・排他的論理和・１の補数を表示
*/
#include <stdio.h>
/*--- 整数x中のセットされたビット数を返す ---*/
int count_bits(unsigned x)
{
int count = 0;
while (x) {
if (x & 1U) count++;
x >>= 1;
}
return (count);
}
/*--- unsigned型のビット数を返す ---*/
int int_bits(void)
{
return (count_bits(~0U));
}
/*--- unsigned型のビット内容を表示 ---*/
void print_bits(unsigned x)
{
int i;
for (i = int_bits() - 1; i >= 0; i--)
putchar(((x >> i) & 1U) ? '1' : '0');
}
int main(void)
{
unsigned na, nb;
puts("二つの非負の整数を入力してください。");
printf("整数Ａ："); scanf("%u", &na);
printf("整数Ｂ："); scanf("%u", &nb);
printf("\nＡ<<2 ＝ "); print_bits(na<<2);
printf("\nＢ>>2 ＝ "); print_bits(nb>>2);
printf("\nＡ & Ｂ ＝ "); print_bits(na & nb); /* 論理積 */
printf("\nＡ | Ｂ ＝ "); print_bits(na | nb); /* 論理和 */
printf("\nＡ ^ Ｂ ＝ "); print_bits(na ^ nb); /* 排他的論理和 */
printf("\n~Ａ ＝ "); print_bits(~na); /* １の補数 */
printf("\n~Ｂ ＝ "); print_bits(~nb); /* １の補数 */
putchar('\n');
return (0);
}
ビット単位の演算は、外部機器を制御するプログラムを書くときなどハードウェアに関係する部分で良く使います。しっかり理解しましょう。
（１０）浮動小数点
float 32ビット 符号１、指数部７（-37～38）、小数部24（6桁）
double 64ビット 符号１、指数部10（-307～308）、小数部53（15桁）
（１１）浮動小数点接尾語 1.0 => double, 1.0F => float, 1.0L => long double
（１２）数学関数 #include <math.h> でmath.hファイルをインクルードしておくこと。
sqrt(double x), sin(double x), cos(double x), tan(double x), atan(double x), exp(double x), log(double x), pow(double x, double y) 全て返り値はdouble型
ビット数とそのビット数で表される符号なし整数値を引数とし、受け取った値をビット反転した結果を符号なし整数値として返す次の関数bit_revを以下の(1)～(3)のように作成する。
unsigned int bit_rev(unsigned int m, int nbit);
m: ビット数nbitで表される符号なし整数(0 <= m < 2^nbit の範囲の数と仮定して良い)
nbit: mに使用されているビット数
返り値：mをビット反転させた符号なし整数値。
（例）nbit=3, m=4ならば、4のビットパターン100を反転させた結果は001となるので返り値は1である。
関数の作成方法：
(1) unsigned int mrev = 0; としてmrevをビット反転させた値を格納する変数とする。
(2)引数mのビット位置をi（末尾をi=0とする）として、i=0からnbit-1まで次の(a), (b)の処理を行う。
(a) 末尾のビットを m % 2で判別して1ならば mrevに 1 << (nbit -i -1)を加える。
(b) m の値を m >> 1 とする。
(3) 返却値としてmrevの値を返す。
この関数bit_revを用い、#define M 3 と指定したMに対して 0 <= m < (1 << M))の範囲の整数 mに対してビット反転させた値を以下の表示例の通りに出力するプログラムを作成せよ（ (1 << M)の値はMが3のときは8である）。
==== 出力例 =====
整数mをビット反転した値を表示 m: Bit Reverse --------------------------- 0: 0 1: 4 2: 2 3: 6 4: 1 5: 5 6: 3 7: 7 ---------------------------
演習課題6Bの結果は以下のような表に示すことができる。ここでは3ビットで表される数の個数をN=8としている。前の演習課題6Bではビットを直接扱ってビットを反転させていたが、この図では別の計算方法を右側に表示している。
以下の指示に従ってこの図に示した方法でビット反転させた値を計算し、演習課題6Bと同じ出力結果が得られるプログラムを作成せよ。
（１）Nの値はオブジェクト形式マクロで#define N 8 と設定すること。
（２）反転させるビット数は次の式で計算すること。
int nbit = (int)(log(N)/log(2.0) + 0.5);
（３）ビット反転結果を格納する配列を int k[N]; とする。図で説明に用いた変数 int i, j; を宣言し、k[j]を以下のコードで計算する。
k[0] = 0; //どのようなビット数でも0の反転結果は0
int js = 1; // i=1のときのjのforループ開始点, js = 2^(i-1)
int je = js * 2; // i=1のときのjのforループ終了点+1, je = 2^i
for (i = 1; i <= nbit; i++, js = je, je *= 2){
for (j = js; j < je; j++){
[図で示したk[j]を求める式]
}
}
（４）出力はNが8のとき演習課題6Bと同じになること。ただしNの値を16, 32と設定しても正常に動作するように作成すること。
なお、ここで使用しているビット反転アルゴリズムは 離散フーリエ変換を計算するFFT(Fast Fourier Transform)アルゴリズムにおいて重要な役割を担っている。