问题与趣味算法.ppt.ppt

C/C++程序设计提高篇问题求解(趣味算法)问题求解(趣味算法)?教学目的?掌握问题求解的一般步骤,学会用计算机可理解的方式表示问题和求解问题?对数组和函数的知识融会贯通?教学要求?重点是方法的掌握,难度不易太高?教学学时? 3学时案例说明?案例1:最短路径?案例2 :发牌游戏?教学重点:问题求解的一般步骤?案例3:逻辑推理?教学重点:非数值问题的计算机表示?案例4:打印日历?教学重点:程序规范性,自上而下的程序设计方法?案例5:农夫过河教学重点:自下而上的程序设计方法问题求解问题求解的步骤?问题抽象化的描述,问题表示(如何建立模型) ?寻找解决方案,问题求解(如何设计算法)?计算机实现过程,效率(如何有效地求解)?现实问题的延伸例1 最短路径问题(理解问题求解的步骤)求从A点到B点的最短路径有多少条?ABC?建模?用二维矩阵表示a[M][N]表示?任一点的走法a[x][y]=a[x-1][y]+a[x][y-1]1 6 21 56 126 252 4621 5 15 35 70 126 2101 4 10 20 35 56 841 3 6 10 15 21 281 2 3 4 5 6 71 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]的值CAB求其他元素的值#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];//outputfor(i=x2;i>=x1;i--){ for(j=y1;j<=y2;j++)cout<<setw(5)<<a[i][j];cout<<endl;}return a[x2][y2];}数组a定义为全局的