算法，求從小到大排序的1500個醜數

醜數：隻包含因子2,3,5的數稱為醜數

解這個題的方法，生成法，滾雪球一樣，越滾越大，假設我們已經有n個最小的醜數集合S，且已經從小到大排好序，下面我們要找下一個醜數，這個醜數必定是2,3,5與集合S的乘積中大于Smax且是最小的。是以我們可以首先用2乘以集合S，找到大于Smax的最小的數T2，再重複找到T3,T5。取T2,T3,T5的最小值。

注：其實我們可以達到o(n)的時間計算複雜度

，這還蠻經典的，我們增加3個變量max2,max3,max5,M是目前遞增醜數序列的最大數。如果上一步是3乘以集合S得到的數M，這四者的關系是2*D[max2]<3*D[max3+1]，5*D[max5] 2*D[max2]<=M<2*D[max2+1]，3*D[max3]<=M<3*D[max3+1]，5*D[max5]<=M<5*D[max5+1]，也即下一步我們隻要比較這三個數2* D[max2+1]， 3*D[max3+1]，5* D[max5+1]中的最小者，如果是 5* D[max5+1]，那麼max5++，且把 5* D[max5+1]取為我們要的下一個醜數， 其餘兩個數max2,max3還是不變。此時我們仍舊有 2*D[max2]<=M<2*D[max2+1]，3*D[max3]<=M<3*D[max3+1]，5*D[max5]<=M<5*D[max5+1]的關系。下面繼續比較。可見時間複雜度，如果我們要n的醜數就是o(n^2)

還有個題，給一個重量a克的物體A，還已知我們有3^n克的砝碼各一個，n=0,1,...k,...。A物體必須放在天平上，其他的任選。怎麼是天平平衡？

我的辦法，從n=0開始，求出所有可能的差的組合，檢查a是否在裡面，不在的話讓n++,繼續下一步。 我們這裡采用分治法時求子問題不是從a開始往下減，而是從n開始，為什麼呢，因為a-1的規模并不一定比a小，但是n-1的規模一定比n小。同時這裡還有個技術室把問題轉化，放大。我們不能直接求出答案，我們求出所有的差，那麼如果a在這個集合裡，那麼問題就解決了。 觀察3^n這個數列的特性，會發現，如果使用了3^k，那麼最小是(3^k+1)/2,不使用3^k，那麼這個數最大是(3^k-1)/2。而 (3^k-1)/2和 (3^k+1)/2又是相鄰的兩個數。這樣就可以确定是否含有3^k了。如果一個數x,在[(3^m)/2 +1 ,(3^(m+1))/2 )那麼必然包含3^m這個數。怎麼求這個呢，可以從1開始，不斷乘以3，然後和x比較是否比x大，直到第一個比x大的數