c語言趣題之“找零錢的方法數量 ”

/*

Name:

Copyright:

Author:

Date: 31-12-14 16:51

Description:

找零錢的方法數量

描述

我們知道人民幣有1、2、5、10、20、50、100這幾種面值。

現在給你n(1≤n≤250)元，讓你計算換成用上面這些面額表示且總數不超過100張，共有幾種。

比如4元，能用4張1元、2張1元和1張2元、2張2元，三種表示方法。

輸入

輸入有多組，每組一行，為一個整合n。

輸入以0結束。

輸出

輸出該面額有幾種表示方法。

樣例輸入

1

4

0

樣例輸出

1

3

*/

#include

#include

#include

#define MAX 7

int A[MAX] = {1, 2, 5, 10, 20, 50, 100};

int count = 0;

void NumChange_1(int n, int top, int s);//回溯法

int NumChange_2(int n); //動態規劃法1

int NumChange_3(int n); //動態規劃法2

int main()

{

int n;

scanf("%d", &n);

while (n != 0)

{

count = 0;

NumChange_1(n, 6, 0);

printf("%d\n", count);

printf("%d\n", NumChange_2(n));

printf("%d\n", NumChange_3(n));

scanf("%d", &n);

}

return 0;

}

void NumChange_1(int n, int top, int s)

{

int i;

if (n == 0)

{

count++;

return ;

}

if (top < 0)

return ;

NumChange_1(n, top-1, s); //先不用A[top]這種貨幣看看

for (i=A[top]; i<=n; i+=A[top])

{

if (s == 100)//總數不超過100張

return ;

NumChange_1(n-i, top-1, ++s);

}

}

int NumChange_2(int n) //動態規劃法1

{

int f[101][251] = {1};//f[m][n]的含義為用m張鈔票構成的金額為n的組合數量

int i, j, k, min, max;

for (i=0; i

{

for (j=1; j<=100; j++)//鈔票張數

{

min = (j > A[i]) ? j : A[i]; //為避免無效運算，給k值規定一個上限和下限

max = (n <= j * A[i]) ? n : j * A[i];

for (k=min; k<=max; k++)//金額總數

{

f[j][k] += f[j-1][k-A[i]];//該組合中含有一張面值為A[i]的鈔票

}

}

}

for(k = 0, i = 1; i <= 100; k += f[i++][n]);

return k;

}

int NumChange_3(int n) //動態規劃法2

{

int f[256][101] = {1};//f[n][m]的含義為用m張鈔票構成的金額為n的組合數量

int i, j, k, max;

for (i=0; i

{

for (k=A[i]; k<=n; k++)//金額總數

{

max = (k < 100) ? k : 100;

for (j=1; j<=max; j++)//鈔票張數

f[k][j] += f[k-A[i]][j-1];//該組合中含有一張面值為A[i]的鈔票

}

}

k = 0;

for(i=1; i<=100; i++)

k += f[n][i];

return k;

}

總結

以上是生活随笔為你收集整理的c语言自动贩卖机找钱,c语言趣题之“找钱的方法数量 ”的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。