用1元，2元，5元，10元，20元和50元的纸币组成100元，共有多少种情况。
用1元，2元，5元，10元，20元和50元的纸币组成100元，共有多少种情况。
要求写出除了多重循环方案之外的另一种程序代码，要求输出总方案数和每种方案中各纸币的个数。
这个是原题，当然，如果你有循环的实现也可以贴上来。
[解决办法]
算起来比较复杂,如果只是用程序输出的话,有比较傻的办法,
全排列c(3,1) * c(6,1) * c(11,1) * c(21,1) * c(51,1)
分别对应50\20\10\5\2元的取法,然后计算每种取法的金额,输出金额<= 100的
也就是200000次左右的循环!
[解决办法]
整数分解问题；
总方案数为多项式：(1+x+x^2+x^3+...+x^100)
*(1+x^2+x^4+...+x^100)
*(1+x^5+x^10+...+x^100)
*(1+x^10+x^20+...+x^100)
*(1+x^20+x^40+...+x^100)
*(1+x^50+x^100)
的x^100项的系数；
既然还需求“每种方案中各纸币的个数”
多重循环就是效率最高的啦；
不能用循环，就把循环改成递归呗，不过只是换汤不换药；
[解决办法]
f(100)
50,50
f(50),50
f(50)
10,10,10,10,10
f(10),10,10,10,10
...
f(10),f(10),f(10),f(10),f(10)
f(10)
5,5
f(5),5
f(5),f(5)
f(5)
2,2,1
f(2),2,1
f(2),f(2),1
f(2)
1,1
如果1也是可分的,则
f(5)
2,2,1
f(2),2,1
f(2),f(2),1
f(2),f(2),f(1).因为1不可分,所以只是举例说明思想.
[解决办法]
刚研究过这种题目，可以用动态规划的思想来解，也可以用广度遍历
这里我就说一下动态规划的思想
假设f[n,j]表示价值为n的面值中含有第j种面值的所有情况的总合
f[n,j] = f[n,j-1] + f[n-v[j],j-1] + f[n-2*v[j],j-1] + f[n-3*v[j],j-1] + ....
其中f[n,j-1]表示没有第j种纸币的情况的总合，f[n-v[j],j-1]表示只有一个第j种纸币的情况总和
那么
f[n-v[j],j-1] = f[n-v[j],j-1] + f[n-2*v[j],j-1] + f[n-3*v[j],j-1] + ....
代入上式，就得到一个地推公式
f[n,j] = f[n,j-1] + f[n-v[j],j-1] (n>=1&&j>=2)
===========================================================
double v[N+1] = {0,1,2,5,10,20};
int getf(int n,int j)
{
if(n>=1 && j>=2)
return getf(n,j-1) + getf(n-v[j],j);
else
return 1;
}
int main(int argc, char* argv[])
{
int i = getf(100,5);
return 0;
}
a = 4236
[解决办法]
#define M 7
int data[M] = {0}; // set tags
int money_style[7] = {1,2,5,10,20,50,100};
int num = 0;
void initialization(int n)
{
for(int i = 0; i < n; i++) //set position as tag 1
{
data[i] = 1;
}
for(i = n; i < M; i++) //null position as tag 0
{
data[i] = 0;
}
}
void getData()
{
int sum = 0;
cout <<left;
cout<<setw(10)<<++num;
for(int i = 0; i < M; i++)
{
if (data[i]==1) //if has tag == 1 get position
{
//cout<<i+1;
cout <<left;
cout<<setw(6)<<money_style[i];
sum+= money_style[i];
}
}
cout <<right;
cout<<setw(15);
cout <<"" <<sum<<"元"<<endl;
}
void reSet(int before)
{
int count = 0;
for(int i = 0; i < before; i++)//get number of tag 1
{
if(data[i]==1)
count++;
}
for(int j = 0; j < count; j++) //set tag 1 from start position data[0]
{
data[j] = 1;
}
for( ; j < before; j++) //others set tag 0
{
data[j] = 0;
}
}
void m_select_n()
{
int i = 0;
while(1)
{
int bfind = false;
if(data[i]== 1 && data[i+1] == 0) //get [][][1][0][][][][]
{
data[i] = 0;
data[i+1] =1; //set [1][0]-> [0][1]
bfind = true;
reSet(i); //reset data[] from i position
getData();
i = -1; //start from i= 0 because i++ =0
}
i++; //i++ if i =-1 then start form begin i =0
if(i == M-1) //if i(0,1,2,3,4,5,6) = 6 ,then finished
break;
}
}
int main()
{
for(int i = 1; i < M+1; i++) //from 1 to 7
{
initialization(i);
getData();
m_select_n();
}
return 0;
}
我的博客中有具体的算法解释
http://umleirk.blog.sohu.com/
[解决办法]
运行结果：
1 1 1元
2 2 2元
3 5 5元
4 10 10元
5 20 20元
6 50 50元
7 100 100元
8 1 2 3元
9 1 5 6元
10 2 5 7元
11 1 10 11元
12 2 10 12元
13 5 10 15元
……
123 1 2 5 20 50 100 178元
124 1 2 10 20 50 100 183元
125 1 5 10 20 50 100 186元
126 2 5 10 20 50 100 187元
127 1 2 5 10 20 50 100 188元
[解决办法]
不好意思，看错题目了！
[解决办法]
整数划分问题，动态规划解决，
[解决办法]
背包问题！我喜欢- -b
#include <iostream>using namespace std;#define N 6int w[N];int number_used[N];//bool is_used[N];void init(){ w[0] = 1; w[1] = 2; w[2] = 5; w[3] = 10; w[4] = 20; w[5] = 50; for (int i = 0; i < N; i++) { number_used[i] = 0; }}int test(int start_index, int left_weight){ int ret = 1; if (left_weight == 0) { for (int i = 0; i < N; i++) { if (number_used[i] > 0) cout << w[i] << "元: "<< number_used[i] <<"张 "; } cout << endl; return 1; } for (int i = start_index; i < N; i++) { if (left_weight >= w[i]) { number_used[i]++; ret += test(i, left_weight - w[i]); number_used[i]--; } } return ret;}int main(){ init(); cout << test(0, 100) <<endl; system("pause"); return 0;}
[解决办法]
递归 。
public class STest { static int[] values={1,2,5,10,20,50}; public static void main(String[] args) { split(100,0,""); } public static void split(int n,int base,String result){ if(n<0) return; if(n==0){ System.out.println(result); return; } for(int i=base;i<values.length;i++){ split(n-values[i],i,result+values[i]+"|"); } }}
[解决办法]
整数拆分,建议看看组合数学,顺便看看母函数以及ferrers图的处理,相信这个问题就会变的很简单了
[解决办法]
跟做天学的百钱买百鸡差不多的问题,用穷举法.
[解决办法]
int main() { int i50, i20, i10, i5, i2, i1; int count = 0; for (i50 = 0; i50 <= 2; i50++) for (i20 = 0; i20 <= 5; i20++) for (i10 = 0; i10 <= 10; i10++) for (i5 = 0; i5 <= 20; i5++) for (i2 = 0; i2 <= 50; i2++) for (i1 = 0; i1 <= 4; i1++) { if (i50 * 50 + i20*20 + i10 * 10 + i5 * 5 + i2 * 2 + i1 * 1 == 100) { count++; printf("$50$:%d, $20$:%d, $10$:%d, $5$:%d, $2$:%d, $1$:%d\n", i50, i20, i10, i5, i2, i1); } } printf("%d!!!!!!!!!\n",count); return 0; }
[解决办法]
我的输出是784，为什么和楼上几位不一样。我的方法虽然效率不高，但应该没有漏掉和重复的，莫非楼上几位的方法有重复分组？
[解决办法]
昨天考淘宝 就是这题
这是我当时的程序实现（共4562组）
#include <iostream>using namespace std;const int N = 100;static int count0 = 0;int b[] = {50,20,10,5,2,1};void p(int *a, int n, int j, int currentIndex){ for(int i=currentIndex;i<6;i++) { if(n-b[i] == 0) { count0++; a[j] = b[i]; cout<<"第"<<count0<<"组结果为："<<endl; for(int k=0;k<=j;k++) printf("%d\t",a[k]); printf("\n"); } else if(n-b[i] > 0) { a[j] = b[i]; p(a,n-b[i],j+1,i); } }}int main(){ int a[N] ={0}; a[0] = b[0]; p(a,N,0,0); return 0;}
[解决办法]
#include <iostream>using namespace std;const int v[6] = {1,2,5,10,20,50};int f(int n, int w){ if(n<0) return 0; if(n==0) return 1; if(w<0) return 0; return f(n, w-1) + f(n-v[w], w);}void main(){ cout<<f(100,5)<<endl; system("pause");}
[解决办法]
跟正一下5楼
f[n-v[j],j] = f[n-v[j],j-1] + f[n-2*v[j],j-1] + f[n-3*v[j],j-1] + ....
代入上式，就得到一个地推公式
f[n,j] = f[n,j-1] + f[n-v[j],j] (n>=1&&j>=2)
[解决办法]
顶了！
[解决办法]
用循环逐一去算?
[解决办法]
确实比较经典啊，估计要用回溯来做
[解决办法]
学习了
[解决办法]
ding
[解决办法]
厉害啊
[解决办法]
数字拆分么
[解决办法]
学习学习。。。
[解决办法]
用回溯估计是比较普通的方法
[解决办法]
算算
[解决办法]
...........
[解决办法]
sdrwervwerwerwevr
[解决办法]
public static void Main()
{
int count = 0;
//1元组成的情况，最多有100种
for (int a = 0; a <= 100; a++)
{
//2元的情况，最多有50种可能
for (int b = 0; b <= 50; b++)
{
for (int c = 0; c <= 20; c++)
{
//10元的情况，最多10种可能
for (int d = 0; d <= 10; d++)
{
//20元的情况，最多5种可能
for (int e = 0; e <= 5; e++)
{
//50元的情况，最多2种可能
for (int f = 0; f <= 2; f++)
{
if ((1 * a + 2 * b + 5 * c + 10 * d + 20 * e + 50 * f)
== 100)
{
count++;
Console.WriteLine("1*{0}+2*{1}+5*{2}+10*{3}+20*{4}+50*{5}=100",
a, b, c, d, e, f);
}
}
}
}
}
}
}
Console.WriteLine("共有{0}种可能情况", count);
}
这个解法相信大家都会，欢迎赐教
[解决办法]
name,名称,0,;beproject,所属项目,0,;type,类型,1,0:小-1:中-2:大;complete,完成,2,;remark,备注,3,;listbox,设备表,4,
7，可以实时上传文件到后台服务器，实时下载后台服务器的文件和实时更新PDA上客户端的系统！
8，可以实时采集和传输图像信息！
跟据您的需要，还可以增加其它功能！
QQ:546046182
[解决办法]
学习了，mark
[解决办法]
看贴回帖好习惯。
[解决办法]
到底哪个效率高些呢，看起来都高不了多少
[解决办法]
[解决办法]
學習了
[解决办法]
我得到的答案是4111
package question.myanswer;
public class MoneyProblem {
public static void main(String[] args) {
int a, b, c, d, e, sign = 1;
for(a = 0; a <= 100; a++){
for(b = 0; b <= 50; b++){
for(c = 0; c <= 20; c++){
for(d = 0; d <= 10; d++){
for(e = 0; e <= 5; e++){
if(1*a + 2*b + 5*c + 10*d + 20*e == 100){
System.out.print(sign + ":" + a + "\t" + b + "\t" + c + "\t" + d + "\t" + e + "\t");
System.out.println("");
sign++;
}
}
}
}
}
}
}
}
[解决办法]
private void simpleButton3_Click(object sender, EventArgs e) { int[] l = new int[] { 100, 50, 20, 10, 5, 1 }; MessageBox.Show( go(l, 0, 100, new int[l.Length]).ToString()); } int go(int[] il, int index, int I, int[] ilUse) { int result = 0; for (int i = 0; true; i++) { if (I > 0) { if (il.Length > index + 1) { result += go(il, index + 1, I, ilUse); } } else if (I == 0) { print(il, ilUse); return ++result; } else { return result; } I = I - il[index]; for (int j = index + 1; j < ilUse.Length; j++) { ilUse[j] = 0; } ilUse[index] = i + 1; } } void print(int[] il, int[] ilUse) { StringBuilder sb = new StringBuilder(); for(int i = 0;i< il.Length ;i++) { if (ilUse[i] > 0) sb.Append(string.Format("{0}元用了{1}张; ", il[i], ilUse[i])); } Console.WriteLine(sb); }
[解决办法]
mark
[解决办法]
学习
[解决办法]
哇学习学习
[解决办法]
计算次数越少的方法应该是越好的方法。
一，普通的循环。
int nCount = 0,nComCount = 0; for (int a = 0;a<= 100;a++) { for (int b = 0;b<= 50 ;b++) { for (int c = 0; c <= 20;c++) { for (int d = 0;d<= 10;d++) { for (int e = 0;e <= 5 ;e++) { for (int f= 0;f<=2;f++) { nComCount++; if ((a*1+b*2+c*5+d*10+e*20+f*50) == 100) { nCount++; printf("%d+%d+%d+%d+%d+%d = 100\n",a,b,c,d,e,f); } } } } } } } printf(" count:%d\n nComCount:%d\n",nCount,nComCount); system("pause");
[解决办法]
二，优化的循环。
int nCount = 0,nComCount = 0; for (int a = 0;a<= 100;a++) { for (int b = 0;b<= (100-a*1)/2 ;b++) { for (int c = 0; c <= (100-a*1 - b*2)/5;c++) { for (int d = 0;d<= (100-a*1 - b*2 -c*5 )/10;d++) { for (int e = 0;e <= (100-a*1 - b*2 -c*5 - d*10)/20 ;e++) { for (int f= 0;f<=(100-a*1 - b*2 -c*5 - d*10 - e*20)/50;f++) { nComCount++; if ((a*1+b*2+c*5+d*10+e*20+f*50) == 100) { nCount++; printf("%d+%d+%d+%d+%d+%d = 100\n",a,b,c,d,e,f); } } } } } } } printf(" count:%d\n nComCount:%d\n",nCount,nComCount); system("pause");
------解决方案--------------------
用背包算法也能实现吧
[解决办法]
91 92 LOU