问题求解与趣味算法.ppt

C/C++程序设计提高篇
问题求解(趣味算法)
问题求解(趣味算法)
教学目的
掌握问题求解的一般步骤,学会用计算机可理解的方式表示问题和求解问题
对数组和函数的知识融会贯通
教学要求
重点是方法的掌握,难度不易太高
教学学时
3学时
案例说明
案例1:最短路径
案例2 :发牌游戏
教学重点:问题求解的一般步骤
案例3:逻辑推理
教学重点:非数值问题的计算机表示
案例4:打印日历
教学重点:程序规范性,自上而下的程序设计方法
案例5:农夫过河
教学重点:自下而上的程序设计方法
问题求解
问题求解的步骤
问题抽象化的描述,问题表示(如何建立模型)
寻找解决方案,问题求解(如何设计算法)
计算机实现过程,效率(如何有效地求解)
现实问题的延伸
例1 最短路径问题(理解问题求解的步骤)
求从A点到B点的最短路径有多少条?
A
B
C
建模
用二维矩阵表示a[M][N]表示
任一点的走法a[x][y]=a[x-1][y]+a[x][y-1]
1 6 21 56 126 252 462
1 5 15 35 70 126 210
1 4 10 20 35 56 84
1 3 6 10 15 21 28
1 2 3 4 5 6 7
1 1 1 1 1 1 1
算法
(1)将矩阵各个元素初始化为0
(2)令矩阵第0行均为1,即a[0][j]=1,j=0 to M-1
(3)令矩阵第0列均为1,即a[i][0]=1,i=0 to N-1
(4) 从第1列至第N-1列的每一列j,
计算该列各行上对应的元素a[i][j]的值,i=1 to M-1,即
a[i][j]=a[i-1][j]+a[i][j-1]
(5) 输出最后的元素a[M-1][N-1]的值
C
A
B
求其他元素的值
#include ""
#include "“
#define M 6
#define N 7
void main()
{ long a[M][N];
int i,j;
for (i=0;i<=M-1;i++)
{ for(j=0;j<=N-1;j++)
a[i][j]=0;
}
for (i=0;i<=M-1;i++)
a[i][0]=1;
for (j=0;j<=N-1;j++)
a[0][j]=1;
for (j=1;j<=N-1;j++)
{ for (i=1;i<=M-1;i++)
a[i][j]=a[i-1][j]+a[i][j-1];
}
for (i=M-1;i>=0;i--)//因假设最下面一行是第0行,故最上面一行为M-1行
{ for(j=0;j<=N-1;j++)
cout<<setw(5)<<a[i][j];
cout<<endl;
}
}
初始化
输出结果
代码
问题1
若C点修路,怎么求A到B的最短路径有多少条
cout<<"please input point C:"<<endl;
cin>>x>>y;
for (j=1;j<=N-1;j++)
{ for (i=1;i<=M-1;i++)
{ a[i][j]=a[i-1][j]+a[i][j-1];
if(x==i && y==j)
a[i][j]=0;
}
}
C点的走法置为0
问题2 如果必须经过C点呢?
需求解A-C的路径和C-B的路径
编写函数fun(x1,y1,x2,y2)求起点(x1,y1)到终点(x2,y2)的最短路径。
int fun(int x1,int y1,int x2,int y2)
{ int i,j;
for (i=x1;i<=x2;i++)
{ for(j=y1;j<=y2;j++)
a[i][j]=0;
}
for (i=x1;i<=x2;i++)
a[i][y1]=1;
for (j=y1;j<=y2;j++)
a[x1][j]=1;
for (j=y1+1;j<=y2;j++)
for (i=x1+1;i<=x2;i++)
a[i][j]=a[i-1][j]+a[i][j-1];
//output
for(i=x2;i>=x1;i--)
{ for(j=y1;j<=y2;j++)
cout<<setw(5)<<a[i][j];
cout<<endl;
}
return a[x2][y2];
}
数组a定义为全局的