《问题求解策略及综合程序设计.ppt》由会员分享，可在线阅读，更多相关《问题求解策略及综合程序设计.ppt（51页珍藏版）》请在三一办公上搜索。
1、第十一章 问题求解策略及综合程序设计,武汉大学计算机学院,主讲：谭成予,教 材:C程序设计导论,本讲重点,八皇后问题,问题定义：八皇后问题是一个著名而古老的问题。该问题要求在88的国际象棋棋盘上放置8个皇后，使得它们不能相互攻击，即任意两个皇后不能处于同一行、同一列或者同一斜线上。问有多少种放置的方案？,Q,j:行号 i:列号每行一个皇后,即每个j值对应一个i值。试探法,(1)j=1 i=1,Q,j:行号 i:列号每行一个皇后,即每个j值对应一个i值。试探法,(1)j=1 i=1,(2)j=2 i=3，4，8 i=3,Q,Q,j:行号 i:列号每行一个皇后,即每个j值对应一个i值。试探法,(1
2、)j=1 i=1,(2)j=2 i=3，4，8 i=3,Q,(3)j=3 i=5，6，7，8 i=5,Q,Q,j:行号 i:列号每行一个皇后,即每个j值对应一个i值。试探法,(1)j=1 i=1,(2)j=2 i=3，4，8 i=3,Q,(3)j=3 i=5，6，7，8 i=5,Q,(4)j=4 i=2，7，8 i=2,Q,Q,j:行号 i:列号每行一个皇后,即每个j值对应一个i值。试探法,(1)j=1 i=1,(2)j=2 i=3，4，8 i=3,Q,(3)j=3 i=5，6，7，8 i=5,Q,(4)j=4 i=2，7，8 i=2,(5)j=5 i=4，8 i=4,Q,(6)j=6 i无法
3、选取回退一步,Q,j:行号 i:列号每行一个皇后,即每个j值对应一个i值。试探法,(1)j=1 i=1,(2)j=2 i=3，4，8 i=3,Q,(3)j=3 i=5，6，7，8 i=5,Q,(4)j=4 i=2，7，8 i=2,Q,(6)j=6 i无法选取回退一步,(5)j=5 i=4，8 i=8,Q,j:行号 i:列号每行一个皇后,即每个j值对应一个i值。试探法,(1)j=1 i=1,(2)j=2 i=3，4，8 i=3,Q,(3)j=3 i=5，6，7，8 i=5,Q,(4)j=4 i=2，7，8 i=2,(5)j=5 i=4，8 i=4,Q,(6)j=6 i无法选取回退一步,(5)j=
4、5 i=4，8 i=8,(6)j=6 i无法选取回退一步,(4)j=4 i=2，7，8 i=7,依次类推,Q,j:行号 i:列号每行一个皇后,即每个j值对应一个i值。试探法,(1)j=1 i=1,(2)j=2 i=3，4，8 i=3,Q,(3)j=3 i=5，6，7，8 i=5,Q,Q,(4)j=4 i=2，7，8 i=7,依次类推,如何表示一具体方案,如何表示一具体方案？int queen8;queenj j=0,1,2,7;表示第j+1行皇后放在第queenj+1列上,即（queeni+1,j+1)放置一个皇后。,皇后放置问题,如何表示（queeni+1,j+1)放置一个皇后以后，与该皇后
5、同列、两个对角线不能再放置皇后？int b8,c15,d15;bj j=0,1,2,7;表示第j+1列上已有皇后如果第i+1行、第j+1列上放置一个皇后，则bj=1 第j+1列上已有皇后ci+j 主对角线上已有皇后di-j+7 从对角线已有皇后,算法描述,初始化棋盘为第1个皇后选择合适位置,第2步定义成一个递归函数tryvoid try(int i);该函数作用是放置第i+1个（i=0,1，7）皇后(第i+1行皇后放置）：for(j=0;j8;j+)/*每个皇后都有8种可能位置*/2-1 如果不存在位置冲突，则 2-2 位置（i+1,j+1）上放置皇后 2-3 如果第8个皇后还没有放置好，则
6、继续放置下一个皇后/*try(i+1)调用*/否则 输出当前解 2-4 释放位置（i+1,j+1）,#include int queen8,b8,c15,d15;int queennum=0;/*当前解的序号*/*找到一个解后，输出当前解*/void print()int k;queennum+;printf(%d:,queennum);for(k=0;k8;k+)printf(t%d,queenk);printf(n);,程序源代码,void try(int i)int j;/*每个皇后都有8种可能位置*/for(j=0;j8;j+)if(bj=0),int main()int k;/*数据
7、初始化*/for(k=0;k15;k+)if(k8)bk=0;ck=0;dk=0;try(0);/*从第1个皇后开始放置*/return 0;,主函数,本讲重点,集合运算,问题定义：假定一个全集合中有1、2到32这32个元素，任意给出两个集合，求它们的并集、交集和差集，并计算各个集合的势（即集合中元素的个数）。,数据结构,集合表示方法有：位向量、数组和树等本例使用位向量表示集合。一个位向量（1：n）表示集合，如果元素i在集合U中，则置SET(i)=1，否则为0。采用unsigned long 类型表示集合将unsigned long的32位从低到高位分别编号1、2到32，如果元素n在集合a中，
8、则将a的第n位置1，否则置0。例，集合1，2，32表示为二进制数10000000000000000000000000000011。为什么定义成unsigned类型而不是long 类型？因为考虑到在计算集合的势时需要用到位运算的右移运算符，为保证在右移时长整数的最高位始终补0所致,算法：假设集合a为1，2，14，则a用二进制数表示为：00000000000000000010000000000011集合b为3,14,24,31，则b用二进制数表示为：01000000100000000010000000000100#define UNION(x,y)(x)|(y)/*计算并集*/#define JI
9、AOJI(x,y)(x)&(y)/*计算交集*/差集运算定义为：#define DIFFERENCE(x,y)(x)(x)&(y)/*注意：先计算x&y，即x,y交集*/,算法,#include#define UNION(x,y)(x)|(y)/*计算并集*/#define JIAOJI(x,y)(x),程序源代码,/*计算集合的势*/int countset(unsigned long n)int num=0;while(n)if(n,/*输出集合*/void printset(unsigned long n)int i=1;printf(“);while(n)if(n,程序源代码,int
10、main(void)unsigned long a,b,c;printf(“请输入集合a:”);a=inputset();printf(“集合a有%d个元素n”,countset(a);printf(“请输入集合b:”);b=inputset();printf(“集合b有%d个元素n”,countset(b);c=UNION(a,b);printf(“集合a 和b 的并集为：”);printset(c);printf(“集合a和b的并集有%d个元素n”,countset(c);c=JIAOJI(a,b);,程序源代码,printf(“集合a 和b 的交集为：”);printf(“集合a和b的交
11、集有%d个元素n”,countset(c);printset(c);c=DIFFERENCE(a,b);printf(“集合a 和b 的差集为：”);printset(c);printf(“集合a和b的差集有%d个元素n”,countset(c);return 0;,程序源代码,本讲重点,问题定义：编写一个具有加（+）、减（-）、乘（*）、除（/）四则运算功能的计算器程程序,分析：通常一个四则运算的算术表达式采用中辍表示法。逆波兰表示法：所有运算符都跟在其运算分量的后面。例如：（1-2）*（4+5）用逆波兰表示法表示成：12 4 5+*,逆波兰表达式计算,如何实现计算器？,读一个运算符，从堆栈
12、中取两个操作数,如何实现计算器？,-1,计算结果为，入栈,如何实现计算器？,-1,-1,读到运算符从堆栈中取两个操作数,如何实现计算器？,-1,计算4+5，结果入栈,如何实现计算器？,-1,读到运算符，从堆栈中取两个操作数,如何实现计算器？,-,计算9*-1结果-9入栈,如何实现计算器？,伪代码如下：while(下一个运算符或运算分量不是文件结束指示符EOF)if(是运算分量)将该运算分量压入堆栈中elseif(是运算符)弹出所需数目的运算分量执行运算将结果压入堆栈elseif(是换行符)弹出并打印栈顶的值else显示出错信息,逆波兰表达式计算,入栈和出栈函数分别为push()和pop()#d
13、efine MAXVAL 100/*堆栈的最大长度*/int sp=0;/*栈顶指针位置*/double valMAXVAL;/*堆栈*/*入栈函数：将f压入堆栈*/void push(double f)if(sp0)return val-sp;elseprintf(“error:stack emptyn”);return 0.0;,入栈和出栈函数,功能：读取操作数或运算符,伪代码如下：跳过前导空格，将读取到的第一个非空格字符存入变量c中；if(变量c不是数字字符或者小数点)终止函数执行，返回c的取值if(c是数字字符)读取整数部分，读取到非数字字符为止，并将该数字字符存放到变量c中 if(c
14、是小数点.)读取小数部分，读取到非数字字符为止，并将该数字字符存放到变量c中si=0;if(c不是文件结束标记EOF)c存入缓冲区中;返回NUMBER;,Getop函数,#include int getch(void);void ungetch(int);/*getop函数：读取操作数或运算符*/int getop(char s)int i,c;/*跳过前导空格*/while(s0=c=getch()=|c=t);s1=0;if(!isdigit(c),i=0;if(isdigit(c)/*读取整数部分*/while(isdigit(s+i=c=getch();if(c=.)/*读取小数部分*
15、/while(isdigit(s+i=c=getch();si=0;if(c!=EOF)ungetch(c);return NUMBER;,程序源代码,#define BUFSIZE 100char bufBUFSIZE;/*ungetch的缓冲区*/int bufp=0;/*缓冲区顶部指针*/int getch(void)return(buf0)?buf-bufp:getchar();void ungetch(int c)if(bufp=BUFSIZE)printf(“ungetch:too many charactersn”);elsebufbufp+=c;,程序源代码,#include#
16、include/*for atof()*/#define MAXOP 100/*运算符或者操作数的最大长度*/#deifne NUMBER 0/*读取到一个操作数的标志*/int getop(char);void push(double);double pop(void);,程序源代码,int main()int type;double op2;char sMAXOP;while(type=getop(s)!=EOF)switch(type)case NUMBER:push(atof(s);break;case+:push(pop()+pop();break;case-:op2=pop();p
17、ush(pop()-op2);break;case*:push(pop()*pop();break;case/:op2=pop();if(op2!=0.0)push(pop()/op2);else printf(“error:zero divisorn”);break;case n:printf(“t%8gn”,pop();break;default:printf(“error:unknown command%sn”,s);return 0;,本讲重点,五子棋游戏,一般来说,开发一个软件要经过以下步骤:,确定软件的功能,定义核心数据结构,对整个软件进行功能模块划分,编写程序实现各功能模块,对源程序进行编译和调试,形成软件产品,五子棋棋盘,两位玩家交替行棋,五子相连判定赢棋,功能分析,定义char gChessBoard1919;表示棋盘,棋盘上每个交叉点有三种状态,当前光标位置表示,struct point int x;int y;,定义核心数据结构,程序的模块划化,定义核心数据结构,初始化,接收按键,移动光标,落子与判定胜负,main()函数,程序中用到的库函数介绍,程序的编制的细节,bioskey,textmode,clrscr,putch,cputs,gotoxy,textcolor,delay,sound 与nosound,程序用到的库函数,用户手册,THE END,
