问题求解策略及综合程序设计方案ppt课件

1、主讲：谭成予主讲：谭成予n a d i n e t a n 1 6 3教教 材材 : C 程 序 设 计 导 论程 序 设 计 导 论集合运算集合运算逆波兰表达式计算逆波兰表达式计算 五子棋游戏程序五子棋游戏程序八皇后问题八皇后问题八皇后问题八皇后问题问题定义：八皇后问题是一个著名而古老的问题。该问题要求在问题定义：八皇后问题是一个著名而古老的问题。该问题要求在88的国际象的国际象棋棋盘上放置棋棋盘上放置8个皇后，使得它们不能相互攻击，即恣意两个皇后不能处于同个皇后，使得它们不能相互攻击，即恣意两个皇后不能处于同一 行 、 同 一 列 或 者 同 一 斜 线 上 。 问 有 多 少 种 放 置

2、 的 方 案 ？一 行 、 同 一 列 或 者 同 一 斜 线 上 。 问 有 多 少 种 放 置 的 方 案 ？QQQQQQQQQijQijj: 行号 i: 列号每行一个皇后,即每个j值对应一个i值。试探法(1) j=1 i=1Qijj: 行号 i: 列号每行一个皇后,即每个j值对应一个i值。试探法(1) j=1 i=1(2) j=2 i=3，4， 8 i=3QQijj: 行号 i: 列号每行一个皇后,即每个j值对应一个i值。试探法(1) j=1 i=1(2) j=2 i=3，4， 8 i=3Q(3) j=3 i=5，6，7， 8 i=5QQijj: 行号 i: 列号每行一个皇后,即每个j值

3、对应一个i值。试探法(1) j=1 i=1(2) j=2 i=3，4， 8 i=3Q(3) j=3 i=5，6，7， 8 i=5Q(4) j=4 i=2，7， 8 i=2QQijj: 行号 i: 列号每行一个皇后,即每个j值对应一个i值。试探法(1) j=1 i=1(2) j=2 i=3，4， 8 i=3Q(3) j=3 i=5，6，7， 8 i=5Q(4) j=4 i=2，7， 8 i=2(5) j=5 i=4， 8 i=4Q(6) j=6 i无法选取回退一步Qijj: 行号 i: 列号每行一个皇后,即每个j值对应一个i值。试探法(1) j=1 i=1(2) j=2 i=3，4， 8 i=3

4、Q(3) j=3 i=5，6，7， 8 i=5Q(4) j=4 i=2，7， 8 i=2Q(6) j=6 i无法选取回退一步(5) j=5 i=4， 8 i=8Qijj: 行号 i: 列号每行一个皇后,即每个j值对应一个i值。试探法(1) j=1 i=1(2) j=2 i=3，4， 8 i=3Q(3) j=3 i=5，6，7， 8 i=5Q(4) j=4 i=2，7， 8 i=2(5) j=5 i=4， 8 i=4Q(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依次类推Qijj: 行号 i: 列号

5、每行一个皇后,即每个j值对应一个i值。试探法(1) j=1 i=1(2) j=2 i=3，4， 8 i=3Q(3) j=3 i=5，6，7， 8 i=5QQ(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)放置一个皇后。放置一个皇后。QQQQQQQQ皇后放置问题皇后放置问题QQQQQQQQ如何表示如何表示queeni+1,j+1)放置一个皇放置一个皇后以后，与该皇后同列

6、、两个对角线不后以后，与该皇后同列、两个对角线不能再放置皇后？能再放置皇后？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个

7、个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; /*当前解的序号当前解的序号*/

8、*找到一个解后，输出当前解找到一个解后，输出当前解*/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) &(ci+j=0)& (di-j+7=0) /*判别位置能否冲突判别位置能否冲突*/ queeni=j; /*摆放皇后摆放皇后*/ bj=1; /*宣布占领第宣布占领第j+1行行*

9、/ ci+j=1; /*占领两个对角线占领两个对角线*/ di-j+7=1; if (i7) try(i+1); /*8个皇后没有摆完，递归摆放下一皇后个皇后没有摆完，递归摆放下一皇后*/ else print(); /*完成义务，打印结果完成义务，打印结果*/ bj=0; /*回溯回溯*/ ci+j=0; di-j+7=0; int main() int k;/*数据初始化数据初始化*/for( k=0;k15;k+) if(k8) bk=0;ck=0; dk=0; try(0);/*从第从第1个皇后开场放置个皇后开场放置*/return 0;主函数主函数集合运算集合运算逆波兰表达式计算逆波

10、兰表达式计算 五子棋游戏程序五子棋游戏程序八皇后问题八皇后问题集合运算集合运算问题定义：假定一个选集合中有问题定义：假定一个选集合中有1、2到到32这这32个元个元素，恣意给出两个集合，求它们的并集、交集和差素，恣意给出两个集合，求它们的并集、交集和差集，并计算各个集合的势即集合中元素的个数。集，并计算各个集合的势即集合中元素的个数。 数据构造数据构造集合表示方法有：位向量、数组和树等本例运用位向量表示集合。一个位向量1：n表示集合，假设元素i在集合U中，那么置SET(i)=1，否那么为0。采用unsigned long 类型表示集合将unsigned long的32位从低到高位分别编号1、2

11、到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用二进制数表示为：用二进制数表示为： 01000000100000000010

12、000000000100#define UNION(x,y) (x)|(y)/*计算并集计算并集*/#define JIAOJI(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)&(y) /*计算交集*/#define DIFFERENCE(x,y) (x)(x)&(y) /*计算差集*/#de

13、fine SET(n) 1=1&j1; return n;/*输出集合*/void printset(unsigned long n)int i=1; printf(“); while(n) if(n&1!=0 printf(“%3d,i); i+; n=n1; printf(“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,cou

14、ntset(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;程序源代码程序源代码集合运算集合运

15、算逆波兰表达式计算逆波兰表达式计算 五子棋游戏程序五子棋游戏程序八皇后问题八皇后问题问题定义：编写一个具有加问题定义：编写一个具有加+ +、减、减- -、乘、乘* *、除、除/ /四那么运算功能的计算器程程序四那么运算功能的计算器程程序分析：通常一个四那么运算的算术表达式采用中辍分析：通常一个四那么运算的算术表达式采用中辍表示法。表示法。逆波兰表示法：一切运算符都跟在其运算分量的后逆波兰表示法：一切运算符都跟在其运算分量的后面。面。例如：例如：1-2*4+5用逆波兰表示法表示成：用逆波兰表示法表示成： 12 4 5 + * 逆波兰表达式计算逆波兰表达式计算如何实现计算器？如何实现计算器？栈底栈

16、底栈顶栈顶2栈底栈底栈顶栈顶2栈底栈底栈顶栈顶读一个运算符，从堆栈中取两个操作数如何实现计算器？如何实现计算器？-1栈底栈底栈顶栈顶计算结果为，入栈如何实现计算器？如何实现计算器？54栈底栈底栈顶栈顶-154栈底栈底栈顶栈顶-1读到运算符从堆栈中取两个操作数如何实现计算器？如何实现计算器？栈底栈底栈顶栈顶-1计算4+5，结果入栈如何实现计算器？如何实现计算器？栈底栈底栈顶栈顶-1读到运算符，从堆栈中取两个操作数如何实现计算器？如何实现计算器？栈底栈底栈顶栈顶-计算9*-1结果-9入栈如何实现计算器？如何实现计算器？伪代码如下：while(下一个运算符或运算分量不是文件终了指示符EOF)if(是

17、运算分量)将该运算分量压入堆栈中elseif(是运算符)弹出所需数目的运算分量执行运算将结果压入堆栈elseif(是换行符)弹出并打印栈顶的值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;入栈和出栈函数

18、入栈和出栈函数功能：读取操作数或运算符功能：读取操作数或运算符 伪代码如下：伪代码如下：跳过前导空格，将读取到的第一个非空格字符存入变量跳过前导空格，将读取到的第一个非空格字符存入变量c中；中；if(变量变量c不是数字字符或者小数点不是数字字符或者小数点) 终止函数执行，前往终止函数执行，前往c的取值的取值if(c是数字字符是数字字符) 读取整数部分，读取到非数字字符为止，并将该数字字符存放到读取整数部分，读取到非数字字符为止，并将该数字字符存放到变量变量c中中 if (c是小数点是小数点.)读取小数部分，读取到非数字字符为止，并将该数字字符存放到读取小数部分，读取到非数字字符为止，并将该数字

19、字符存放到变量变量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)&c!=.) return c; i=0; if (isdigit(c) /*读取整数部分*/ while(isdigit(s+i=c=get

20、ch(); if (c=.)/*读取小数部分*/ 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 characte

21、rsn);elsebufbufp+=c;程序源代码程序源代码#include #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();push(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;集合运算集合运算逆波兰