典型算法分析 典型算法算法设计技术
下面是好好范文网小编收集整理的典型算法分析 典型算法算法设计技术，仅供参考，欢迎大家阅读！
虽然设计算法尤其是设计好的算法是一件困难的工作，但是设计算法也不是没有方法可循，人们经过几十年的探讨，总结和积累了许多行之有效的方法，了解和掌握这些方法会给我们解决问题提供一些思路。经常采用的算法设计技术有：迭代法、穷举搜索法、递推法、递归法、贪婪法、回溯法、分治法、动态规划法、并行算法等，了解和借鉴这些算法设计的方法，有助于解决类似程序设计问题。主要介绍迭代法、穷举搜索法、递推法、递归法、回溯法、贪婪法这六种算法。
1 迭代法
迭代法是用来解决数值计算问题中的非线形方程(组)求解或最优解的一种算法，以求方程(组)的近似根。
迭代法的基本思想是：从某个点出发，通过某种方式求出下一个点，此点应该离要求解的点（方程的解）更近一步，当两者之差接近到可以接受的精度范围时，就认为找到了问题的解。简单迭代法每次只能求出方程的一个解，需要人工先给出近似初值。
例1用迭代法求某正数a的平方根。已知求平方根的迭代公式为：x1 = 1/2 (x0 + a/x0)
用迭代法编写的程序如下：
#include"math.h"
main()
{ float a,x0,x1;
printf("/n请输入正数 a: ");
scanf("%f", &a);
if(a<0)
printf("error !/n");
else
{ x0=a/2;
x1=(x0+a/x0)/2;
do
{ x0=x1;
x1=(x0 +a/x0)/2;
}while (fabs(x0-x1)>1e-5);
printf("sqrt(%f)=%f/n",a,x1);
2 穷举搜索法
穷举搜索法又称为枚举法，按某种顺序对所有的可能解逐个进行验证，从中找出符合条件要求的作为问题的解。此算法通常用多重循环实现，对每个变量的每个值都测试是否满足所给定的条件，是则找到了问题的一个解。这种算法简单易行，但只能用于解决变量个数有限的场合。
例2一张100元钞票换成面值分别为5元、1元、0.5元的三种钞票共100张，每种钞票至少1张，则每种面值的钞票各多少张？有哪几种可能的兑换方案？
用穷举搜索法编写的程序如下：
#include"stdio.h"
main()
{ int i,j,k=0;
for(i=1;i<=19;i++)
for(j=1;j<=94-i*5;j++)
if (5*i+1*j+0.5*(100-i-j)==100)
{ k++ ;
printf("5元：%d, 1元：=%d, 0.5元：%d ", i,j,100-i-j);
printf("共有%d种兑换方案/n",k);
3 递推法
利用问题本身具有的递推性质或递推公式求得问题的解的一种算法，从初始条件出发，逐步推出所需的结果。但是有些问题很难归纳出一组简单的递推公式。
例3编写程序，用递推法计算斐波那契（Fibonacci）级数的第n项。斐波那契级数数列为：0，1，1，2，3，5，8，13，21，…，即：F=0，F(1)=1，当n>时，F(n)=F(n-1)+F(n-2)。
用递推法编写的程序如下：
#include"stdio.h"
long fun1(int n)
{ long f0=0,f1=1,f,i;
if (n==0) return 0;
if (n==1) return 1;
for(i=2;i<=n;i++)
{ f=f0+f1;
f0=f1;
f1=f;
return (f);
void main()
{ int n;
scanf("%d",&n) ;
printf("f(%d)=%ld/n",n,fun1(n));
4 递归法
递归法的思想是：将N＝n时不能得出解的问题，设法递归（压栈）转化为求n－1，n－2，……的问题，一直到N＝0或1的情况，由于初始情况的解可以给出或方便得到，因此开始层层出栈得到N＝2、3、……、n时的解，得到最终结果。用递归法写出的程序简单易读，但效率不如递推法高。任何可以用递推法解决的问题，可以很方便地用递归法解决，但是许多用递归法解决的问题，不能用递推法解决。
例4用递归法计算 n! 。
用递归法编写的程序如下：
#include"stdio.h"
int fun int n)
{ int result;
if(n==0 || n==1)
return 1;
else
{ result=n*fun(n-1);
return? result;
void main()
{ int n;
scanf("%d",&n);
printf("%d! = %d/n",n,fun(n));
例5用递归法解决“背包问题”， “背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N 件物品，其重量分别为w1，w2，...，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S 。
用递归法编写的程序如下：
#include"stdio.h"
#define N 7
#define S 15
int w[N+1]={0,1,4,3,4,5,2,7};
int knap(int s,int n)
{ if(s==0) return 1;
if(s<0 || (s>0 && n<1)) return 0;
if (knap(s-w[n],n-1))
{ printf("%4d",w[n]);
return 1;
return knap(s,n-1);
main()
{ if(knap(S,N))
printf("OK!/n");
else
printf("NO!/n");
5 回溯法
回溯法又称为试探法，在用某种方法找出解的过程中，若中间项结果满足所解问题的条件，则一直沿这个方向搜索下去，直到无路可走或无结果，则开始回溯，改变其前一项的方向或值继续搜索。若其上一项的方向或值都已经测试过，还无路可走或无结果，则再继续回溯到更前一项，改变其方向或值继续搜索。若找到了一个符合条件的解，则停止或输出这个结果后继续搜索；否则继续回溯下去，直到回溯到问题的开始处（不能再回溯），仍没有找到符合条件的解，则表示此问题无解或已经找到了全部的解。用回溯法可以求得问题的一个解或全部解。
例6著名的四色定理指出任何平面区域图均可用四种颜色着色,使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过四种颜色的着色方案。程序中用1～4表示四种颜色。要着色的N个区域用0～N－1编号,区域相邻关系用adj矩阵表示，矩阵的i行j列的元素为1 ，表示区域i与区域j相邻；矩阵的i行j列的元素为0，表示区域i与区域j不相邻。数组 color用来存储着色结果，color[i]的值为区域i所着颜色。
用回溯法编写的程序如下：
#include"stdio.h"
#define N 10
void output(int color)? /* 输出一种着色方案 */
{ int i;
for(i=0;i<N;i++)
printf("%4d", color[i]);
printf("/n");
int back( int *ip ,int color ) /* 回溯 */
{ int c=4;
while(c==4)
{ if (*ip<=0) return 0;
--(*ip);
c=color[*ip];
color[*ip]=-1;
return c ;
/* 检查区域 i，对 c 种颜色的可用性 */
int colorOK(int i,int c,int adj[N],int color)
{ int j;
for(j=0;j<i;j++)
if (adj[i][j]!=0 && color[j]==c) return 0;
return 1;
/* 为区域i选一种可着的颜色 */
int select(int i,int c,int adj[N],int color)
{ int k;
for(k=c;k<=4;k++)
if(colorOK(i,k,adj,color)) return k;
return 0;
int coloring(int adj[N]) /* 寻找各种着色方案 */
{ int color[N],i,c,cnt;
for(i=0;i<N;i++)
color[i]=-1;
i=c=0;
cnt=0 ;
while(1)
{ if((c=select(i,c+1,adj,color))==0)
{ c=back(&i,color);
if(c==0) return cnt;
else
{ color[i]=c;
i++;
if(i==N)
{ output(color);
++cnt;
c=back(&i,color);
else c = 0 ;
void main()
{ int adj[N][N]=
{0,1,0,1,1,1,1,1,1,1},
{1,0,1,1,0,1,1,1,1,0},
{0,1,0,1,0,1,1,0,1,1},
{1,1,1,0,1,1,0,0,1,1},
{1,0,0,1,0,1,0,0,0,0},
{1,1,1,1,1,0,1,0,0,1},
{1,1,1,0,0,1,0,0,1,0},
{1,1,0,0,0,0,0,0,1,1},
{1,1,1,1,0,0,1,1,0,1},
{1,0,1,1,0,1,0,1,1,0}
printf("共有%d组解./n",coloring(adj));
6 贪婪法
贪婪法又称为登山法，指从问题的初始解出发，一步一步接近给定的目标，并尽可能快地去逼近更好的解。贪婪法是一种不追求最优解，只希望最快得到较为满意解的方法。贪婪法不需要回溯，只能求出问题的某个解，不能求出所有的解。
平时购物找钱时，为使找回的零钱的数量最少，不考虑找零钱的所有各种方案，而是从最大面额的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种，这就是使用了贪婪法。例如50元找成20元、20元、10元。
例7编写程序，实现人民币的找零：任何一张面额的纸币都找成比它的面额小的纸币，最小单位是元。采用贪婪法求解，首先分解成面额值尽可能大的小额纸币。
用贪婪法编写的程序如下：
#include"stdio.h"
#define? N 20
int find(int n,int m,int *d,int c,int *pd)
{ int r ;
if(n==0) return 0;
if(m==0 || c==0 ) return -1;
if(n<*d) return find(n,m,d+1,c-1,pd);
else
{ *pd=*d ;
r=find(n-*d,m-1,d,c,pd+1);
if (r>=0) return r+1;
return -1;
void main()
{ int n,m,k,i,p[N];
int d[7]={100,50,20,10,5,2,1};
printf (" 请输入钱数和找零最大张数n , m: " );
scanf("%d%d",&n,&m);
for(i=0;i<7;i++)
if (n>d[i]) break;
k=find(n,m,&d[i],7-i,p);
if (k<=0) printf("找不开！/n");
else
{ printf("%d=%d",n,p[0]);
for(i=1;i<k;i++) printf("+%d",p[i]);
printf("/n");
转自：
