项目三 基本算法.ppt

项目三基本算法应用课程回顾项目三基本算法应用项目三基本算法应用项目三基本算法应用项目三基本算法应用项目三基本算法应用[SF1-1]求Sum=1+2+3+5+…+100
[SF1-2]求P=10!
[SF1-3]求Sum=1!+2!+3!+…+10!有许多问题的解“隐藏”在多个可能之中。穷举就是对多种可能情形一一测试，从多种可能中找出符合条件的（一个或一组）解。当然，也可能得出无解的结论。【SF2】百钱买百鸡问题设鸡翁、鸡母、鸡雏的数量分别为cocks、hens、chicks，则可得如下模型：
5*cocks+3*hens+chicks/3.0=100
cocks+hens+chicks=100
下面考虑如何寻找另外的约束条件。
按常识，cocks、hens、chicks都应为正整数，且它们的取值范围分别应为：
cocks：0～20(假如100元全买cocks，最多20只)
hens：0～33(假如100元全买hens，最多33只)
chicks：0～100(假如全买chicks，最多100只)本题的穷举过程如下：
首先从0开始，列举cocks（鸡翁）的各个可能值，在每个cocks值下找满足两个方程的一组解算法如下：
for(cocks=0;cocks<20;++cocks)
{/*下面进一步用穷举法来表现S1：*/
for(hens=0;hens<33;++hens)
{
s1.2找满足方程的一个chicks
s2输出一组解
}
}由于对列举的每个cocks与每个hens都可以按下式
chicks=100-cocks–hens
求出一个chicks。
因此，只要该chicks满足另一个方程
5*cocks+3*hens+chicks/3.0=100
便可以得到一组满足题意的cocks、hens、chicks。
故S1.2可以改写为：
chicks=100-cocks–hens;
if(5*cocks+3*hens+chicks/3.0=100)
printf(“%d\t%d\t%d\n”,cocks,hens,chicks);
经过剥葱头似的几步求精过程，再加入类型声明语句并调整输出格式，便可以得到一个C程序。算法如下：
for(cocks=0;cocks<20;++cocks)
{/*下面进一步用穷举法来表现S1：*/
for(hens=0;hens<33;++hens)
{
chicks=100–cokcs-hens;
if(5*cocks+3*hens+chicks/3.0=100)
printf(“%d\t%d\t%d\n”,cocks,hens,chicks);
}
}/*程序名:SF2.c*/
#include<stdio.h>
voidmain()
{
intcocks,hens,chicks;
printf(“\n公鸡数\t母鸡数\t小鸡数");
for(cokcs=0;cocks<20;++cocks)/*穷举cocks*/
for(hens=0;hens<33;++hens)
{
chicks=100–cokcs-hens;
if(5*cocks+3*hens+chicks/3.0=100)
printf(“%d\t%d\t%d\n”,cocks,hens,chicks);
}
}运行结果
公鸡数 母鸡数 小鸡数
0 25 75
4 18 78
8 11 81
12 4 84编程练习父子俩的年龄：父亲今年30岁，儿子今年6岁，问多少年后父亲的年龄始儿子年龄的2倍。
换硬币：把一元人民币换成5分、2分、1分的硬币，有多少种换法?
要登上n阶楼梯，每一步允许跨1阶或2阶。共有多少种登楼梯方法？
打印出500之内所有能被7或9整除的数。7.奇妙的算式：有人用字母代替十进制数字写出下面的算式。请找出这些字母代表的数字
EGAL
×L
────────
LGAE
8.找赛手：两个羽毛球队进行比赛，各出三人。甲队为A，B，C三人，乙队为x、y、z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。A说他不和x比，C说他不和x、z比。请编写一个程序找出三对赛手的名单。课程回顾任务2.3最大公约数、最小公倍数任务2.4求素数算法课程回顾假定一对新出生的兔子一个月后成熟，并且再过一个月开始生出一对小兔子。按此规律，在没有兔子死亡的情形下，一对初生的兔子，到一年头上，可以繁殖成多少对兔子？任务2.5递推与迭代算法假定一对新出生的兔子一个月后成熟，并且再过一个月开始生出一对小兔子。按此规律，在没有兔子死亡的情形下，一对初生的兔子，到一年头上，可以繁殖成多少对兔子？1，1，2，3，5，8，13，21，34，55…编写一个C程序，利用如下的格里高利公式求π的值。直到最后一项的值小于10