程序设计实习课件

1、本讲内容课后作业难点题目(2道)2009年期中考试题(2道)课后作业其他题目(6道 )周末上机作业选讲(1道)第1页，共33页。POJ2774：木材加工动态规划解法木材厂有N根原木，它们的长度分别是一个整数. 现在想把这些木头切割成K根长度相同的小段木头.小段木头的长度要求是正整数. 请计算能够得到的小段木头的最大长度定义函数f(x):要切割得到x根木头时,所能够获得的最大长度 定义函数g(l):从原木中最多可以切割得到g(l)个长为l的木头 则f单调减，g单调减。 （为什么？f,g是互为反函数吗？） （注意g函数的单调性是二分法的基础，即求最大的x,使得g(x)=K。）k - len - m

2、axK - maxRest 要切割出k段 - len = f(k) - maxK = g(len) - 切完maxK根长len的木头后剩下最长木头的长度是maxRest 其中有maxRest total : 无法切割int partition( int k) k=1: 终态, objectBar1.len为切割前最长原木的长度 objectBar1.maxK为长度为len的原木个数 objectBar1.MaxRest为长度小于len的最长原木长度objectBark-1.maxK=0 : 递归过程partition(k-1)objectBark-1.maxK=k: objectBar k与o

3、bjectBar k-1相同objectBark-1.maxK=k)不要忘了计算objectBark.MaxRest第3页，共33页。木材加工参考程序#include #include using namespace std;const int MAX = 10005;int srcLenMAX; / 原始木头长度int N,K,tot;struct int len;int maxK;int maxrest;objectBarMAX;第4页，共33页。void solve()if(tot = 1 & srcLeni = srcLenN; i-);objectBar1.len = srcLenN

4、;objectBar1.maxK = N - i;objectBar1.maxrest = srcLeni;/开始递推 第5页，共33页。/开始递推 for(k = 2; k = k) objectBark.len = objectBark - 1.len; objectBark.maxK = objectBark - 1.maxK; objectBark.maxrest = objectBark - 1.maxrest;else第6页，共33页。 for(j = objectBark - 1.len - 1; j = objectBark - 1.maxrest & j = 1; j-) /

5、 枚举可能长度j cnt = 0,rest = 0; for(i = N; i = 1; i-) /计算最多可以切出多少个长度为j的木头 if(srcLeni = j)cnt += srcLeni / j;rest = rest (srcLeni % j) ? rest : (srcLeni % j); elserest = rest srcLeni ? rest : srcLeni;break; if(cnt = k) break; 第7页，共33页。 objectBark.len = j; objectBark.maxK = cnt; objectBark.maxrest = rest;

6、printf(%dn,objectBarK.len); 第8页，共33页。int main()freopen(f.txt,r,stdin);scanf(%d%d,&N,&K);tot = 0;for(int i = 1; i 1)个数，任意取2个数x,y(共有C(n,2)种)，然后枚举它们之间的6种可能运算： x + y , x y , y x, x * y ,x / y (y 0), y / x (x 0 )设z为x,y运算的结果，那么用z替代原来的x,y，n个数就变成为了n 1个数。递归进行这个过程，直到n = 1。#include #define up 24.00001#define d

7、own 23.99999bool is(int n);double a54;/ai用于存放求解i个数时的各数第11页，共33页。int main()while(scanf(%lf %lf %lf %lf, &a40, &a41, &a42, &a43) & a40!=0) if (is(4) printf(YESn); else printf(NOn);bool is(int n)if (n = 1) return (a10 down); / 到达终止条件，判断是否找到24double * pa = an;double * pb = an-1;第12页，共33页。for (int i=0; i

8、n; i+) for (int j=i+1; jn; j+) /将除了pai, paj以外的复制给下层函数。int iter = 0;for (int temp=0; tempn; temp+)if (temp!=i & temp!=j)pbiter = patemp;iter+;/穷举对i、j的运算pbn-2 = pai + paj; /加法if (is(n-1) return true;pbn-2 = pai - paj; /减法if (is(n-1) return true;pbn-2 = paj - pai; /减法第13页，共33页。if (is(n-1) return true;p

9、bn-2 = pai * paj; /乘法if (is(n-1) return true;if (paj != 0) /除法pbn-2 = pai / paj;if (is(n-1) return true;if (pai != 0) /除法pbn-2 = paj / pai;if (is(n-1) return true;return false;第14页，共33页。2009年期中试题: POJ3726 仙岛求药Description：少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。

10、迷阵由MN个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。图-1 显示了一个迷阵的样例及李逍遥找到仙药的路线.第15页，共33页。Input：输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始，两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义: ：少年李逍遥所在的位置；.：可以安全通行的方格；#：有怪物的方格；*：仙药所在位置。当在一行中读入的是两个零时，表示

11、输入结束。Output：对于每组测试数据，分别输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。第16页，共33页。Sample Input:8 8.#.#.#.#.#.#.#.#.#.#.#.#.#.#.*.#.#6 5.*.#.#.#.#.9 6.#.#. .#.*.# .#. .#. .#. .#. .#. #.# .#.#. 0 0Sample Output:108-1第17页，共33页。/用宽度优先搜索解决此题。/每次从队头取一个节点，看是否是终点，如果不是，就将队头节点周围的可达/的点都放入队列。要记住每个点的

12、上一个点是什么#include using namespace std;#define SIZE 32int M,N;char MazeSIZESIZE;int nStartR,nStartC;int nDestR,nDestC;int nHead;int nTail;struct Positionint r;int c;int depth; QueueSIZE * SIZE;int Bfs();第18页，共33页。int main()int i,j,k;while(1) cin M N;if( M = 0 & N = 0 )break;memset( Maze,#,sizeof(Maze);

13、for( i = 1;i = M; i + )for( j = 1; j Mazeij;if( Mazeij = ) nStartR = i;nStartC = j;Mazeij = .;else if( Mazeij = * ) nDestR = i;nDestC = j;Mazeij = .;第19页，共33页。cout Bfs() endl;int Bfs( ) nHead = 0;nTail = 1;QueuenHead.r = nStartR;QueuenHead.c = nStartC;QueuenHead.depth = 0;int dir2 = 0,1,0,-1,1,0,-1,

14、0;while( nHead != nTail) if( QueuenHead.r = nDestR & QueuenHead.c = nDestC ) return QueuenHead.depth;第20页，共33页。 for(int i = 0; i 4; i+) int nCurR = QueuenHead.r + diri0;int nCurC = QueuenHead.c + diri1;if(MazenCurRnCurC = .) QueuenTail.c = nCurC;QueuenTail.r = nCurR;QueuenTail.depth = QueuenHead.dep

15、th + 1;MazenCurRnCurC = #;nTail +;else if(MazenCurRnCurC = *) return QueuenHead.depth + 1; nHead +; return -1;第21页，共33页。2009年期中试题: POJ3728 Blah数集Description：大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对于以a为基的集合Ba定义如下：(1) a是集合Ba的基，且a是Ba的第一个元素；(2)如果x在集合Ba中，则2x+1和3x+1也都在集合Ba中；(3)没有其他元素在集合Ba中了。现在小高斯想知道如果将集合Ba中元素按照升序排列

16、，第N个元素会是多少？Input：输入包括很多行，每行输入包括两个数字，集合的基a(1=a=50)以及所求元素序号n(1=n=1000000)Output：对于每个输入，输出集合Ba的第n个元素值Sample Input1 10028 5437 Sample Output418900585 第22页，共33页。#include using namespace std;int Stack1000010;int main()int a,n;while( scanf(%d%d,&a,&n) != EOF) int p2 = 1 ,p3 = 1;int nTop = 1;Stack1 = a;whil

17、e(1) if( nTop = n ) printf(%dn, StacknTop );break;if( 2 * Stackp2 + 1 3 * Stackp3+1 ) nTop +;StacknTop = 3 * Stackp3 + 1;p3 +;else / 扩展的结点相等的时候两个指针都要向前滑动nTop +;StacknTop = 3 * Stackp3 + 1;p3 +;p2 +;return 0;第24页，共33页。POJ2804：字典词条(一行)：一个英文单词、一个外语单词100000 个词条给外语单词，翻译出英文这个题目很简单，方法较多，可以 (1)排序+二分 (2)hash

18、表 (3)（平衡）二叉搜索树 (4)Trie树关键点：查找的效率。以方法(1)为例：qsort bsearch使用结构表示词条外语单词英文单词外文单词作为排序的key值搜索词条：外语单词注意： qsort排序的元素类型与bsearch查找的元素类型要完全一致第25页，共33页。POJ2797：最短前缀前缀：单词前若干个字母，不是其它单词的前缀21000行可以是整个单词这个题目关键点把有相同前缀的单词放到一起： qsort确定它们的各自前缀，只需考虑相邻的单词(为什么？证明)不是前面单词的前缀不是后面单词的前缀按照输入的顺序输出： qsort时间复杂度O(nlogn)两次排序，使用结构保存：单词本身word单词word的前缀prefixword在输入中的顺序第26页，共33页。POJ2813：画家问题分析问题特征： (1) 每一格要么画一次，要么不画 (2)