読者です 読者をやめる 読者になる 読者になる

ピアノ問題の一般解(数学ガール: 乱択アルゴリズム)

本の中では(a=8, b=4)の場合だけ検算していますが、それ以外の場合についても確かめるためのプログラムです。"./a.out a b"で実行すると場合の数を返します(a,bは書籍上で定義されているものと同じです)。

ソースコード

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
int* sound(int size) {
int* sounds = malloc(size* sizeof(int));  
int i;
  for(i = 0; i < size; i++)
    sounds[i] = 1;
  return sounds;
}
void sound_step(int* sounds, int size) {
  sounds[0] = sounds[1];
int i;
  for(i = 1; i < size; i++)
    sounds[i] = sounds[i-1] + sounds[i+1];
}
int piano_count(int a, int b) {
int* snds = sound(a);
int i;
  for(i = 0; i < b; i++)
    sound_step(snds, a-i-1);
int value = snds[a-b-1];
  free(snds);
  return value;
}
int str_to_int(char* str) {
int n = 0;
  while(*str != 0) {
    n = n * 10 + (*str++ - '0');
  }
  return n;
}
void test(void);
int main(int argc, char* argv[]) {
  if(argc == 2 && !strcmp("test", argv[1])) {
    test();
    return 0;
  }
  if(argc != 3) {
    fprintf(stderr, "usage:%s a b\n", argv[0]);
    return 1;
  }
  int a = str_to_int(argv[1]);
  int b = str_to_int(argv[2]);
  assert(a > b);
  printf("%d通り\n", piano_count(a, b));
  return 0;
}

void test_functions(void) {
int* snds = sound(8);
  sound_step(snds, 7);
  assert(7 == snds[6]);
  sound_step(snds, 6);
  assert(27 == snds[5]);
  free(snds);
}
void test_piano_count(void) {
int count = piano_count(8, 4);
  assert(165 == count);
}
void test(void) {
  test_functions();
  test_piano_count();
}