C语言常用的算法.pdf

迭代法

迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为 f(x)=0 ，用

某种

数学方法导出等价的形式 x=g(x) ，然后按以下步骤执行：

（1）选一个方程的近似根，赋给变量 x0；

（2）将 x0的值保存于变量 x1，然后计算 g(x1) ，并将结果存于变量 x0；

（3） 当x0与 x1的差的绝对值还小于指定的精度要求时，重复步骤（ 2）的计算。

若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的 x0就认

为是

} while ( fabs(x0-x1)>Epsilon) ；

printf( “方程的近似根是 %f ”，x0) ；

}

迭代算法也常用于求方程组的根，令

X= （x0，x1，, ， xn-1 ）

设方程组为：

xi=gi(X) (I=0 ，1，, ， n-1)

则求方程组根的迭代算法可描述如下：

【算法】迭代法求方程组的根

{ for (i=0 ；i<n ；i++)

for (delta=0.0,i=0 ； i<n;i++)

if (fabs(y[i]-x[i])>delta) delta=fabs(y[i]-x[i]) ；

} while (delta>Epsilon) ；

for (i=0;i<n;i++)

printf( “变量 x[%d] 的近似根是 %f ”，I ，x[i]) ；

printf( “ ”) ；

}

具体使用迭代法求根时应注意以下两种可能发生的情况：

（1）如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此

在

穷举搜索法

穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找

出那些符合要求的候选解作为问题的解。

6] 上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。 如图就是一个解。

程序引入变量 a、b、c、d、e、f ，并让它们分别顺序取 1至6的证书，在它们互不相同的

条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一

种满足要求的排列，把它们输出。当这些变量取尽所有的组合后，程序就可得到全部可能的

解。细节见下面的程序。

【程序 1】

if (c==a)||(c==b) continue ；

for (d=1 ；d<=6；d++) {

if (d==a)||(d==b)||(d==c) continue ；

for (e=1 ；e<=6；e++) {

if (e==a)||(e==b)||(e==c)||(e==d) continue ；

f=21-(a+b+c+d+e) ；

if ((a+b+c==c+d+e))&&(a+b+c==e+f+a)) {

printf( “%6d,a) ；

printf( “%4d%4d”,b,f) ；

printf( “%2d%4d%4d”,c,d,e) ；

}

按穷举法编写的程序通常不能适应变化的情况。 如问题改成有 9个变量排成三角形， 每条

边有 4个变量的情况，程序的循环重数就要相应改变。

对一组数穷尽所有排列，还有更直接的方法。将一个排列看作一个长整数，则所

有排列对应着一组整数。将这组整数按从小到大的顺序排列排成一个整数，从对应最小的整

数开始。按数列的递增顺序逐一列举每个排列对应的每个整数，这能更有效地完成排列的穷

举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若

当前排列为 1，2， 4，6，5，3，并令其对应的长整数为 124653。要寻找比长整数 124653更大

的排列，可从该排列的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一

个数字大时，如本例中的 6比它的前一位数字 4大，这说明还有对应更大整数的排列。但为了

在前面数字 1，2，5固定的情况下，还应选择对应最小整数的那个排列，为此还需将后面那部

分数字的排列顺序颠倒，如将数字 6，4，3的排列顺序颠倒，得到排列 1，2，5，3，4，6，这

才是排列 1， 2，4，6，5， 3的下一个排列。按以上想法编写的程序如下。

【程序 2】

# include <stdio.h>

# define SIDE_N 3

# define LENGTH 3

# define VARIABLES 6

int A,B,C,D,E,F ；

int *pt[]={&A,&B,&C,&D,&E,&F} ；

while(1)

{ for (i=0 ；i<SIDE_N；i++)

{ for (t=j=0 ；j<LENGTH；j++)

t+=*side[i][j] ；

side_total[i]=t ；

}

for (equal=1,i=0 ；equal&&i<SIDE_N-1 ；i++)

if (side_total[i]!=side_total[i+1] equal=0 ；

if (equal)

{ for (i=1 ；i<VARIABLES；i++)

if (j==0) break ；

for (i=VARIABLES-1 ；i>=j ； i--)

if (*pt[i]>*pt[i-1]) break ；

t=*pt[j-1] ； * pt[j-1] =* pt[i] ； *pt[i]=t ；

for (i=VARIABLES-1 ；i>j ；i--,j++)

{ t=*pt[j] ； *pt[j] =* pt[i] ； *pt[i]=t ； }

}

}

从上述问题解决的方法中，最重要的因素就是确定某种方法来确定所有的候选解。下面

再用一个示例来加以说明。

显然这个 n元组等价于一个选择方案。 用枚举法解决背包问题， 需要枚举所有的选取方案，而

根据上述方法，我们只要枚举所有的 n元组，就可以得到问题的解。

显然，每个分量取值为 0或1的 n元组的个数共为 2n个。而每个 n元组其实对应了一个长度

为n的二进制数，且这些二进制数的取值范围为 0～2n-1 。因此， 如果把 0～2n-1 分别转化为相

应的二进制数，则可以得到我们所需要的 2n个n元组。

【算法】

maxv=0；

for (i=0 ；i<2n ；i++)

{ B[0..n-1]=0 ；

把i 转化为二进制数，存储于数组 B中；

}

if ((temp_w<=tw)&&(temp_v>maxv))

{ maxv=temp_v ；

保存该 B数组；

}

}

}

递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题

规模为 N的解，当 N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问

由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整数，存储长整

数数组的每个元素只存储长整数的一位数字。如有 m位成整数 N用数组 a[ ] 存储：

N=a[m] ×10m-1+a[m-1] ×10m-2+ … +a[2] ×101+a[1] ×100

并用 a[0] 存储长整数 N的位数 m，即a[0]=m 。按上述约定，数组的每个元素存储 k的阶

乘k！的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素 ,, 。 例

如， 5！=120，在数组中的存储形式为：

3

0

2

1

=24，计算 5！，可对原来的 24累加 4次24后得到 120。细节见以下程序。

# include <stdio.h>

# include <malloc.h>

# define MAXN 1000

void pnext(int a[ ],int k)

{ int *b,m=a[0],i,j,r,carry ；

b=(int * ) malloc(sizeof(int)* (m+1)) ；

for ( i=1 ；i<=m；i++) b[i]=a[i] ；

for ( j=1 ；j<=k ；j++)

{ for ( carry=0,i=1;i<=m;i++)

free(b) ；

a[0]=m ；

}

void write(int *a,int k)

{ int i ；

printf( “%4d！=”,k) ；

for (i=a[0] ； i>0 ；i--)

printf( “%d”,a[i]) ；

printf( “\n\n ”) ；

a[0]=1 ；

a[1]=1 ；

write(a,1) ；

for (k=2 ；k<=n；k++)

{ pnext(a,k) ；

write(a,k) ；

getchar() ；

}

}