常用算法设计思路方法、迭代法
迭代法是用于求方程或方程组近似根种常用算法设计思路方法设方程为f(x)=0用某种数学思路方法导出等价形式x=g(x)然后按以下步骤执行:
(1) 选个方程近似根赋给变量x0；
(2) 将x0值保存于变量x1然后计算g(x1)并将结果存于变量x0；
(3) 当x0和x1差绝对值还小于指定精度要求时重复步骤(2)计算
若方程有根并且用上述思路方法计算出来近似根序列收敛则按上述思路方法求得x0就认为是方程根上述算法用C形式表示为:
【算法】迭代法求方程根
{ x0=近似根；
do {
x1=x0；
x0=g(x1)； /*按特定方程计算新近似根*/
} while ( fabs(x0-x1)>Epsilon)；
prf(“方程近似根是%f\n”x0)；
}
迭代算法也常用于求方程组根令
X=(x0x1…xn-1)
设方程组为:
xi=gi(X) (I=01…n-1)
则求方程组根迭代算法可描述如下:
【算法】迭代法求方程组根
{ for (i=0;i<n;i)
x=近似根;
do {
for (i=0;i<n;i)
y=x;
for (i=0;i<n;i)
x=gi(X);
for (delta=0.0,i=0;i<n;i)
(fabs(y-x)>delta) delta=fabs(y-x)；
} while (delta>Epsilon)；
for (i=0;i<n;i)
prf(“变量x[%d]近似根是 %f”Ix)；
prf(“\n”)；
}
具体使用迭代法求根时应注意以下两种可能发生情况:
(1) 如果方程无解算法求出近似根序列就不会收敛迭代过程会变成死循环因此在使用迭代算法前应先考察方程是否有解并在中对迭代次数给予限制；
(2) 方程虽然有解但迭代公式选择不当或迭代近似根选择不合理也会导致迭代失败

2、穷举搜索法
穷举搜索法是对可能是解众多候选解按某种顺序进行逐枚举和检验并从众找出那些符合要求候选解作为问题解
【问题】 将A、B、C、D、E、F这 6个变量排成如图所示 3角形这 6个变量分别取[16]上整数且均不相同求使 3角形 3条边上变量的和相等全部解如图就是个解
引入变量a、b、c、d、e、f并让它们分别顺序取1至6证书在它们互不相同条件下测试由它们排成如图所示 3角形 3条边上变量的和是否相等如相等即为种满足要求排列把它们输出当这些变量取尽所有组合后就可得到全部可能解细节见下面
【1】
# <stdio.h>
void
{ a,b,c,d,e,f;
for (a=1;a<=6;a)
for (b=1;b<=6;b) {
(ba) continue;
for (c=1;c<=6;c) {
(ca)||(cb) continue;
for (d=1;d<=6;d) {
(da)||(db)||(dc) continue;
for (e=1;e<=6;e) {
(ea)||(eb)||(ec)||(ed) continue;
f=21-(a+b+c+d+e);
((a+b+cc+d+e))&&(a+b+ce+f+a)) {
prf(“%6d,a);
prf(“%4d%4d”,b,f);
prf(“%2d%4d%4d”,c,d,e);
scanf(“%*c”);
}
}
}
}
}
}
按穷举法编写通常不能适应变化情况如问题改成有9个变量排成 3角形每条边有4个变量情况循环重数就要相应改变
对组数穷尽所有排列还有更直接思路方法将个排列看作个长整数则所有排列对应着组整数将这组整数按从小到大顺序排列排成个整数从对应最小整数开始按数列递增顺序逐列举每个排列对应每个整数这能更有效地完成排列穷举从个排列找出对应数列下个排列可在当前排列基础上作部分调整来实现倘若当前排列为124653并令其对应长整数为124653要寻找比长整数124653更大排列可从该排列最后个数字顺序向前逐位考察当发现排列中某个数字比它前个数字大时如本例中6比它前位数字4大这介绍说明还有对应更大整数排列但为了顺序从小到大列举出所有排列不能立即调整得太大如本例中将数字6和数字4交换得到排列126453就不是排列124653下个排列为了得到排列124653下个排列应从已经考察过那部分数字中选出比数字大但又是它们中最小那个数字比如数字5和数字4交换该数字也是从后向前考察过程中第个比4大数字5和4交换后得到排列125643在前面数字125固定情况下还应选择对应最小整数那个排列为此还需将后面那部分数字排列顺序颠倒如将数字643排列顺序颠倒得到排列125346这才是排列124653下个排列按以上想法编写如下
【2】
# <stdio.h>
# SIDE_N 3
# LENGTH 3
# VARIABLES 6
A,B,C,D,E,F;
*pt={&A,&B,&C,&D,&E,&F};
*side[SIDE_N][LENGTH]={&A,&B,&C,&C,&D,&E,&E,&F,&A};
side_total[SIDE_N];
{}
{ i,j,t,equal;
for (j=0;j<VARIABLES;j)
*pt[j]=j+1;
while(1)
{ for (i=0;i<SIDE_N;i)
{ for (t=j=0;j<LENGTH;j)
t*side[j];
side_total=t;
}
for (equal=1,i=0;equal&&i<SIDE_N-1;i)
(side_total!=side_total[i+1] equal=0;
(equal)
{ for (i=1;i<VARIABLES;i)
prf(“%4d”,*pt);
prf(“\n”);
scanf(“%*c”);
}
for (j=VARIABLES-1;j>0;j--)
(*pt[j]>*pt[j-1]) ;
(j0) ;
for (i=VARIABLES-1;i>=j;i--)
(*pt>*pt[i-1]) ;
t=*pt[j-1];* pt[j-1] =* pt; *pt=t;
for (i=VARIABLES-1;i>j;i--,j)
{ t=*pt[j]; *pt[j] =* pt; *pt=t; }
}
}
从上述问题解决思路方法中最重要原因就是确定某种思路方法来确定所有候选解下面再用个举例来加以介绍说明
【问题】 背包问题
问题描述:有区别价值、区别重量物品n件求从这n件物品中选取部分物品选择方案使选中物品总重量不超过指定限制重量但选中物品价值的和最大
设n个物品重量和价值分别存储于w[ ]和v[ ]中限制重量为tw考虑个n元组(x0x1…xn-1)其中xi=0 表示第i个物品没有选取而xi=1则表示第i个物品被选取显然这个n元组等价于个选择方案用枚举法解决背包问题需要枚举所有选取方案而根据上述思路方法我们只要枚举所有n元组就可以得到问题解
显然每个分量取值为0或1n元组个数共为2n个而每个n元组其实对应了个长度为n 2进制数且这些 2进制数取值范围为0～2n-1因此如果把0～2n-1分别转化为相应 2进制数则可以得到我们所需要2n个n元组
【算法】
maxv=0;
for (i=0;i<2n;i)
{ B[0..n-1]=0;
把i转化为 2进制数存储于B中;
temp_w=0;
temp_v=0;
for (j=0;j<n;j)
{ (B[j]1)
{ temp_w=temp_w+w[j];
temp_v=temp_v+v[j];
}
((temp_w<=tw)&&(temp_v>maxv))
{ maxv=temp_v;
保存该B；