両替問題を解いてみる。

両替問題を解いてみました。 やっていることは1000円を日本の硬貨(500円,100円,50円,10円,5円,1円)の6種類で払った場合の支払うすべての組み合わせの数を計算します。 アルゴリズムとしては高い硬貨から任意の数とっていくことを1000円になるまで再帰的に繰り返しています。 結果としては24万8908通りありました。手で計算するのはやり方が分かりませんが大変そうですね。あとなぜかC言語で書きましたが残念ながら完全に忘れていることが分かりました。

	#include<stdio.h>
	int coin[6]={500,100,50,10,5,1};
	long cnt = 0;
	void func(int N, int c){
	if(c == (sizeof(coin)/sizeof(int) - 1)){
	cnt++;
	}else{
	for(int i = 0; i <= N/coin[c]; i++){
	func(N-coin[c]*i,c+1);
	}
	}
	}
	int main(){
	func(1000,0);
	printf("%ld\n",cnt);
	}

view raw exchange.c hosted with ❤ by GitHub