问题与趣味算法.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]162156126252462151535701262101410203556841361015212812345671111111误楚敲坐盯允柞恨旺慑泄隶佰始渠钒盐贼彪虐舰锤徽光选痈君合楼作提勘问题与趣味算法问题与趣味算法算法(1)将矩阵各个元素初始化为0(2)令矩阵第0行均为1,即a[0][j]=1,j=0toM-1(3)令矩阵第0列均为1,即a[i][0]=1,i=0toN-1(4)从第1列至第N-1列的每一列j,计算该列各行上对应的元素a[i][j]的值,i=1toM-1,即a[i][j]=a[i-1][j]+a[i][j-1](5)输出最后的元素a[M-1][N-1]的值CAB戌刃迸声捞快侗褪葵沦代叙干咙兄罗渗猎皱仕均氧翘胶荚奇闺豺骤悔洲叼问题与趣味算法问题与趣味算法求其他元素的值#include""#include"“#defineM6#defineN7voidmain(){ longa[M][N]; inti,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<<"pleaseinputpointC:"<<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)的最短路径。intfun(intx1,inty1,intx2,inty2){ inti,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