《问题与趣味算法课件》由会员分享，可在线阅读，更多相关《问题与趣味算法课件（45页珍藏版）》请在金锄头文库上搜索。
1、C/C+程序设计提高篇,问题求解（趣味算法）,问题求解(趣味算法),教学目的 掌握问题求解的一般步骤,学会用计算机可理解的方式表示问题和求解问题 对数组和函数的知识融会贯通 教学要求 重点是方法的掌握,难度不易太高 教学学时 3学时,案例说明,案例1:最短路径 案例2 :发牌游戏 教学重点:问题求解的一般步骤 案例3:逻辑推理 教学重点:非数值问题的计算机表示 案例4:打印日历 教学重点:程序规范性,自上而下的程序设计方法 案例5:农夫过河 教学重点:自下而上的程序设计方法,问题求解,问题求解的步骤 问题抽象化的描述，问题表示(如何建立模型) 寻找解决方案，问题求解（如何设计算法） 计算机实现
2、过程，效率（如何有效地求解） 现实问题的延伸,例1 最短路径问题(理解问题求解的步骤),求从A点到B点的最短路径有多少条？,A,B,C,建模 用二维矩阵表示aMN表示 任一点的走法axy=ax-1y+axy-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，即a0j=1,j=0 to M-1 (3)令矩阵第0列均为1，即ai0=1,i=0 to N-1 (4) 从
3、第1列至第N-1列的每一列j， 计算该列各行上对应的元素aij的值,i=1 to M-1，即 aij=ai-1j+aij-1 (5) 输出最后的元素aM-1N-1的值,C,A,B,求其他元素的值,#include iostream.h #include iomanip.h“ #define M 6 #define N 7 void main() long aMN; int i,j; for (i=0;i=0;i-)/因假设最下面一行是第0行，故最上面一行为M-1行 for(j=0;j=N-1;j+) coutsetw(5)aij; coutendl; ,初始化,输出结果,代码,问题1 若C点修
4、路,怎么求A到B的最短路径有多少条 coutxy; for (j=1;j=N-1;j+) for (i=1;i=M-1;i+) aij=ai-1j+aij-1; if(x=i ,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+) aij=0; for (i=x1;i=x2;i+) aiy1=1; for (j
5、=y1;j=y2;j+) ax1j=1; for (j=y1+1;j=y2;j+) for (i=x1+1;i=x2;i+) aij=ai-1j+aij-1;,/output for(i=x2;i=x1;i-) for(j=y1;j=y2;j+) coutsetw(5)aij; coutendl; return ax2y2; ,数组a定义为全局的,#include iostream.h #include iomanip.h #define M 6 #define N 7 int aMN; int fun(int x1,int y1,int x2,int y2) int i,j; for (i=
6、x1;i=x2;i+) for(j=y1;j=y2;j+) aij=0; for (i=x1;i=x2;i+) aiy1=1; for (j=y1;j=y2;j+) ax1j=1; for (j=y1+1;j=y2;j+) for (i=x1+1;i=x2;i+) aij=ai-1j+aij-1;,/output for(i=x2;i=x1;i-) for(j=y1;jxy; m=fun(0,0,x,y); coutmendl; n=fun(x,y,M-1,N-1); coutnendl; m=m*n; coutthe total is mendl; ,可进一步讨论,若必须先经过C点,再经过D
7、点,如何修改程序?,例5 发牌,有13张扑克牌1到13,叠成一叠.重复下面动作: 把最上面那张放到最底,再把最上面那张放到最底,抽出一张是1; 把最上面那张放到最底,再把最上面那张放到最底,抽出一张是2; . 把最上面那张放到最底,再把最上面那张放到最底,抽出一张是13; 求13张牌的顺序 答案：11 5 1 8 10 2 6 12 3 9 7 4 13,问题分析,数组placeN(N为牌的张数)放置每张牌,为使牌的序号与数组下标一致,palce0弃用 开始时置数组为全0 从1-13循环查看数组中对应的位置,在第M+1个0处放置1张牌(M为翻几张) 板书放牌的过程,算法设计,要解决哪些问题:
8、1循环查看数组中的位置 可设置计数器Now,指向当前的查看位置，如果nowN,now重置为1 2在第个处放置一张牌 可设置计数器，记录连续出现的的个数,算法流程,开始,初始化数组place，置now=0，i=1,iN?,打印结果，结束,Y,N,J=0,J=M+1？,Y,N,Placenow=i,放置1张牌,now=now+走向下一位置,nowN？,Y,Now=1,Y,Placenow=0?,i+，去发放下一张牌,j+,#include iostream.h #define N 13 #define M 2 int placeN+1; void main() int i,j,now; now=0
9、; /*当前座位的位置*/ for (i=1; i=N ; i+) /* 将第i张牌放在placenow */ j=0;,while (jN) now=1; if (placenow=0) j+; ; placenow=i; cout原来那叠牌的顺序为:endl; for (i=1; i=N; i+) coutplacei ; coutendl; ,原来那叠牌的顺序. 若为N张牌,翻M张呢?,这一算法的思想可以使用到循环报数的游戏中，例如： 有30个小孩，从1-3循环报数，报道3的出列，求小孩的出列顺序。 请尝试编写代码。,谁是窃贼 公安人员审问四名窃贼嫌疑犯。已知，这四人当中仅有一名是窃贼，
10、还知道这四人中每人要么是诚实的，要么总是说谎的。在回答公安人员的问题中：甲说：“乙没有偷，是丁偷的。”乙说：“我没有偷，是丙偷的。”丙说：“甲没有偷，是乙偷的。”丁说：“我没有偷。”请根据这四人的答话判断谁是盗窃者。,例3 逻辑推理,这类问题求解的关键是如何表示成计算机可理解的问题.,*问题分析假设a0、a1、a2、a3分别代表四个人，变量的值为1代表该人是窃贼,为0则不是。这样，可以列出下列条件表达式： 甲说：”乙没有偷，是丁偷的。” a1+a3=1 乙说：“我没有偷，是丙偷有。” a1+a2=1 丙说：“甲没有偷，是乙偷的。” a0+a1=1 丁说：“我没有偷。” a0+a1+a2+a3=
11、1,求解思路,四人中仅有一名是窃贼，且这四个人中的每个人要么说真话，要么说假话，而由于甲、乙、丙三人都说了两句话：“X没偷，Y偷了”，故不论该人是否说谎，他提到的两人中必有一人是小偷。 使用穷举法,分别假定甲、乙、丙、丁是小偷，如能使1,2,3同时成立,即可求解。,例4：打印日历,任意输入1个年份,打印该年的日历 程序演示,打印某年的日历,算法 输入年份 逐月打印日历 打印月头（月份名称） 计算该月有多少天 计算该月1日是星期几 首行留空； 从1号开始，打印每天，到星期六换行,区分是否闰年,/*主函数*/ void main() int year; year=getYearFromUser()
12、; printCalendar(year); /* 获得用户输入的日期*/ int getYearFromUser(void) int year; while(1) coutyear; if(year=1900) return year; coutthe year must be at least 1900endl; ,/*打印日历*/ void printCalendar(int year) int month; for(month=1;month=12;month+) printCalendarMonth(month, year); coutendl; ,输入的日期是1900年之后的,打印
13、一个月的日历,打印表头 这个月的1号是星期几？（前面留多少空） 这个月有多少天？（闰年和非闰年） 一个星期换1行,你认为应该解决哪些问题？,/*打印一个月的日历*/ void printCalendarMonth(int month,int year) int weekday,ndays,day; coutmonthName(month) yearendl; coutSUN MON TUE WED THU FRI SATendl; ndays=monthDays(month,year); weekday=firstDayOfMonth(month,year); IndentFirstLine(
14、weekday); for(day=1;day=ndays;day+) coutday; if (day10) cout ; else cout ;,if (weekday=Saturday) coutendl; weekday=(weekday+1)%7; if (weekday!=Sunday) coutendl; ,打印头部,每个日期占4位，不足补空格,一周换一行,两个月之间留空行,/*返回月份的名称*/ char *monthName(int month) char m1380=Jan,Feb,Mar,Apr,May,Jun,Jul, Aug,Sep,Oct,Nov,Dec; retu
15、rn mmonth-1; /* 根据月份的第一天是星期几确定打印位置*/ void IndentFirstLine(int weekday) int i; for(i=0;iweekday;i+) cout ; ,4个空格,计算一个月（year，month）的1号是星期几？,1900年1月1日是星期一； 计算（year，month,1)与（1900,1,1）间的差距的天数d; d%7余数06，分别代表星期一星期天,注意中间的闰年,/*计算月份的第一天是星期几*/ int firstDayOfMonth(int month,int year) int weekday,i; weekday=Monday; for(i=1900;iyear;i+) weekday=(weekday+365)%7; if (isLeapYear(i) weekday= (weekday+1)%7; for(i=1;imonth;i+) weekday=(weekday+ monthDays(i,year)%7; return weekday; ,/*判断是否闰年*/ bool isLeapYear(int year) if(year % 400=0 |(year %100!=0 ,/*计算一个月有多少天*/ int monthD
