C++百钱百鸡问题的解决方法

应该都看过这个题目吧，呵呵，中国古老的问题，原题是“公鸡每只5元，母鸡每只3元，小鸡三只1元，用100元钱买100只鸡，求公鸡，母鸡，小鸡的只数”。

这类问题呢，一般都是用穷举法，俗话说就是套，看那个行，就是哪个，计算机套起来是很容易的吗，有个循环吗，呵呵，我们又在偷懒了。这里我们把100元买100只改成n元买n只。

源代码如下：

#include<stdio.h>
voidchicken_question(intchicken_num,int*k,intg[],intm[],intx[])
...{
　　inta,b,c,t;
　　t=0;
　　for(a=0;a<=chicken_num;a++)
　　　　for(b=0;b<=chicken_num;b++)
　　　　　　for(c=0;c<=chicken_num;c++)
　　　　　　　　if((a+b+c)==chicken_num&&(5*a+3*b+c/3==chicken_num)&&(c%3==0))
　　　　　　　　...{
　　　　　　　　　　g[t]=a;
　　　　　　　　　　m[t]=b;
　　　　　　　　　　x[t]=c;
　　　　　　　　　　t++;
　　　　　　　　}
　　*k=t;
}
main()
...{
　　intn;
　　intgongji[50],muji[50],xiaoji[50],num=0;
　　inti,*p_num=&num;
　　printf("公鸡5元每只，母鸡3元每只，小鸡3只1元");
　　printf("n元买n只鸡,请输入n的值：");
　　scanf("%d",&n);
　　chicken_question(n,p_num,gongji,muji,xiaoji);
　　for(i=0;i<num;i++)
　　...{
　　　　printf("%d%d%d
",gongji[i],muji[i],xiaoji[i]);
　　}
}

但是这样还是有个问题，如果n=100的话，那么循环的次数太多了，最里面的那个循环要循环循环100W次呢，这样影响到速度。所以我们还要看看题目，公鸡是5元1只，那么我们不可能用n元买到n只，我们最多只能买n/5只，母鸡呢我们最多只能买n/3只，而小鸡的只数又与公鸡和母鸡有关，这样我们的循环就节省多了。 [Page]

修改后的代码：

#include<stdio.h>
voidchicken_question(intchicken_num,int*k,intg[],intm[],intx[])
...{
　　inta,b,c,t;
　　t=0;
　　for(a=0;a<=chicken_num/5;a++)
　　　　for(b=0;b<=chicken_num/3;b++)
　　　　...{
　　　　　　c=100-a-b;
　　　　　　if((a+b+c)==chicken_num&&(5*a+3*b+c/3==chicken_num)&&(c%3==0))
　　　　　　...{
　　　　　　　　g[t]=a;
　　　　　　　　m[t]=b;
　　　　　　　　x[t]=c;
　　　　　　　　t++;
　　　　　　}
　　　　}
　　*k=t;
}
main()
...{
　　intn;
　　intgongji[50],muji[50],xiaoji[50],num=0;
　　inti,*p_num=&num;
　　printf("公鸡5元每只，母鸡3元每只，小鸡3只1元");
　　printf("n元买n只鸡,请输入n的值：");
　　scanf("%d",&n);
　　chicken_question(n,p_num,gongji,muji,xiaoji);
　　for(i=0;i<num;i++)
　　...{
　　　　printf("%d%d%d
",gongji[i],muji[i],xiaoji[i]);
　　}
}

上一篇：面试题目：猫吃老鼠问题的求解下一篇：快速清空StringGrid单元格内容