第 7章 常用基本算法的 C语言实现
7.1统计与计数问题算法
7.2 累加 /累乘求和与求积问题算法
7.3 解决不确定性问题的穷举算法
7.4排序问题算法
7.5数值积分算法
7.6多项式计算问题算法
7.7非线性方程求解问题算法
7.8产生随机数算法
7.1统计与计数问题算法统计与计数问题应用比较普遍,一般方法是：设定一个计数器变量 count,初值为 0，
每获得一个数据,进行必要判断后,若满足统计条件,则计数器变量 count加 1,这样当对所有数据进行判断后,计数器变量 count的值就是统计的结果 。
【 例 7.1】 输入若干非 0实数,统计其中正数的个数,负数的个数 。 遇到 0时结束 。
分析：设两个计数器变量 n和 m,n用于统计正数的个数,m用于统计负数的个数 。
#include <stdio.h>
main( )
{ int n,m;
double x;
n=0; m=0;
printf("please input real numbers:\n ");
scanf("%lf ",&x);
while(x!=0)
{if(x>0) n++;
else m++
scanf("%lf ",&a);
}
printf("plus=%d,negative=%d\n ",n,m);
} [Return]
7.2 累加 /累乘求和与求积问题算法求解累加和问题时,存放求和结果的变量 （ 例如
sum） 初值一般为 0,采用循环的方式获取数据,每循环一次,求和变量累加一个数据,最后求和变量的值即为这些数据累加的和 。
求解累乘问题时,存放乘积结果的变量 （ 例如
mul） 初值一般为 1,将每次获取的待累乘的数据依次连乘到乘积结果变量,最后乘积变量的值即为这些数据连乘的积 。
【 例 7.3】 输入 n个整数,计算并输出平均成绩,
要求输出精确到两位小数 。
【 例 7.3】 输入 n个整数,计算并输出平均成绩,要求输出精确到两位小数 。
算法的 程序代码如下：
#include <stdio.h>"
main( )
{int i,score,sum=0
double ave;
printf("please input n=\n ");
scanf("%d ",&n);
printf("input %d number,\n ",n);
for(i=1;i<=n;i++)
{ scanf("%d ",&score);
sum+=score;
}
ave=sum/n;
printf("average=%.2f\n ",ave);
} [Return]
7.3 解决不确定性问题的穷举算法有些问题很难用确定的算法步骤进行描述,或根本就没有确定的算法描述方法,但它们具有这样的特点：如果问题有一组或多组解,则必定全在某个集合中；如果集合内无解,集合外也肯定无解 。
这样,就可以将集合中的元素一一列举出来,验证是否为问题的解,这就是穷举法 。
最简单得一类穷举问题可用线性方程或线性方程组或不等式解决 。
【 例 7.6】 公元五世纪,我国数学家张邱建在
,算经,一书中提出有趣的百钱买百鸡问题：,鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,
百钱买百鸡,问翁母雏各几何？,
分析：设 x,y,z分别表示买鸡翁,鸡母,鸡雏的数目,则有
x+y+z=100
5x+3y+z/3=100
三个未知数,两个方程,有无穷多组解,在本题中,应只求正整数解 。 根据可能性分析,得出可能的取值范围为：鸡翁 x,1～ 19之间；鸡母,1～ 32之间；鸡雏,3～ 98之间；
可用一个三重循环对 x,y,z的所有组合情况,测试满足条件的解 。
为减少循环次数,可对上述方程进行优化,用
z=100-x-y带入另一个方程,得,7x+4y=100。
用二重循环即可实现程序代码 。
算法程序代码如下：
#include <stdio.h>
main( )
{
int x,y;
printf("%5c%5c%5c"\n,'x','y','z');
for(x=1;x<=19;x++)
for(y=1;y<=32;y++)
if(7*x+4*y==100)
{
printf("%5d%5d%5d\n",x,y,100-x-y);
break;
}
} [Return]
排序是程序设计中一种重要的操作,应用十分普遍,
常用的排序算法有选择排序,插入排序,冒泡排序,索引排序等几种：
【 例 7.9】 用选择排序算法对 n个数组元素进行排序。
将 N个数组元素 a[0]~a[N-1]由小到大进行选择排序的基本方法是：
第 0步,找到 a[0]~a[N-1]中的最小值元素与 a[0]交换 ;
第 1步,找到 a[1]~a[N-1]中的最小值元素与 a[1]交换；
…
第 N-2步,找到 a[N-2]~a[N-1]中的最小值元素与 a[N-2]
交换。
排序完成。 [Return]
7.4排序问题算法
1,变步长梯形求积分法变步长梯形积分法计算定积分的基本思想是：
首先用梯形公式计算 其中,n=1,h=b-a;
然后用下列递推公式计算：
2n--->n,0.5h--->h
直到 |T2n-Tn|<ε为止。
【 例 7.13】 用变步长梯形求积分法求的定积分。取 ε=0.000001。
算法程序代码如下：
7.5 数值积分算法
#include <stdio.h>
#include <math.h>
double fx(double x) /*计算被积函数 f(x)的值，此处计算 exp(-
x*x))*/
{
double y;
y=exp(-x*x);
return(y);
}
double txdjf(double a,double b,double eps) /*计算积分 */
{/*参数说明,a为积分下限,b为积分上限,eps 为积分精度要求
*/
int n,k;
double fa,fb,h,t1,p,s,x,t,k;
fa=fx(a);
fb=fx(b);
n=1; h=b-a;
t1=h*(fa+fb)/2.0;
p=eps+1.0;
while (p>=eps)
{
s=0.0;
for (k=0; k<=n-1; k++)
{
x=a+(k+0.5)*h; s=s+fx(x);
}
t=(t1+h*s)/2.0; p=fabs(t1-t);
t1=t; n=n+n; h=h/2.0;
}
return(t);
}
main( )
{
double a,b,eps,s;
a=0.0; b=1.0; eps=0.000001;
s= txdjf (a,b,eps);
printf("s=%e\n",s);
} [Return]
1,一元多项式求值算法计算一元多项式 p(x)=an-1xn-1+an-2xn-
2+…+a1x+a0 在指定点 x处的函数值的一般方法是：
首先将多项式表示成如下嵌套形式：
p(x)=(…((an -1x+an-2)x+ an-3)x+…+a1)x+a0
然后从里往外一层一层地计算。其递推计算公式如下：
un-1=an-1
uk=uk+1x+ak,k=n-1,n-2,…,1,0
最后得到的 u0就是多项式 p(x)的值。
【 例 7.15】 计算多项式 p(x)= x6-6x5+3x4+5x3-
x2+7x-15
7.6 多项式计算问题算法
#include <stdio.h>
double dxs(double a[],int n,double x) /*求多项式在 x处的值,x为变量的实际值 */
{ /*参数说明,a为存放多项式系数的数组,n为多项式的项数（值为最高次数减 1）
*/
int i;
double u;
u=a[n-1];
for (i=n-2; i>=0; i--) u=u*x+a[i];
return(u);
}
main( )
{
int i;
double px;
double a[7]={-15.0,7.0,- 1.0,5.0,3.0,-6.0,
1.0}; /*系数数组初始化 */
double x[6]={0.8,-0.8,1.1,-1.1,1.5,-1.5};
/*变量数组初始化 */
for (i=0; i<=5; i++)
{
px= dxs(a,7,x[i]);
printf("x(%d)=%5.2lf p(%d)=%13.7e\n",
i,x[i],i,px);
}
} [Return]
【 例 7.19】 用牛顿迭代法求方程 f(x)=x3+2x2+10x-20=0在 1.2附近的一个实根。要求精确到 ε＝ 0.000001，最大迭代次数为 60。其中 f'(x)
＝ 3x2+4x＋ 10
分析：迭代是一个不断用新值取代旧值的过程。
设方程 f(x)=0满足以下条件：
(1)f(x)在闭区间 [a,b]上，其 f'(x)与 f"(x)均存在，且各自保持固定符号；
(2) f(x)连续,f(a)与 f(b)异号；
(3)f(x0)f"(x)>0，且 x,x0∈ [a,b];
则方程 f(x)＝ 0在区间 [a,b]上有且只有一个实根。
取初值 x0，由牛顿迭代公式：
xn+1=xn-f(xn)/f’(xn)
计算得到的序列 x0,x1,…,xn,… 逐渐逼近于方程 f(x)=0的根。
结束迭代过程的条件为 (|f(xn+1)|<ε 与 (|xn+1-xn|)<ε同时成立，
其中 ε为精度要求。
7.7 非线性方程求解问题算法
#include <stdio.h>
#include "math.h"
void fx(double x,double y[2])/*计算 f(x)与 f’(x)的值函数 */
{
y[0]=x*x*x+2.0*x*x+10.0*x-20.0; /* f(x)的表达式 */
y[1]=3.0*x*x+4.0*x+10; /* f’(x)的表达式 */
return;
}
int dd(double *x,double eps,int js)
{ /*参数说明,x存放迭代初值和迭代结果的指针变量 ;eps精度值 ;js*最大迭代次数 /
int k,l;
double y[2],d,p,x0,x1;
l=js; k=1; x0=*x;
fx(x0,y);
d=eps+1.0;
while ((d>=eps)&&(l!=0))
{
if (fabs(y[1])+1.0==1.0)
{
printf("err\n"); return(-1);}
x1=x0-y[0]/y[1];
fx(x1,y);
d=fabs(x1-x0); p=fabs(y[0]);
if (p>d) d=p;
x0=x1; l=l-1;
}
*x=x1;
k=js-l;
return(k);
}
main( )
{
int js,k;
double x,eps;
eps=0.000001; js=60; x=1.5;
k=dd(&x,eps,js);
if (k>=0)
printf("k=%d x=%13.7e\n",k,x);
printf("\n");
} [Return]
【 例 7.20】 连续产生 10个 0到 1之间均匀分布的随机数。 r的初值取 5.0。
分析：产生 0到 1之间均匀分布的一个随机数的公式如下：
ri=mod(2053ri-1+13849,m),i=1,2,…
pi=ri/m
其中 ri为随机数种子,pi为第 i个随机数。
设 m=216＝ 65536
程序代码如下：
7.8 产生随机数算法
#include "stdio.h" /*该函数的功能是返回一个 0到 1之间分布的随机数 */
double mrnd1(double *r) /*形参 r为指针变量，指向存放随机数种子的存储单元 */
{
int m;
double s,p;
s=65536.0;
m=(int)(*r/s); *r=*r-m*s; *r=2053.0*(*r)+
13849.0;
m=(int)(*r/s); *r=*r-m*s; p=*r/s;
return(p);
}
main( )
{
int i;
double r;
r=5.0;
for (i=0; i<=9; i++)
printf("%10.7lf\n",mrnd1(&r));
} [Return]
7.1统计与计数问题算法
7.2 累加 /累乘求和与求积问题算法
7.3 解决不确定性问题的穷举算法
7.4排序问题算法
7.5数值积分算法
7.6多项式计算问题算法
7.7非线性方程求解问题算法
7.8产生随机数算法
7.1统计与计数问题算法统计与计数问题应用比较普遍,一般方法是：设定一个计数器变量 count,初值为 0，
每获得一个数据,进行必要判断后,若满足统计条件,则计数器变量 count加 1,这样当对所有数据进行判断后,计数器变量 count的值就是统计的结果 。
【 例 7.1】 输入若干非 0实数,统计其中正数的个数,负数的个数 。 遇到 0时结束 。
分析：设两个计数器变量 n和 m,n用于统计正数的个数,m用于统计负数的个数 。
#include <stdio.h>
main( )
{ int n,m;
double x;
n=0; m=0;
printf("please input real numbers:\n ");
scanf("%lf ",&x);
while(x!=0)
{if(x>0) n++;
else m++
scanf("%lf ",&a);
}
printf("plus=%d,negative=%d\n ",n,m);
} [Return]
7.2 累加 /累乘求和与求积问题算法求解累加和问题时,存放求和结果的变量 （ 例如
sum） 初值一般为 0,采用循环的方式获取数据,每循环一次,求和变量累加一个数据,最后求和变量的值即为这些数据累加的和 。
求解累乘问题时,存放乘积结果的变量 （ 例如
mul） 初值一般为 1,将每次获取的待累乘的数据依次连乘到乘积结果变量,最后乘积变量的值即为这些数据连乘的积 。
【 例 7.3】 输入 n个整数,计算并输出平均成绩,
要求输出精确到两位小数 。
【 例 7.3】 输入 n个整数,计算并输出平均成绩,要求输出精确到两位小数 。
算法的 程序代码如下：
#include <stdio.h>"
main( )
{int i,score,sum=0
double ave;
printf("please input n=\n ");
scanf("%d ",&n);
printf("input %d number,\n ",n);
for(i=1;i<=n;i++)
{ scanf("%d ",&score);
sum+=score;
}
ave=sum/n;
printf("average=%.2f\n ",ave);
} [Return]
7.3 解决不确定性问题的穷举算法有些问题很难用确定的算法步骤进行描述,或根本就没有确定的算法描述方法,但它们具有这样的特点：如果问题有一组或多组解,则必定全在某个集合中；如果集合内无解,集合外也肯定无解 。
这样,就可以将集合中的元素一一列举出来,验证是否为问题的解,这就是穷举法 。
最简单得一类穷举问题可用线性方程或线性方程组或不等式解决 。
【 例 7.6】 公元五世纪,我国数学家张邱建在
,算经,一书中提出有趣的百钱买百鸡问题：,鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,
百钱买百鸡,问翁母雏各几何？,
分析：设 x,y,z分别表示买鸡翁,鸡母,鸡雏的数目,则有
x+y+z=100
5x+3y+z/3=100
三个未知数,两个方程,有无穷多组解,在本题中,应只求正整数解 。 根据可能性分析,得出可能的取值范围为：鸡翁 x,1～ 19之间；鸡母,1～ 32之间；鸡雏,3～ 98之间；
可用一个三重循环对 x,y,z的所有组合情况,测试满足条件的解 。
为减少循环次数,可对上述方程进行优化,用
z=100-x-y带入另一个方程,得,7x+4y=100。
用二重循环即可实现程序代码 。
算法程序代码如下：
#include <stdio.h>
main( )
{
int x,y;
printf("%5c%5c%5c"\n,'x','y','z');
for(x=1;x<=19;x++)
for(y=1;y<=32;y++)
if(7*x+4*y==100)
{
printf("%5d%5d%5d\n",x,y,100-x-y);
break;
}
} [Return]
排序是程序设计中一种重要的操作,应用十分普遍,
常用的排序算法有选择排序,插入排序,冒泡排序,索引排序等几种：
【 例 7.9】 用选择排序算法对 n个数组元素进行排序。
将 N个数组元素 a[0]~a[N-1]由小到大进行选择排序的基本方法是：
第 0步,找到 a[0]~a[N-1]中的最小值元素与 a[0]交换 ;
第 1步,找到 a[1]~a[N-1]中的最小值元素与 a[1]交换；
…
第 N-2步,找到 a[N-2]~a[N-1]中的最小值元素与 a[N-2]
交换。
排序完成。 [Return]
7.4排序问题算法
1,变步长梯形求积分法变步长梯形积分法计算定积分的基本思想是：
首先用梯形公式计算 其中,n=1,h=b-a;
然后用下列递推公式计算：
2n--->n,0.5h--->h
直到 |T2n-Tn|<ε为止。
【 例 7.13】 用变步长梯形求积分法求的定积分。取 ε=0.000001。
算法程序代码如下：
7.5 数值积分算法
#include <stdio.h>
#include <math.h>
double fx(double x) /*计算被积函数 f(x)的值，此处计算 exp(-
x*x))*/
{
double y;
y=exp(-x*x);
return(y);
}
double txdjf(double a,double b,double eps) /*计算积分 */
{/*参数说明,a为积分下限,b为积分上限,eps 为积分精度要求
*/
int n,k;
double fa,fb,h,t1,p,s,x,t,k;
fa=fx(a);
fb=fx(b);
n=1; h=b-a;
t1=h*(fa+fb)/2.0;
p=eps+1.0;
while (p>=eps)
{
s=0.0;
for (k=0; k<=n-1; k++)
{
x=a+(k+0.5)*h; s=s+fx(x);
}
t=(t1+h*s)/2.0; p=fabs(t1-t);
t1=t; n=n+n; h=h/2.0;
}
return(t);
}
main( )
{
double a,b,eps,s;
a=0.0; b=1.0; eps=0.000001;
s= txdjf (a,b,eps);
printf("s=%e\n",s);
} [Return]
1,一元多项式求值算法计算一元多项式 p(x)=an-1xn-1+an-2xn-
2+…+a1x+a0 在指定点 x处的函数值的一般方法是：
首先将多项式表示成如下嵌套形式：
p(x)=(…((an -1x+an-2)x+ an-3)x+…+a1)x+a0
然后从里往外一层一层地计算。其递推计算公式如下：
un-1=an-1
uk=uk+1x+ak,k=n-1,n-2,…,1,0
最后得到的 u0就是多项式 p(x)的值。
【 例 7.15】 计算多项式 p(x)= x6-6x5+3x4+5x3-
x2+7x-15
7.6 多项式计算问题算法
#include <stdio.h>
double dxs(double a[],int n,double x) /*求多项式在 x处的值,x为变量的实际值 */
{ /*参数说明,a为存放多项式系数的数组,n为多项式的项数（值为最高次数减 1）
*/
int i;
double u;
u=a[n-1];
for (i=n-2; i>=0; i--) u=u*x+a[i];
return(u);
}
main( )
{
int i;
double px;
double a[7]={-15.0,7.0,- 1.0,5.0,3.0,-6.0,
1.0}; /*系数数组初始化 */
double x[6]={0.8,-0.8,1.1,-1.1,1.5,-1.5};
/*变量数组初始化 */
for (i=0; i<=5; i++)
{
px= dxs(a,7,x[i]);
printf("x(%d)=%5.2lf p(%d)=%13.7e\n",
i,x[i],i,px);
}
} [Return]
【 例 7.19】 用牛顿迭代法求方程 f(x)=x3+2x2+10x-20=0在 1.2附近的一个实根。要求精确到 ε＝ 0.000001，最大迭代次数为 60。其中 f'(x)
＝ 3x2+4x＋ 10
分析：迭代是一个不断用新值取代旧值的过程。
设方程 f(x)=0满足以下条件：
(1)f(x)在闭区间 [a,b]上，其 f'(x)与 f"(x)均存在，且各自保持固定符号；
(2) f(x)连续,f(a)与 f(b)异号；
(3)f(x0)f"(x)>0，且 x,x0∈ [a,b];
则方程 f(x)＝ 0在区间 [a,b]上有且只有一个实根。
取初值 x0，由牛顿迭代公式：
xn+1=xn-f(xn)/f’(xn)
计算得到的序列 x0,x1,…,xn,… 逐渐逼近于方程 f(x)=0的根。
结束迭代过程的条件为 (|f(xn+1)|<ε 与 (|xn+1-xn|)<ε同时成立，
其中 ε为精度要求。
7.7 非线性方程求解问题算法
#include <stdio.h>
#include "math.h"
void fx(double x,double y[2])/*计算 f(x)与 f’(x)的值函数 */
{
y[0]=x*x*x+2.0*x*x+10.0*x-20.0; /* f(x)的表达式 */
y[1]=3.0*x*x+4.0*x+10; /* f’(x)的表达式 */
return;
}
int dd(double *x,double eps,int js)
{ /*参数说明,x存放迭代初值和迭代结果的指针变量 ;eps精度值 ;js*最大迭代次数 /
int k,l;
double y[2],d,p,x0,x1;
l=js; k=1; x0=*x;
fx(x0,y);
d=eps+1.0;
while ((d>=eps)&&(l!=0))
{
if (fabs(y[1])+1.0==1.0)
{
printf("err\n"); return(-1);}
x1=x0-y[0]/y[1];
fx(x1,y);
d=fabs(x1-x0); p=fabs(y[0]);
if (p>d) d=p;
x0=x1; l=l-1;
}
*x=x1;
k=js-l;
return(k);
}
main( )
{
int js,k;
double x,eps;
eps=0.000001; js=60; x=1.5;
k=dd(&x,eps,js);
if (k>=0)
printf("k=%d x=%13.7e\n",k,x);
printf("\n");
} [Return]
【 例 7.20】 连续产生 10个 0到 1之间均匀分布的随机数。 r的初值取 5.0。
分析：产生 0到 1之间均匀分布的一个随机数的公式如下：
ri=mod(2053ri-1+13849,m),i=1,2,…
pi=ri/m
其中 ri为随机数种子,pi为第 i个随机数。
设 m=216＝ 65536
程序代码如下：
7.8 产生随机数算法
#include "stdio.h" /*该函数的功能是返回一个 0到 1之间分布的随机数 */
double mrnd1(double *r) /*形参 r为指针变量，指向存放随机数种子的存储单元 */
{
int m;
double s,p;
s=65536.0;
m=(int)(*r/s); *r=*r-m*s; *r=2053.0*(*r)+
13849.0;
m=(int)(*r/s); *r=*r-m*s; p=*r/s;
return(p);
}
main( )
{
int i;
double r;
r=5.0;
for (i=0; i<=9; i++)
printf("%10.7lf\n",mrnd1(&r));
} [Return]
