重复结构典型算法.ppt

重复结构典型算法
*
第一页，共28页
编写求 1-2+3-4+5- ... -100的和程序。
 第一步：设定项号，定义变量，找前后项关系
这是关键的一步。
  设定项号n =1 2 3 4 ...
sum=1-2+3-4+5- ... –100
存和
前后项关系为n=n+1，比较简单。生成的数n有正负号，且有规律：奇数为正，偶数为负,可用二选一if语句判别；这里定义一个变量s判别。
第二步：构造重复结构
求解这类题目，循环体总要执行多次。采用do while重复结构是很自然的。用其它重复结构，可行吗？
*
第二页，共28页
do
{ n=n+1; s=-s;
sum=sum+s*n;
} while (n<100);
第三步：设置变量初值
设置变量初值是保证正确计算出第一项值。十分明显，各变量的初值为：
int n=0, sum=0, s=-1;
第四步： 静态检查
跟踪三步左右，如果结果是正确的，一般情况下，可断定算法是正确的。
*
第三页，共28页
语句 第一次循环 第二次循环 第三次循环
n=n+1; 1 2 3
s=-s 1 -1 1
sum=sum+s*n; 1 -1 2
第五步：编程

通过上述分析，确定了数据结构，定义了有关变量和类型(因明显是整型，未作说明),完成了算法设计。接下来编程就是用C语言精确表述这一思维过程。
/* 求 1-2+3-4+5- ... -100的和 */
#include <>
void main()
{ int sum=0,n=0,s=-1;
printf(" *** 运行结果 ***\n");
*
第四页，共28页
do
{
n++;
s=-s;
sum+=s*n;
} while (n<100);
printf("1-2+3-4+ ... -100=%d\n",sum);
}
*** 运行结果 ***
1-2+3-4+ ... -100=-50
编写下述功能程序：
求 sinx=x-x3/3!+x5/5!-x7/7!+ ... 的近似值，误差为1×10-8。
*
第五页，共28页
do
{
n++;
s=-s;
sum+=s*n;
} while (n<100);
printf("1-2+3-4+ ... -100=%d\n",sum);
}
*** 运行结果 ***
1-2+3-4+ ... -100=-50
编写下述功能程序：
求 sinx=x-x3/3!+x5/5!-x7/7!+ ... 的近似值，误差为1×10-8。
*
第六页，共28页
第一步：设定项号，定义变量，找前后项关系
设定项号n=1 2 3 4 ...
sinx=x-x3/3!+x5/5!-x7/7!+ ...
存sin函数值 存x的幂xn 存阶乘fact
前后项关系比较复杂。从整体找前后项关系比较困难，分别找前后项的分子和分母的关系比较简便。前后项关系：
分子 xn = -xn*x*x
分母 fact=fact*(2*n-2)*(2*n-1)
*
第七页，共28页
第二步： 构造重复结构
求解这类题目，循环体总要执行多次(循环次数不确定)，一般采用do while重复结构。
do
{
n=n+1; xn=-xn*x*x;
fact=fact*(2*n-2)*(2*n-1);
sinx=sinx+xn/fact;
} while (fabs(xn/fact)>1e-8);
第三步：设置变量初值