资源预览内容
第1页 / 共51页
第2页 / 共51页
第3页 / 共51页
第4页 / 共51页
第5页 / 共51页
第6页 / 共51页
第7页 / 共51页
第8页 / 共51页
第9页 / 共51页
第10页 / 共51页
亲,该文档总共51页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第十一章 问题求解策略及综合程序设计,武汉大学计算机学院,主讲:谭成予 ,教 材: 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,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: 列号 每行一个皇后,即每个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 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)放置一个皇后以后,与该皇后同列、两个对角线不能再放置皇后? 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+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种可能位置*/ 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。 采用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用二进制数表示为: 01000000100000000010000000000100 #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(“请输入集合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); printf(“集合a和b的差集有%d个元素n”,countset(c); return 0; ,程序源代码,本讲重点,问题定义:编写一个具有加(+)、减(-)、乘(*)、除(/)四则运算功能的计算器程程序,分析:通常一个四则运算的算术表达式采用中辍表示法。 逆波兰表示法:所有运算符都跟在其运算分量的后面。 例如:(1-2)*(4+5) 用逆波兰表示法表示成: 12 4 5 + *,逆波兰表达式计算,如何实现计算器?,读一个运算符,从堆栈中取两个操作数,如何实现计算器?,-1,计算结果为,入栈,如何实现计算器?,-1,-1,读到运算符从堆栈中取两个操作数,如何实现计算器?,-1,计算4+5,结果入栈,如何实现计算器?,-1,读到运算符,从堆栈中取两个操作数,如何实现计算器?,-,计算9*-1结果-9入栈,如何实现计算器?,伪代码如下: while(下一个运算符或运算分量不是文件结束指示符EOF) if(是运算分量) 将该运算分量压入堆栈中 else if(是运算符) 弹出所需数目的运算分量 执行运算 将结果压入堆栈 else if(是换行符) 弹出并打印栈顶的值 else 显示出错信息,逆波兰表达式计算,入栈和出栈函数分别为push()和pop() #define 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是小数点.)读取小数部分,读取到非数字字符为止,并将该数字字符存放到变量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=.)/*读取小数部分*/ while (isdigit(s+i=c=getch(); 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);,程序源
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号