算法設(shè)計(jì)與分析習(xí)題課

1、算法設(shè)計(jì)與分析習(xí)題課 復(fù)雜性分析 n幾種基本結(jié)構(gòu)的算法時(shí)間頻度 for (int i=0; in; i+) S(); for (int i=0; in; i+) for (int j=0; jn; j+) S(); for (int i=0; in; i+) for (int j=i; j1,k1，要用最 少的幣數(shù)找出n元錢，能否用貪心算法求解？ 若采用貪心法求解，即先盡量找最大可用面值的貨幣。若采用貪心法求解，即先盡量找最大可用面值的貨幣。 設(shè)最大可用面值為設(shè)最大可用面值為ct，即：，即：ctnct+1，tk。 設(shè)從設(shè)從c0到到ct，各種面值的貨幣各找了，各種面值的貨幣各找了ai個(gè)，即：個(gè)，

2、即： a0c0+a1c1+.+atct=n，求解目標(biāo)為，求解目標(biāo)為ai最少。最少。 貪心選擇性質(zhì)：貪心選擇性質(zhì)： 所做的貪心選擇為：所做的貪心選擇為：atctn(at+1)ct 即：即：a0c0+a1c1+.+at-1ct-1ct 最優(yōu)子結(jié)構(gòu)性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)： 做出貪心選擇做出貪心選擇atct后，應(yīng)使剩余的部分后，應(yīng)使剩余的部分 a0+a1+.+at-1達(dá)到最少。達(dá)到最少。 程序存儲(chǔ)問(wèn)題 n設(shè)有n個(gè)程序1,2, n 要存放在長(zhǎng)度為 L的磁帶上。程序i存放在磁帶上的長(zhǎng)度是 li，1in。 n程序存儲(chǔ)問(wèn)題要求確定這n 個(gè)程序在磁 帶上的一個(gè)存儲(chǔ)方案，使得能夠在磁帶 上存儲(chǔ)盡可能多的程序。 刪數(shù)

3、問(wèn)題 n給定n 位正整數(shù)a，去掉其中任意kn 個(gè) 數(shù)字后，剩下的數(shù)字按原次序排列組成 一個(gè)新的正整數(shù)。對(duì)于給定的n位正整數(shù) a 和正整數(shù)k，設(shè)計(jì)一個(gè)算法找出剩下數(shù) 字組成的新數(shù)最小的刪數(shù)方案。 n例如，n=178543，k=4，則結(jié)果為13。 刪數(shù)問(wèn)題 設(shè)X = X1 X2 . Xi-1 Xi Xi+1 . Xn 若X1 X2 . Xi-1 Xi+1 可證明，刪除Xi是可得到的最小的數(shù)。 石子合并問(wèn)題 n在一個(gè)操場(chǎng)的四周擺放著n 堆石子?，F(xiàn) 要將石子有次序地合并成一堆。規(guī)定每 次只能選2 堆石子合并成新的一堆，合 并的費(fèi)用為新的一堆的石子數(shù)。試設(shè)計(jì) 一個(gè)算法，計(jì)算出將n堆石子合并成一堆 的最小

4、總費(fèi)用。 數(shù)列極差問(wèn)題 n對(duì)由N (N2000)個(gè)正數(shù)組成的一個(gè)數(shù)列，進(jìn)行 如下操作：每一次刪去其中2 個(gè)數(shù)設(shè)為a和b， 然后在數(shù)列中加入一個(gè)數(shù)a*b+1，如此下去直 至只剩下一個(gè)數(shù)。在所有按這種操作方式最后 得到的數(shù)中，最大的數(shù)記為max，最小的數(shù)記 為min，則該數(shù)列的極差M 定義為M = max - min。 n例如，若數(shù)列為(1, 2, 3)，則極差為10-8=2。 數(shù)字三角形問(wèn)題 n給定一個(gè)由n行數(shù)字組成的數(shù)字三角形如 下圖所示。試設(shè)計(jì)一個(gè)算法，計(jì)算出從 三角形的頂至底的一條路徑，使該路徑 經(jīng)過(guò)的數(shù)字總和最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 整數(shù)變換問(wèn)題

5、 n整數(shù)變換問(wèn)題。關(guān)于整數(shù)i的變換f和g定 義如下：f(i)=3i；g(i)=i/2。 n試設(shè)計(jì)一個(gè)算法，對(duì)于給定的2個(gè)整數(shù)n 和m，用最少的f和g變換次數(shù)將n變換為 m。 n例如，可以將整數(shù)15 用4 次變換將它變 換為整數(shù)4：4=gfgg(15)。 整數(shù)變換問(wèn)題 15 745 32122135 911063116667405 4 最長(zhǎng)遞增子序列問(wèn)題 n給定正整數(shù)序列x1, x2, , xn。計(jì)算其 最長(zhǎng)遞增子序列的長(zhǎng)度s。 n例如，若序列為(3, 6, 2, 5)，則s=2。 設(shè)mi表示以Xi為結(jié)尾的最大遞增子序列的長(zhǎng)度。 則：mi = 1+max0,mk | xkxi,1ki 最優(yōu)服務(wù)次序問(wèn)題 n設(shè)有n 個(gè)顧客同時(shí)等待一項(xiàng)服務(wù)。顧客i 需要的服務(wù)時(shí)間為ti，1in，應(yīng)如何安 排n 個(gè)顧客的服務(wù)次序才能使平均等待 時(shí)間達(dá)到最?。科骄却龝r(shí)間是n 個(gè)顧 客等待服務(wù)時(shí)間