08/08/27 19:16:45
次のような非常に制限の強いプログラム言語X_1を考える。
1.使用できるデータ型（変数、定数とも）はC言語で言うところのunsigned charのみである。
2.使用できる演算は代入、足し算、引き算、論理演算(AND,OR,NOT,XOR,右シフト、左シフト)のみである。
3.if,while,goto,関数呼び出し等の制御構造は一切なし。プログラムは上から下へ順番に実行されるのみである。
4.unsigned char型の変数を使うことが出来る。個数に制限はない。
5.一ステップで代入一回、演算一回行うことが出来る。つまり１ステップは以下のどれか。
a=b;
a=~b;
a=b+c;
a=b-c;
a=b&c;
a=b|c;
a=b^c;
a=b<<c;
a=b>>c;
(※単項の-は禁止）
6.プログラムの終わりに次のような値を返す文を入れる。
return a;
この値をプログラムの値と呼ぶ。
7.プログラム中で使用できる定数は0x01のみである。
問題1
プログラム言語Pにおいてプログラムの値がaになるもので
最小ステップのプログラムを、Pにおけるaを返すエレガントなプログラムと呼ぶ。
0～255についてそれぞれその値を返すX_1におけるエレガントなプログラムを一つ挙げよ。
問題2
プログラム言語X_1に対してプログラム中で使用できる定数を0x01では無く、他の値aに変えたものをプログラム言語X_aと呼ぶ。
また、エレガントなプログラムのステップ数が最も大きくなるような値をそのプログラム言語の最悪の値と呼ぶ。
プログラム言語X_0～X_255の内、最悪の値に対するステップ数が最も小さくなるプログラム言語はどれか。