使われ方はこんな感じ。これで1番目から100番目までの数列の要素が出力される。mainの中で使われているi_to_nという関数をどのように作るか。
int main( void )
{
for(i=0; i<100; i++){
printf("%d %d\n" ,i ,i_to_n(i));
}
return 0;
}
まずはホワイトボードに色々書き殴ってみる。
n 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ... 2の倍数 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ... 3の倍数 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, ... i 0, 1, 2, 3, 4, ... i%2 0, 1, 0, 1, 0, ... i/2 0, 0, 1, 1, 2, ...
つまり、2の倍数かつ3の倍数である6の倍数ごとに周期性がある。ある6の倍数から次の6の倍数までの中には必ず2つの、2の倍数でもなく3の倍数でもない数が存在する。6の倍数で部分数列をつくると、各々の部分数列に含まれる最初の各要素は、部分数列について6だけ差がある。このことは2番目の要素についても同じ。各部分数列の番号付けはi/2で出来る。部分数列内の要素の番号付けはi%2で出来る。ということでこんな感じ。
部分行列の1番目の数の数列の一般項 n = 1 + 6 * (i / 2 の商) 部分行列の2番目の数の数列の一般項 n = 5 + 6 * (i / 2 の商)
当然ながら、int型の演算における(i/2)は「iを2で割ったときの商」というれっきとした「意味」があるので、6*i/2を3*iのようにまとめてはいけない。ということで下のようにかける。
int i_to_n(int i)
{
int n;
if( 0 == (i % 2) ){
n = 1 + 6 * (i / 2);
}else{
n = 5 + 6 * (i / 2);
}
return n;
}
入出力チェックが行われていないので軽く脳内チェック。nはint型なので、iが大きいと数学的にはおかしな結果が得られるはず。例えば、(INT_MAX)/3の辺りで。テストコードを書いてみる。
void check(void)
{
int i = 0;
int i_sta = INT_MAX/3 - 10;
int i_end = i_sta + 20;
for(i=i_sta;i<i_end;i++){
printf("%10d %10d %10u\n",i, i_to_n(i), i_to_n(i));
}
return;
}
走らせると明らかにおかしな出力である。出力結果が採点されるので、これでは困る。
715827872 2147483617 2147483617 715827873 2147483621 2147483621 715827874 2147483623 2147483623 715827875 2147483627 2147483627 715827876 2147483629 2147483629 715827877 2147483633 2147483633 715827878 2147483635 2147483635 715827879 2147483639 2147483639 715827880 2147483641 2147483641 715827881 2147483645 2147483645 715827882 2147483647 2147483647 715827883 -2147483645 2147483651 715827884 -2147483643 2147483653 715827885 -2147483639 2147483657 715827886 -2147483637 2147483659 715827887 -2147483633 2147483663 715827888 -2147483631 2147483665 715827889 -2147483627 2147483669 715827890 -2147483625 2147483671 715827891 -2147483621 2147483675
注目すべき点はprintf関数でフォーマット指定する際にunsigned int型とすると、上手くいくという点である。少なくとも僕がテストコードを走らせている処理系では、printf文がint型とunsigned int型を処理する場合の違いは最上位ビットを負数を表現するフラグと考えるか否かだけの違いなので、こんな感じの事が起きる。とりあえずnが負数ならperror();exit();するという手もあるが、それだと十分にビットを使えていない(半分くらいのビットが無駄になる)し出力チェックは入力チェックに比べてコストがかかるので面白くない。このままの状態で出力だけunsigned intを使うのもいいが、それだと論理的でない機がする。まずはunsigned int型にして、論理的に正しく計算できる範囲を広げよう。
unsigned int i_to_n(unsigned int i)
{
unsigned int n;
if( 0 == (i % 2) ){
n = 1 + 3 * i;
} else {
n = 5 + 3 * i;
}
return n;
}
void check(void)
{
unsigned int i = 0;
unsigned int i_sta = UINT_MAX/3 - 10;
unsigned int i_end = i_sta + 20;
for(i=i_sta;i<i_end;i++){
printf("%10d %10u %10d %10u\n",i,i, i_to_n(i), i_to_n(i));
}
return;
}
で、出力結果が下のような感じ。
1431655755 1431655755 -29 4294967267 1431655756 1431655756 -27 4294967269 1431655757 1431655757 -23 4294967273 1431655758 1431655758 -21 4294967275 1431655759 1431655759 -17 4294967279 1431655760 1431655760 -15 4294967281 1431655761 1431655761 -11 4294967285 1431655762 1431655762 -9 4294967287 1431655763 1431655763 -5 4294967291 1431655764 1431655764 -3 4294967293 1431655765 1431655765 1 1 1431655766 1431655766 3 3 1431655767 1431655767 7 7 1431655768 1431655768 9 9 1431655769 1431655769 13 13 1431655770 1431655770 15 15 1431655771 1431655771 19 19 1431655772 1431655772 21 21 1431655773 1431655773 25 25 1431655774 1431655774 27 27
ここまでしてから、入力チェックを行って、エラー終了させる。どこにエラーの原因が潜んでいるか微妙なので、計算のたびにエラーチェックをさせる。
unsigned int uint_dvi(unsigned int a, unsigned int b)
{
unsigned int a_dvi_b = a;
if (a <= (UINT_MAX * b)) {
a_dvi_b /= b;
} else {
errno = ERANGE;
fprintf(stderr,"%u / %u",a,b);
perror("#");
exit(EXIT_FAILURE);
}
return a_dvi_b;
}
unsigned int uint_mul(unsigned int a, unsigned int b)
{
unsigned int a_mul_b = a;
if (a <= (UINT_MAX / b)) {
a_mul_b *= b;
} else {
errno = ERANGE;
fprintf(stderr,"%u * %u",a,b);
perror("#");
exit(EXIT_FAILURE);
}
return a_mul_b;
}
unsigned int uint_add(unsigned int a, unsigned int b)
{
unsigned int a_plus_b = a;
if (a <= (UINT_MAX - b)) {
a_plus_b += b;
} else {
errno = ERANGE;
fprintf(stderr,"%u + %u",a,b);
perror("#");
exit(EXIT_FAILURE);
}
return a_plus_b;
}
unsigned int i_to_n(unsigned int i)
{
unsigned int n = i;
//n /= 2;
n = uint_dvi(n, 2);
//n *= 6;
n = uint_mul(n, 6);
if (0 == (i % 2)) {
//n += 1;
n = uint_add(n, 1);
} else {
//n += 5;
n = uint_add(n, 5);
}
return n;
}
で、こんな感じ。しっかりと落ちてくれている。まぁこれで、処理系依存がないだろうと思う。採点する人間の処理系を公開してほしいものだ。おかげで色々と考えさせられるが。
1431655755 4294967267 1431655756 4294967269 1431655757 4294967273 1431655758 4294967275 1431655759 4294967279 1431655760 4294967281 1431655761 4294967285 1431655762 4294967287 1431655763 4294967291 1431655764 4294967293 4294967292 + 5#: Numerical result out of range 1431655765