93
HDU1284-錢幣兌換問題
錢幣兌換問題
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5258 Accepted Submission(s): 2989
Problem Description
在一個國家僅有1分，2分，3分硬幣，將錢N兌換成硬幣有很多種兌法。請你編程序計算出共有多少種兌法。
Input
每行隻有一個正整數N，N小於32768。
Output
對應每個輸入，輸出兌換方法數。
Sample Input
2934
12553
Sample Output
718831
13137761
Author
SmallBeer(CML)
Source
//數學問題
/*思路：n分錢分成零錢符合x1+2*x2+3*x3的公式，隨著x1,x2,x3取不同值就有不同的分法。
那麼，先確定x3的值就可以確定x1與x2的值，確定x2的值那x1的值一定是定值，不需要求。
所以，先定x3的值，假設x3=k，那麼x1+2*x2=n-3*k，重點來了，此時隻要知道x2的取值範圍就可以
得到當x3等於k時有多少種分法了。x2的範圍並不難求，假設沒有x1，那麼2*x2<=n-3*k，則0<=x2<=(n-3*k)/2，
即x2一共有(n-3*k)/2+1種可能，也就是當k3取某個值時一共有(n-3*k)/2+1種分法。
所以，將k3的所有值(k3*3<=n)取完，每取一次值就加一次(n-3*k)/2+1，最終得到分n分錢所有的可能性！*/
AC代碼：
#include<stdio.h>
#include<string.h>
int main()
{
int i,n,sum;
while(scanf("%d",&n)!=EOF)
{
sum=0;
for(i=0;i*3<=n;i++)
{
sum+=(n-i*3)/2+1;
}
printf("%d\n",sum);
}
return 0;
}
最後更新：2017-04-03 05:39:04