《问题与趣味算法课件》由会员分享,可在线阅读,更多相关《问题与趣味算法课件(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