《十一章问题求解策略及综合程序设计知识分享》由会员分享，可在线阅读，更多相关《十一章问题求解策略及综合程序设计知识分享（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,(3) j=3 i=5，6，7， 8 i=5,Q
2、,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无法选取回退一步,Q,j: 行号 i: 列号 每行一个皇后,即
3、每个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=5
4、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+
5、1)放置一个皇后以后，与该皇后同列、两个对角线不能再放置皇后？ 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步定义成一个递归函数try void try(int i); 该函数作用是放置第i+1个（i=0,1，7）皇后(第i+1行皇后 放置）： for(j=0;j8;j+) /*每个皇后都有8种可能位置*/ 2-1 如果不存在位置冲突，则 2-2 位置（i+1,j
6、+1）上放置皇后 2-3 如果第8个皇后还没有放置好，则 继续放置下一个皇后 /*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种可
7、能位置*/ for (j=0;j8;j+) if (bj=0) ,int main() int k;/*数据初始化*/ 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。 采
8、用unsigned long 类型表示集合将unsigned long的32位从低到高位分别编号1、2到32，如果元素n在集合a中，则将a的第n位置1，否则置0。 例，集合1，2，32表示为二进制数10000000000000000000000000000011。 为什么定义成unsigned类型而不是long 类型？ 因为考虑到在计算集合的势时需要用到位运算的右移运算符，为 保证在右移时长整数的最高位始终补0所致,算法： 假设集合a为1，2，14，则a用二进制数表示为： 00000000000000000010000000000011 集合b为3,14,24,31，则b用二进制数表示为： 0
9、1000000100000000010000000000100 #define UNION(x,y) (x)|(y)/*计算并集*/ #define JIAOJI(x,y) (x) while(n) if(n ,/*输出集合*/ void printset(unsigned long n) int i=1; printf(“); while(n) if(n ,程序源代码,int main(void) unsigned long a,b,c; printf(“请输入集合a:”); a=inputset(); printf(“集合a有%d个元素n”,countset(a); printf(“请输入
10、集合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的交集有%d个元素n”,countset(c); printset(c); c=DIFFERENCE(a,b); printf(“集合a 和b 的差集为：”); printset(c); prin
11、tf(“集合a和b的差集有%d个元素n”,countset(c); return 0; ,程序源代码,本讲重点,问题定义：编写一个具有加（+）、减（-）、乘（*）、除（/）四则运算功能的计算器程程序,分析：通常一个四则运算的算术表达式采用中辍表示法。 逆波兰表示法：所有运算符都跟在其运算分量的后面。 例如：（1-2）*（4+5） 用逆波兰表示法表示成： 12 4 5 + *,逆波兰表达式计算,如何实现计算器？,读一个运算符，从堆栈中取两个操作数,如何实现计算器？,-1,计算结果为，入栈,如何实现计算器？,-1,-1,读到运算符从堆栈中取两个操作数,如何实现计算器？,-1,计算4+5，结果入栈,
12、如何实现计算器？,-1,读到运算符，从堆栈中取两个操作数,如何实现计算器？,-,计算9*-1结果-9入栈,如何实现计算器？,伪代码如下： while(下一个运算符或运算分量不是文件结束指示符EOF) if(是运算分量) 将该运算分量压入堆栈中 else if(是运算符) 弹出所需数目的运算分量 执行运算 将结果压入堆栈 else if(是换行符) 弹出并打印栈顶的值 else 显示出错信息,逆波兰表达式计算,入栈和出栈函数分别为push()和pop() #define MAXVAL 100 /*堆栈的最大长度*/ int sp=0; /*栈顶指针位置*/ double valMAXVAL; /
13、*堆栈*/ /*入栈函数：将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是小数点.)读取小数部分，读取到非数字字符为止，并将该数字字符存放到变量c中 si=0; if
14、(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=.)/*读取小数部分*/ while (isdigit(s+i=c=ge
15、tch(); si=0; if (c!=EOF) ungetch(c); return NUMBER; ,程序源代码,#define BUFSIZE 100 char 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”); else bufbufp+=c; ,程序源代码,#include #include /*for atof()*/ #define MAXOP 100 /*运算符或者操作数的最大长度*/ #deifne NUMBER 0 /*读取到一个操作数的标志*/ int getop(char ); void push(double); double pop(void);,程序源
