ピアノ問題の一般解(数学ガール: 乱択アルゴリズム)
本の中では(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(); }