算法設(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è)，即：a0c0+a1

2、c1+.+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ǔ)問題n設(shè)有n個(gè)程序1,2, n 要存放在長(zhǎng)度為L(zhǎng)的磁帶上。程序i存放在磁帶上的長(zhǎng)度是li，1in。n程序存儲(chǔ)問題要求確定這n 個(gè)程序在磁帶上的一個(gè)存儲(chǔ)方案，使得能夠在磁帶上存儲(chǔ)盡可能多的程序。刪數(shù)問題n給定n 位正整數(shù)a，去掉其中任意kn 個(gè)數(shù)

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

4、一次刪去其中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ù)字三角形問題n給定一個(gè)由n行數(shù)字組成的數(shù)字三角形如下圖所示。試設(shè)計(jì)一個(gè)算法，計(jì)算出從三角形的頂至底的一條路徑，使該路徑經(jīng)過的數(shù)字總和最大。73 88 1 02 7 4 44 5 2 6 5整數(shù)變換問題n整數(shù)變換問題。關(guān)于整數(shù)i的變換f和g定義如下：f(i)=3i；g(i)=i/2。n試設(shè)計(jì)一個(gè)算法，對(duì)于給定的2個(gè)整數(shù)n

5、和m，用最少的f和g變換次數(shù)將n變換為m。n例如，可以將整數(shù)15 用4 次變換將它變換為整數(shù)4：4=gfgg(15)。整數(shù)變換問題15745321221359110631166674054最長(zhǎng)遞增子序列問題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ù)次序問題n設(shè)有n 個(gè)顧客同時(shí)等待一項(xiàng)服務(wù)。顧客i需要的服務(wù)時(shí)間為ti，1in，應(yīng)如何安排n 個(gè)顧客的服務(wù)次序才能使平均等待時(shí)間達(dá)到最??？平均等待時(shí)間是n 個(gè)顧客等待服務(wù)