程序设计方案实习

程序设计实习第十讲习题评讲本讲内容课后作业难点题目(2道)

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

maxK

=

g(len)->切完maxK根长len的木头后剩下最长木头的长度是maxRest其中有maxRest<len成立。（为什么？）int

sourceBar[N]:存储N根原木的长度objectBar[K]:结构体objectBar[i]的含义如下len;要切割得到i根木头时,所能够获得的木头的最大长度maxK;切割成长度为len的木头时,可切得的最大木头数量MaxRest;切割成maxK根长度为len的木头后,剩余原木的最大长度注意，先确定len，再确定maxK,最后确定MaxRest。total:切割前N根原木的长度总和特殊情况：K>total:无法切割int

partition(

int

k)k==1:终态,objectBar[1].len为切割前最长原木的长度objectBar[1].maxK为长度为len的原木个数objectBar[1].MaxRest为长度小于len的最长原木长度objectBar[k-1].maxK=0:递归过程partition(k-1)objectBar[k-1].maxK>=k:objectBar

[k]与objectBar

[k-1]相同

objectBar[k-1].maxK<k:确定len:objectBara[k].len

[objectBar[k-1].MaxRest,

objectBar[k-1].le哪个长度len能够使得objectBar[k].maxK

k?(也就是g(len)>=k)不要忘了计算objectBar[k].MaxRest木材加工参考程序#include

<iostream>#include

<algorithm>using

namespace

std;const

int

MAX

=

10005;int

srcLen[MAX];//原始木头长度int

N,K,tot;struct{int

len;

int

maxK;int

maxrest;}objectBar[MAX];void

solve(){if(tot

<

K){//特殊情况特殊判断printf("0\n");return;}int

i,j,k,cnt,rest;//对递推开始状态初始化for(i

=

N;

i

>=

1

&&

srcLen[i]

==

srcLen[N];i--);objectBar[1].len

=

srcLen[N];objectBar[1].maxK

=

N

-

i;objectBar[1].maxrest

=

srcLen[i];//开始递推//开始递推for(k

=

2;

k

<=

K;

k++){if(objectBar[k

-

1].maxK

>=

k){objectBar[k].len

=

objectBar[k

-1].len;objectBar[k].maxK

=

objectBar[k

-1].maxK;objectBar[k].maxrest

=

objectBar[k-

1].maxrest;}else{for(j

=

objectBar[k

-

1].len

-

1;

j

>=

objectBar[k

-1].maxrest

&&

j

>=

1;

j--){//枚举可能长度jcnt=0,rest=0;for(i=N;i>=1;i--){//计算最多可以切出多少个长度为j的木头if(srcLen[i]

>=

j){cnt

+=

srcLen[i]

/

j;rest

=

rest

>

(srcLen[i]

%

j)

?

rest

:

(srcLen[i]

%j);}else{rest

=

rest

>

srcLen[i]

?

rest

:

srcLen[i];break;}}if(cnt

>=

k)

break;}objectBar[k].len

=

j;objectBar[k].maxK

=

cnt;objectBar[k].maxrest

=

rest;}}printf("%d\n",objectBar[K].len);}int

main(){freopen("f.txt","r",stdin);scanf("%d%d",&N,&K);tot

=

0;for(int

i

=

1;

i

<=

N;

i

++){scanf("%d",&srcLen[i]);tot

+=

srcLen[i];}sort(srcLen,srcLen

+

N

+

1);solve();return

0;}3+(6–2)/4,5/(5-1/5)的语法树是什么？POJ2787：算24poj2787算24给出4个小于10个正整数，你可以使用加减乘除4种运算以

及括号把这4个数连接起来得到一个表达式。现在的问题是，是否存在一种方式使得得到的表达式的结果等于24每一种可能的计算方式都对应一棵语法树。比如a*(b+c)。本题只有4个数、4中运算，因此可以通过穷举搜索全部可能的语法树（因而穷举了全部可能表达式）来寻找24。穷举搜索的方法是，从语法树的树叶开始往上形成语法树，即自底向上的构建语法树。具体的说，对当前的n(>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

<stdio.h>#define

up

24.00001#define

down

23.99999bool

is(int

n);double

a[5][4];//a[i]用于存放求解i个数时的各数int

main(){while(scanf("%lf

%lf

%lf

%lf",

&a[4][0],&a[4][1],

&a[4][2],

&a[4][3])

&&

a[4][0]!=0){if

(is(4))

printf("YES\n");else

printf("NO\n");}}bool

is(int

n){if

(n

==

1)return

(a[1][0]

<

up

&&

a[1][0]

>down);//到达终止条件，判断是否找到24double

*

pa

=

a[n];double

*

pb

=

a[n-1];for

(int

i=0;

i<n;

i++){for

(int

j=i+1;

j<n;

j++){//将除了pa[i],pa[j]以外的复制给下层函数。int

iter=0;for

(int

temp=0;

temp<n;

temp++){if

(temp!=i

&&

temp!=j){pb[iter]

=

pa[temp];iter++;}}//穷举对i、j的运算pb[n-2]=pa[i]+pa[j];//加法if

(is(n-1))return

true;pb[n-2]=pa[i]-pa[j];//减法if

(is(n-1))return

true;pb[n-2]=pa[j]-pa[i];//减法if

(is(n-1))

return

true;pb[n-2]=pa[i]*

pa[j];//乘法if

(is(n-1))return

true;if

(pa[j]!=0)//除法{pb[n-2]

=

pa[i]

/

pa[j];if

(is(n-1))

return

true;}if

(pa[i]!=0)//除法{pb[n-2]

=

pa[j]

/

pa[i];if

(is(n-1))

return

true;}}}return

false;}2009年期中试题:POJ3726仙岛求药Description：少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。图-1显示了一个迷阵的样例及李逍遥找到仙药的路线.Input：输入有多组测试数据.每组测试数据以两个非零整数M

和N

开始，两者均不大于20。M

表示迷阵行数,N

表示迷阵列数。接下来有M

行,每行包含N个字符,不同字符分别代表不同含义:‘@’：少年李逍遥所在的位置；‘.’：可以安全通行的方格；‘#’：有怪物的方格；‘*’：仙药所在位置。当在一行中读入的是两个零时，表示输入结束。Output：对于每组测试数据，分别输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药,则输出-1。Sample

Input:8

8.@##...##....#.##.#.##....#.###.#.#...#...###.#....#.*...#...###6

5.*.#..#.....##.......#.......@9

6.#..#..#.*.#.####...#.....#.....#.....#...#.@.##.#..#.0

0Sample

Output:108-1//用宽度优先搜索解决此题。//每次从队头取一个节点，看是否是终点，如果不是，就将队头节点周围的可达//的点都放入队列。要记住每个点的上一个点是什么#include

<iostream>using

namespace

std;#define

SIZE

32int

M,N;char

Maze[SIZE][SIZE];int

nStartR,nStartC;int

nDestR,nDestC;int

nHead;int

nTail;struct

Position{int

r;

int

c;

int

depth;}

Queue[SIZE

*

SIZE];int

Bfs();int

main(){int

i,j,k;while(1)

{cin

>>

M

>>

N;if(

M

==

0

&&

N

==

0

)break;memset(

Maze,"#",sizeof(Maze));for(

i

=

1;i

<=

M;

i

++

)for(

j

=

1;

j

<=

N;

j

++

)

{cin

>>

Maze[i][j];if(

Maze[i][j]

==

"@"

)

{nStartR

=

i;nStartC

=

j;Maze[i][j]

=

".";}else

if(

Maze[i][j]

==

"*"

)

{nDestR

=

i;nDestC

=

j;Maze[i][j]

=

".";}}cout

<<

Bfs()

<<

endl;}}int

Bfs(

)

{nHead

=

0;nTail

=

1;Queue[nHead].r

=Queue[nHead].c

=nStartR;nStartC;Queue[nHead].depth

=

0;int

dir[][2]

=

{{0,1},{0,-1},{1,0},{-1,0}};while(

nHead

!=

nTail)

{if(

Queue[nHead].r

==

nDestR

&&

Queue[nHead].c

==

nDestC

)

{return

Queue[nHead].depth;}for(int

i

=

0;

i

<

4;

i++)

{int

nCurR

=

Queue[nHead].r

+

dir[i][0];int

nCurC

=

Queue[nHead].c

+

dir[i][1];if(Maze[nCurR][nCurC]

==

".")

{Queue[nTail].c

=

nCurC;Queue[nTail].r

=

nCurR;Queue[nTail].depth

=

Queue[nHead].depth

+1;Maze[nCurR][nCurC]

=

"#";nTail

++;}else

{if(Maze[nCurR][nCurC]

==

"*")return

Queue[nHead].depth

+

1;}}nHead

++;}return

-1;}2009年期中试题:POJ3728

Blah数集

Description：大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对于以a为基的集合Ba定义如下：a是集合Ba的基，且a是Ba的第一个元素；如果x在集合Ba中，则2x+1和3x+1也都在集合Ba中；

(3)没有其他元素在集合Ba中了。现在小高斯想知道如果将集合Ba中元素按照升序排列，第N个元素会是多少？

Input：输入包括很多行，每行输入包括两个数字，集合的基a(1<=a<=50))以及所求元素序号n(1<=n<=1000000)Output：对于每个输入，输出集合Ba的第n个元素值

Sample

Input1

10028

5437Sample

Output418900585#include

<iostream>using

namespace

std;int

Stack[1000010];int

main(){int

a,n;while(

scanf("%d%d",&a,&n)

!=

EOF)

{int

p2

=

1

,p3

=

1;int

nTop

=

1;

Stack[1]

=

a;

while(1)

{if(

nTop

==

n

)

{printf("%d\n",

Stack[nTop]

);break;}if(

2

*

Stack[p2]

+

1

<

3

*

Stack[p3]+1

)

{nTop

++;Stack[nTop]

=

2

*

Stack[p2]

+

1;p2

++;}else

if(

2

*

Stack[p2]

+

1

>

3

*

Stack[p3]+1

)

{nTop

++;Stack[nTop]

=

3

*

Stack[p3]

+

1;p3

++;}else{//扩展的结点相等的时候两个指针都要向前滑动nTop++;Stack[nTop]

=

3

*

Stack[p3]

+

1;p3

++;p2

++;}}}return

0;}POJ2804：字典词条(一行)：一个英文单词、一个外语单词100000个词条给外语单词，翻译出英文这个题目很简单，方法较多，可以(1)排序+二分(2)hash表(3)（平衡）二叉搜索树(4)Trie树关键点：查找的效率。以方法(1)为例：qsort→bsearch使用结构表示词条外语单词英文单词外文单词作为排序的key值搜索词条：外语单词注意：qsort排序的元素类型与bsearch查找的元素类型要完全一致s1<=s2<=s3。证明lcp(s1,s2)>=lcp(s1,s3)。令lcp(s1,s3)=p。Lcp(s1,s2)>=p,否则lcp(s1,s2)<p，即s1(p)<s2(p)。这导致s3(p)=s1(p)<s2(p)即s3<s2，矛盾。POJ2797：最短前缀前缀：单词前若干个字母，不是其它单词的前缀2~1000行可以是整个单词这个题目关键点把有相同前缀的单词放到一起：qsort确定它们的各自前缀，只需考虑相邻的单词(为什么？证明)不是前面单词的前缀不是后面单词的前缀按照输入的顺序输出：qsort时间复杂度O(nlogn)两次排序，使用结构保存：单词本身word单词word的前缀prefixword在输入中的顺序POJ2813：画家问题分析问题特征：每一格要么画一次，要么不画操作顺序无关性，只与在该格子上的操作次数有关猜测：确定第一行的每一块是否要画，就可以确定其他全部格子是否要画。可能无解(无法将全部块涂成黄色)技巧加边框，简化计算使用位运算，枚举第一行的全部情况0

~

(1<<N–1)种情况第k位为1，画第一行的第k块移动影响的时钟1ABDE2

ABC3

BCEF4

ADG5