第一章 算法的基本概念 徐浩.ppt

数理学院徐浩
第一章算法的基本概念
引言
算法的定义和特征
算法的定义:Algorithm,解决一个特定问题的一组有穷规则的集合
算法的特征,
,算法必须在执行有限步后终止,运算的时间合理
,每一步都必须有明确的定义
,必须有0个或者多个输入
,必须有1个或者多个输出
,算法中有待实现的运算都是基本运算
好的算法是如何设计出来的?
#include ""
#include ""
main()
{
int i,j;
printf("first num is:");
scanf("%d",&i);
printf("second num is:");
scanf("%d",&j);
printf("the result is:%d",euclid(i,j));
getch();
}
int euclid(int m,int n)
{
int r;
do{
r=m%n;
m=n;
n=r;
}while(r);
return m;
}
一个简单的算法问题:欧几里德问题,求二数的最大公因数
最简单的算法设计方法:穷举法
:百鸡问题
张丘建在算经中提出:公鸡5元每只,母鸡3元每只,小鸡3只1元,用100元买100只鸡,各自有多少只.
令a为公鸡只数,b为母鸡只数,c为小鸡只数,可得如下约束方程:
只要使用3重循环就可以实现穷举法求结果,程序如下:
#include ""
#include ""
main()
{
int n,h;
printf("the total num and money is:") ;
scanf("%d,%d",&n,&h);
chicken_question(n,h);
getch();
}
int chicken_question(int n,int h)
{
int k, a,b,c;
int g[10],m[10],j[10];
k=0;
for(a=0;a<=n;a++){
for(b=0;b<=n;b++){
for(c=0;c<=n;c++) {
if((a+b+c==n)&&(5*a+3*b+c/3==h)&&(c%3==0))
{
g[k]=a;m[k]=b;j[k]=c;
printf("the cock num is:%d,the hen num is:%d,the chicken num is:%d\n",a,b,c);
k++;
}
}}}
if(k==0) printf("no result");
else
printf("the total result num is:%d",k);
}
上述的三重循环产生的执行时间,取决于循环体开始的一行,每一重循环将执行(n+1)次
执行总次数将是(n+1)(n+1)(n+1)
考虑到只能买到n/5只公鸡,n/3只母鸡,将算法进行改进:
int chicken_question_improve(int n,int h)
{
int k, a,b,c,i,j;
int g[10],m[10],s[10];
k=0;
i=n/5;
j=n/3;
for(a=0;a<=i;a++){
for(b=0;b<=j;b++){
c=n-a-b;
if((5*a+3*b+c/3==h)&&(c%3==0))
{
g[k]=a;m[k]=b;s[k]=c;
printf("the cock num is:%d,the hen num is:%d,the chicken num is:%d\n",a,b,c);
k++;
}
}}
if(k==0) printf("no result");
else
printf("the total result num is:%d",k);
}
计算一下执行次数是多少?
(n/5+1)*(n/3+1)是整个执行次数
货郎担问题:售货员到若干个城市去售货,已知各个城市之间的距离,求一个总路程最短,经过每个城市,最后回来出发点的路线。(如果是规定一个城市作为始发站,结果如何?)
求最短路径的哈密尔顿回路问题,数据结构是无向加权图G=<V,E>,V是顶点集合,E是距离集合,如图所示,从1号城市出发,获得最短路径的线路图
例:
穷举法来解上述问题,是将所有路线都走一遍。从中找出最短路径来。程序如下(使用了伪代码):
Void salesman_problem(int n,float &min,int t[ ],float c[ ][ ])
{
int p[n],i=1;
float