程序設計實習第十講習題評講本講內容課后作業難點題目(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