2. 此地的記憶體用量明顯比上一題的傳統篩法大許多。
可否將它作節省呢？
首先我們不要prev[]只留下next[]，那對於next[i]來說，
如果i-1沒有被刪除，那i的上一個是i-1，但若i-1已經被刪除了，
我們用next[i-1]來存原來的prev[i]，換句話說，
i的上一個就是i-1與next[i-1]中值較少的那一個。
請問，還有什麼邊界條件要考慮，並且將此概念寫成程式。
這個技巧在第一個問題之下能否適用呢？
個人解答：
以下的解法非常非常非常(沒錯，就是三個非常)容易搞混，
所以請務必仔細的讀每一句話，並且留意：
"值"和"索引值"的差別！
首先，在第一個延伸問題的前提下，這個技巧仍然可以適用，
只不過，index的基礎移動變為2了。
原本的的核心概念是：
當自己被刪掉時，告訴自己的上一個數:"你的下一個變成XX"，
再告訴自己的下一個數:"你的上一個變成OO"。
這樣子就結束了。
但在現在，我們只剩下next可以放"下一個"，
所以在上一個數的存放的時候，我們要利用已被"刪除"的數的空間。
整體而言，當一個數被刪掉的時候，我們應該要做三件事：
1. 把next[x]值，存給前一個index的next[]。
2. 在index為next[x]的位置的前一個(-2)，存入前一個位置的index。
3. 將自己的位置，也存入前一個位置的index。
在這個機制下，要如何判斷一個數x的前面一個是哪位的方式，
就是先找往前2單位的index，
看它裡面的值是否比index大，較大代表未刪去，較小代表已刪去。
前者的狀況表示x-2即是x的前一個，後者的狀況，
x-2裡面存放的，就是x的前一個數的index。
很難理解是嗎？
我們舉幾個例子：
考慮3、5、7、9、11，一開始是
index 3 5 7 9 11
value 5 7 9 11 13
9被刪去的時候，我們做上述的三件事：
1. 告訴前一個數，你的next[]要改存11了。
9-2是7，next[7]=9，表示它目前是沒被刪除的，
所以我們把11存到next[7]裡面。
2. 在9的下一個位置next[9]的前一個(-2)位置，存入前一個位置(7)的index。
也就是在11-2=9的地方存入7。
3. 將自己的位置，也存入前一個位置的index。(也就是在9的地方存入7)
這當中其實3可以不用做結果也一樣，
會這麼做只是因為在定義上來說，我們希望只要是已刪去的數，
儲存的值都要比自己小。
做完以後的樣子會變成：
index 3 5 7 9 11
value 5 7 11 7 13
再舉個例子，考慮31、33、35、37、39，
篩去的順序會是33->39->35，依序做完的狀況如下：
index 31 33 35 37 39
value 33 35 37 39 41
after 1 35 31 37 39 41
after 2 35 31 37 41 37
after 3 37 31 31 41 37
過程不再贅述，就是仍然按照上面三個步驟進行就是了。
或許有人會說，看起來2和3是做相同的事情呀！
你每次繞來繞去，最後不就是把自己改掉就好了，
那我們不做2直接做3就好啦！
2和3兩個情況，在大多數是相同的，但還是有例外：
以下的刪去順序是先27再25，因為3比較早篩。
index 23 25 27 29
value 25 27 29 31
after 1 25 29 25 31
after 2 29 23 23 31
發現了嗎？因為29要知道自己的前面是23的話，
我們必須告訴27，要27裡面放23進去，
這時候29-2是27，而不是25，如果我們只改掉25裡面的值，
就會產生問題。
除此以外還有一個很重要的邊界條件：
在原問題中，我們使用NULL做為邊界。
在C語言中，NULL其實就是指0的意思，
但記得我們的迴圈是怎麼判斷繼續的嗎？
沒錯，就是乘積<n。
使用NULL的狀況下，
在我們這樣子把值指定給"刪去"後的index時，
會發生我們會讀到NULL的狀況，
這時候mult會一直等於0，也就一直跳不出去，
而且偵測到NULL就break的方式，
也會受限於0的值會傳遞到奇怪的地方而有時會出錯。
怎麼辦呢？
既然用0不行，那我們將其設成MAXSIZE+1如何？
如此一來，當跑到最後面，迴圈肯定能夠跳出來。
當然缺點是能跑的值會更加受限於資料型態的最大範圍，
但這個方法本來就會受限於乘法隨數字增大，
而令計算時間變長的問題，其實也不能跑多大的數字XD
判斷前一個值的時候，我們使用
if(LEFT(x) < next[LEFT(x)]) 當中LEFT(x)可以定義成x-2或x-1，
端看今天我們有沒有先行將2的倍數處理掉。
如果前一位(i-2)的index比所存的value小，代表沒被刪掉，
所以i-2就是i的前一個。
否則，就是i-2所存的value值，是i的前一個的index。
Code的部分，我們將prev相關的通通除去，
而在最後的走訪print出所有質數的時候，
將條件改成：for(i = 2; i!= MAXSIZE+1; NEXT(i))即可。
為了方便一點閱讀，多設了一個變數tmp，
讓if和else執行的狀況看起來更有條理。
Code：
/* Coded by Desolve(雨蕭) 2013.2.9
REMOVE先判斷前一個的位置後，做三件事情：
1. 把next[x]值，存給前一個index的next[]。
2. 在index為next[x]的位置的前一個(-2)，存入前一個位置的index。
3. 將自己的位置，也存入前一個位置的index。
第3點可以不用做，這只是為了概念上較容易懂；
但注意2和3不完全等義，所以不能只做3而不做2。
*/
#define REMOVE(x) { \
if(LEFT(x) < next[LEFT(x)]){ \
next[LEFT(x)] = next[x]; \
next[LEFT(next[x])] = LEFT(x); \
next[x] = LEFT(x); \
}else{ \
tmp = next[LEFT(x)]; \
next[tmp] = next[x]; \
next[LEFT(next[x])] = tmp; \
next[x] = tmp; \
}\
}
#define LEFT(x) x-2
#define INITIAL(n) { unsigned long i; \
for(i=3; i<=n; i+=2) \
next[i]=i+2; \
next[2]=3, next[n]=MAXSIZE+1; \
}
沒有留言:
張貼留言