本次作業為數列應用
查了一下發現是OEIS裡的A051037又有Hamming sequence、Regular number等稱號
簡單來說就是只有以2、3、5為質因數的數列
1~60範圍長這樣：
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60
題目有兩種模式：X模式、Y模式
X模式是問等號後方的數字是否為數列的數字
例如：X=10 ，若 10 是屬於這數列則印出true，反之false
這個模式算簡單，只要判斷是否可以整除2、3、5然後一直除，最後等於1就是屬於這數列
Y模式是問第幾個數為何
例如：Y=10 ，則要印出12
這Y模式也太難了吧，查資料時也看到這是一個演算法的經典問題
總之我想了頗久
雖然這是最不趕的作業但我不信邪XDD
好險還蠻順利的完成OuO
本篇主要記錄我的想法，應該就不會有程式碼了
不過想看程式碼可以去我的Github找這裡，自己的作業自己寫OuO
一、建表
首先我想到了最輕鬆(
就是利用網路上的數列檔案建表，要第幾個就去找索引
不過網路上只有提供10000個，而助教說用long存，所以應該不只這些
所以放棄QuQ
二、用次方產生
就是用2、3、5的次方產生
也就是(2^i)*(3^j)*(5^k)然後i、j、k各種排列組合
不過因為大小出現的順序幾乎沒規律，產生後可能需要經過排序，頗麻煩=''=
所以放棄QuQ
三、數列產生數列
發現如果a為數列中的數則2a、3a、5a也為數列中的數
那如何不經過排序就產生數列?
首先想到就是跟前n-1個的2、3、5倍來比較，找出大於最後一個又是最小的放在下一個
例如：目前數列為：1, 2, 3, 4, 5, 6, 8, 9, 10, 12
要找出下一個就把1, 2, 3, 4, 5, 6, 8, 9, 10, 12都乘以2、乘以3、乘以5，如下
2, 4, 6, 8, 10, 12, 16, 18, 20, 24
3, 6, 9, 12, 15, 18, 24, 27, 30, 36
5, 10, 15, 20, 25, 30, 40, 45, 50, 60
然後找出大於12又是最小的，發現是15，所以12後是15
發現越來越有點樣子了，不過這個時間複雜度應該是O(n^2)吧(亂分析
所以放棄QuQ
四、數列產生數列．改
發現全部都乘有點不太必要，因為前面都一定會太小浪費時間
找比12/5還要大的數即可，因為如果比12小5倍以上，乘以2、3、5都不會大於12
所以應該從3開始乘就好
一下子就縮短許多時間
不過空間是浪費的，而且每算一個數都要重新乘，乘完就丟，完全沒有再利用的觀念
所以放棄QuQ
五、數列產生數列．終極版
把乘過的也儲存起來呢? 突然靈光乍現OuO
終極版來囉~
首先用一個List(可以想成陣列，不過更好用OuO)存數列，名稱叫ha好了，1是開頭
我把1*2、1*3、1*5分別存到另外三個List裡面，用.add()即可，名稱分別為2h、3h、5h
找下一個時只要比較2h、3h、5h的第一個數誰最小
發現2是最小的，所以把它存到ha的後面，用.add(2)即可
接著把2從2h裡面移除，用.remove(0)即可
p.s.如果有重複的就都要移除，例如6在2h、3h都會有，不過取到6時它都會在2h、3h的第一個
這樣就完成第2個
再來就是迴圈了
找第三個時一樣把2*2、2*3、2*5分別放到2h、3h、5h後
比較三List的第一個大小，此時2h的第一個是4了
這次最小是3所以就把3放到ha後面，然後從3h裡移除3
分析一下：
新增3個數放到List後面是常數時間
比較3個數也是常數時間
移動、移除一個數是常數時間
只有一開始輸入的n決定迴圈要跑幾次，所以是O(n) 嗎
(
最後跑Y=999999時花了30秒左右(手機計時)
總之我已經盡我所能快了，還有其他方法歡迎提供QuQ
參考資料：(前面內容中都有附上連結)
踏踏OUO
回覆刪除路人4ni OuO
刪除