經(jīng)典ACM算法合集經(jīng)典ACM算法合集

《經(jīng)典ACM算法合集經(jīng)典ACM算法合集》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、實(shí)驗(yàn)一統(tǒng)計(jì)數(shù)字問題實(shí)驗(yàn)二最大間隙問題實(shí)驗(yàn)三眾數(shù)問題實(shí)驗(yàn)四半數(shù)集問題實(shí)驗(yàn)五集合劃分問題實(shí)驗(yàn)六最少硬幣問題實(shí)驗(yàn)七編輯距離問題實(shí)驗(yàn)八程序存儲問題實(shí)驗(yàn)九最優(yōu)服務(wù)次序問題實(shí)驗(yàn)十汽車加油問題實(shí)驗(yàn)十一工作分配問題實(shí)驗(yàn)十二0-1背包問題實(shí)驗(yàn)十三最小重量機(jī)器設(shè)計(jì)問題實(shí)驗(yàn)十四最小權(quán)頂點(diǎn)覆蓋問題實(shí)驗(yàn)十五集合相等問題實(shí)驗(yàn)十六戰(zhàn)車問題實(shí)驗(yàn)一統(tǒng)計(jì)數(shù)字問題1、問題描述：一本書的頁碼從自然數(shù)1開始順序編碼直到自然數(shù)n。書的頁碼按照通常的習(xí)慣編排，每個(gè)頁碼都不含多余的前導(dǎo)數(shù)字0。例如，第6頁用數(shù)字6表示，而不是06或006等。數(shù)字計(jì)數(shù)問題要求對給定書的總頁碼n，計(jì)算出書的全部頁碼中分別用到多少次數(shù)字0，1，

2、2，…，9。2、題目分析：考慮由0,1,2,…,9組成的所有n位數(shù)。從n個(gè)0到n個(gè)9共有個(gè)n位數(shù)，在這些n位數(shù)中，0,1,2,…，9每個(gè)數(shù)字使用次數(shù)相同，設(shè)為。滿足如下遞歸式：由此可知，。據(jù)此，可從低位向高位進(jìn)行統(tǒng)計(jì)，再減去多余的0的個(gè)數(shù)即可。3、算法設(shè)計(jì)：定義數(shù)組a[10]存放0到9這10個(gè)數(shù)出現(xiàn)的次數(shù)，個(gè)位為第0位，第j位的數(shù)字為r。采用while循環(huán)從低位向高位統(tǒng)計(jì)：a.統(tǒng)計(jì)從個(gè)位算起前j位0~9個(gè)數(shù)；b.如果j+1位為0，去掉第j+1位補(bǔ)0個(gè)數(shù)；c.統(tǒng)計(jì)第j+1位出現(xiàn)1~(r-1)個(gè)數(shù)；d.統(tǒng)計(jì)第j+1位出現(xiàn)r個(gè)數(shù)。4、源程序：#include

3、>intmain(){longintsn[10];inti,n,c,k,s,pown;for(i=0;i<10;i++)sn[i]=0;cin>>n;for(k=s=0,pown=1;n>0;k++,n/=10,pown*=10){c=n%10;for(i=0;i<10;i++)sn[i]+=c*k*(pown/10);for(i=0;i

4、count()，故該算法的時(shí)間復(fù)雜度為O(1)。實(shí)驗(yàn)二最大間隙問題1、問題描述：最大間隙問題：給定n個(gè)實(shí)數(shù)x1,x2,...,xn,求這n個(gè)數(shù)在實(shí)軸上相鄰2個(gè)數(shù)之間的最大差值。假設(shè)對任何實(shí)數(shù)的下取整函數(shù)耗時(shí)O(1)，設(shè)計(jì)解最大間隙問題的線性時(shí)間算法。對于給定的n個(gè)實(shí)數(shù)x1,x2,...,xn，編程計(jì)算它們的最大間隙。2、題目分析：考慮到實(shí)數(shù)在實(shí)軸上按大小順序排列，先對這n個(gè)數(shù)排序，再用后面的數(shù)減去前面的數(shù)，即可求出相鄰兩數(shù)的差值，找出差值中最大的即為最大差值。3、算法設(shè)計(jì)：a.用快速排序算法對這n個(gè)數(shù)排序，快速排序算法是基于分治策略的一個(gè)排序算法。其基本思想是，對于輸入的子

5、數(shù)組a[p:r]，按以下三個(gè)步驟進(jìn)行排序：①分解：以a[p]為基準(zhǔn)元素將a[p:r]劃分為3段a[p:q-1]，a[q]和a[q+1:r]，使a[p:q-1]中任何一個(gè)元素小于等于a[p]，而a[q+1:r]中任何一個(gè)元素大于等于a[q]。下標(biāo)q在劃分過程中確定。②遞歸求解：通過遞歸調(diào)用快速排序算法分別對a[p:q-1]和a[q+1:r]進(jìn)行排序。③合并：由于對a[p:q-1]和a[q+1:r]的排序是就地進(jìn)行的，所以在a[p:q-1]和a[q+1:r]都已排好的序后，不需要執(zhí)行任何計(jì)算，a[p:r]就已排好序。b.用函數(shù)maxtap()求出最大差值。4、源程序：#incl

6、ude#includedoublea[1000000];templatevoidswap(Type&x,Type&y){Typetemp=x;x=y;y=temp;}templateintPartition(Type*a,intlow,inthigh){Typepivotkey;intmid=(low+high)/2;if((a[low]

7、

8、(a[low]>a[mid]&&a[mid]>a[high]))swap(a[low],a[mid])

9、;if((a[low]a[high])

10、

11、(a[low]>a[high]&&a[mid]pivotkey);if(i>=j)break;swap(a[i],a[j]);}a[low]=a[j];a[j]=pivotkey;returnj;}templat