Computer Transformation(1)

• テストコード

短いコードを書くためには、入念に下調べをしておく必要がある。焦ってはいけない。
入力値nの値が1増えるごとに文字列は2倍になっていくので、とりあえずはn=1〜15あたりで出力が出来る程度のコードを書いてみよう。問題の記述通り、1と0からなる文字列を生成し、0のペアを数え上げる単純なものだ。下調べなので素早く仕上げておく。

#include<stdio.h>

char v[16][1<<16];
int i,j,k;
int ans;

main()
{
  v[0][0]='1';

  for(i=1;i<16;++i)
  {
    for(ans=j=k=0;v[i-1][j]!=NULL;++j)
    {
      switch(v[i-1][j])
      {
        case '0':
          v[i][k++]='0', v[i][k++]='1';
          break;
        case '1':
          v[i][k++]='1', v[i][k++]='0';
          break;
      }
    }

    for(j=1;j<k;++j)
      if(v[i][j-1]=='0'&&v[i][j]=='0')++ans;

//    printf("%s\n%d step(s): %d\n\n",v[i],i,ans);
    printf("n=%2d: %4d\n",i,ans);
  }
}

こいつを実行すると、

n= 1:    0
n= 2:    1
n= 3:    1
n= 4:    3
n= 5:    5
n= 6:   11
n= 7:   21
n= 8:   43
n= 9:   85
n=10:  171
n=11:  341
n=12:  683
n=13: 1365
n=14: 2731
n=15: 5461

この程度値がわかっていれば、規則性がつかみやすい。ここからまず、漸化式を作ってみることにしよう。