C语言简单算法举例.pptxVIP

简单算法举例

求1×2×3×4×5

S1:p=1

S2:i=2

S3:p=p×i

S4:i=i+1

S5:若i≤5,返回S3;否则结束

设两个变量。一个变量p代表被乘数，一个变量i代表乘数。不另设变量存放乘积结果，而直接将每一步的乘积放在被乘数变量中。

S3到S5组成一个循环。

算法结束，变量p就是所求结果。

举例:求5！的算法用流程图表示

求1-1/2+1/3-1/4+…+1/99-1/100

S1:sum=1

S2:deno=2

S3:sign=1

S4:sign=(-1)×sign

S5:term=sign×(1/deno)

S6:sum=sum+term

S7:deno=deno+1

S8:若deno≤100,返回S4;否则结束

求1-1/2+1/3-1/4+…+1/99-1/100

判定2000-2500年中的每一年是否闰年

S1:y=2000(y为被检测的年份）

S2:若y%4≠0,则输出y”不是闰年”。然后转到S5

S3:若y%4=0且y%100≠0,则输出y”是闰年”。然后转到S5

S4:若y%100=0且y%400=0,则输出输出y”是闰年”，否则输出“不是闰年”然后转到S5

S5:y=y+1

S6:当y≤2500时，转至S2继续执行，否则，算法停止

对于一个大于或等于3的正整数，判断它是不是一个素数

S1:输入n的值

S2:i=2（i作为除数）

S3:n被i除，得余数r

S4:如果r=0,表示能被i整除，则打印n“不是素数”，算法结束；否则执行S5

S5:i=i+1

S6:如果i≤√n,返回S3;否则打印n“是素数”。然后结束

所谓素数，指除1和该数本身之外，不能被其它任何整数整除的数

方法：将n作为被除数，将2到√n之间的各个整数轮流作为除数。如果不能被整除，则n为素数。

判断素数的算法用流程图表示

由上述例子可以看出，算法都是由基本功能操作和控制结构这两个要素组成。

1）计算机基本功能操作四个方面

①逻辑运算 ②算术运算

③数据比较=≠④数据传送（输入输出赋值）

2)算法控制结构决定算法的执行顺序

总结:典型算法

迭代法

穷举法（枚举法）

递推与递归法

迭代法

基本思想：把一个复杂的问题的求解过程转化为相对简单的迭代算式，然后重复执行这个简单的算式，直到得到最终解。

在科学计算领域中，许多问题需要这种解决办法。

特点：迭代公式

如p=p×i；例sum=sum+term

又如：求解方程x3-x-1=0,在x=1.5附近的根。

利用迭代公式x=(x+1)1/3

将x0=1.5代入右端，

得x1=(1.5+1)1/3=1.35721

再用x1作为近似值代入上式右端，

得x2=(1.35721+1)1/3=1.33086

重复以上步骤，逐次求得更精确的解。

穷举法

基本思想：首先根据问题的部分条件预估答案的范围，然后在此范围内对所有可能的情况进行逐一验证，直到全部情况均通过了验证为止。若某个情况使验证符合题目的全部条件，则该情况为本题一个答案。若全部情况验证结果均不符合题目的全部条件，则说明该问题无解。

举例：“百钱百鸡问题”

鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？

如果用x,y,z分别代表公鸡，母鸡，小鸡的数量，根据题意列方程：

x+y+z=100

5x+3y+z/3=100

根据题意：x,y,z范围一定是0到100的正整数。最简单的方法是在此范围内不断变化x,y,z的值，穷举x,y,z全部可能组合，若满足方程组则是一组解。这样即可得问题的全部解。

递推与递归法

递推法：利用递推公式，由简到繁逐次迭代求解。关键是找到进行递推的通项公式。

递归法：利用递推公式，由繁到简，用简单的问题和已知操作运算来解决问题，要求语言具有反复自我调用的能力。

举例：f(n)=n×f(n-1)f(1)=1

数列通项f(n)=n!