C趣味编程百例(11)

文章类别：C语言程序设计 | 发表日期:2008-9-24 14:44:50

36.百钱百鸡问题
37.爱因斯坦的数学题
38.换分币



36.百钱百鸡问题
    中国古代数学家张丘建在他的《算经》中提出了闻名的“百钱买百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？
*题目分析与算法设计
    设鸡翁、鸡母、鸡雏的个数分别为x,y,z，题意给定共100钱要买百鸡，若全买公鸡最多买20只，显然x的值在0~20之间；同理，y的取值范围在0~33之间，可得到下面的不定方程：
                  5x+3y+z/3=100
                  x+y+z=100
    所以此问题可归结为求这个不定方程的整数解。
    由程序设计实现不定方程的求解与手工计算不同。在分析确定方程中未知数变化范围的前提下，可通过对未知数可变范围的穷举，验证方程在什么情况下成立，从而得到相应的解。
*程序说明与注释
#include<stdio.h>
void main()
{
    int x,y,z,j=0;
    printf("Folleing are possible plans to buy 100 fowls with 100 Yuan.\n");
    for(x=0;x<=20;x++)               /*外层循环控制鸡翁数*/
        for(y=0;y<=33;y++)           /*内层循环控制鸡母数y在0~33变化*/
        {
            z=100-x-y;             /*内外层循环控制下，鸡雏数z的值受x,y的值的制约*/
            if(z%3==0&&5*x+3*y+z/3==100)
                                   /*验证取z值的合理性及得到一组解的合理性*/
                printf("%2d:cock=%2d hen=%2d chicken=%2d\n",++j,x,y,z);
        }
}
*运行结果
Follwing are possible plans to buy 100 fowls with 100 Yuan.
    1:cock=0 hen=25 chicken=75
    2:cock=4 hen=18 chicken=78
    3:cock=8 hen=11 chicken=81
    4:cock=12 hen=4 chicken=84
*总是的进一步讨论
    这类求解不定方程总理的实现，各层循环的控制变量直接与方程未知数有关，且采用对未知数的取值范上穷举和组合的方法来复盖可能得到的全部各组解。能否根据题意更合理的设置循环控制条件来减少这种穷举和组合的次数，提高程序的执行效率，请读者考虑。


37.爱因斯坦的数学题
    爱因斯坦出了一道这样的数学题：有一条长阶梯，若每步跨2阶，则最最后剩一阶，若每步跨3 阶，则最后剩2阶，若每步跨5阶，则最后剩4阶，若每步跨6阶则最后剩5阶。只有每次跨7阶，最后才正好一阶不剩。请问这条阶梯共有多少阶？
*题目分析与算法设计
    根据题意，阶梯数满足下面一组同余式：
        x≡1 (mod2)
        x≡2 (mod3)
        x≡4 (mod5)
        x≡5 (mod6)
        x≡0 (mod7)
*程序说明与注释
#include<stdio.h>
void main()
{
    int i=1;                  /*i为所设的阶梯数*/
    while(!((i%2==1)&&(i%3==2)&&(i%5==4)&&(i%6==5)&&(i%7==0)))
        ++i;                  /*满足一组同余式的判别*/
    printf("Staris_number=%d\n",i);
}
*运行结果
    Staris_number=119
*问题的进一步讨论
    此题算法还可考虑求1、2、4、5的最小公倍数n，然后判t(t为n-1)≡0(mod7)是否成立，若不成立则t=t+n,再进行判别，直至选出满足条件的t值。请自行编写程序实现。

38.换分币
    用一元人民币兑换成1分、2分和5分硬币，共有多少种不同的兑换方法。
*题目分析与算法设计
    根据题意设i,j,k分别为兑换的1分、2分、5分硬币所具有的钱数(分)，则i,j,k的值应满足：
          i+j+k=100
*程序说明与注释
#include<stdio.h>
void main()
{
    int i,j,k,count=1;
    printf("There are follwing small exchange plans for 1 Yuan note:\n");
    for(i=0;i<=100;i++)         /*i为1分硬币钱数，可取值0,1，2...,100*/
        for(j=0;j<=100-i;j+=2)     /*j为2分硬币钱数，可取0值，2，4，...，100*/
            for(k=0;k<=100-i-2*j;k+=5)        /*k为5分硬币钱数*/
                if(i+j+k==100)
                    printf(count%4?"%d:1*%d+2*%d+5*%d\t":"%d:1*%d+2*%d+5*%d\n",count++,i,j/2,k/5);
}
*运行结果
    There are follwing small exchange plans for 1 Yuan note:

*思考题
    此题若修改条件，要求应换若干2分的，还应换若干1分的，且1分的个数是2分个数的10倍，其余的换成5分的，问每种硬币换多少个？

上一篇：{实例}C趣味编程百例(10) 人气:7231
下一篇：{实例}C趣味编程百例(12) 人气:5493

C语言程序设计视频教程