方法名稱：
public static boolean isSpecial (int n)
給出一個數字，檢查它是否特殊，這是如何特殊定義的：
從自然數開始；在第k個篩分步驟，去除第(k-1)-st個篩分步驟后剩余的序列的每個第(k 1)-st項；迭代。
1、3、7、13、19、27、39、49、63、79、91、109、133、147、181、207、223、253、289、307、349、9、9、4、53 529, 567, 613, 649, 709, 763, 807, 843, 927, 949, 1009, 1093, 1111, 1189, 1261, 1321, 1359, 1473, 7, 3, 7, 9, 149, 19, 149, 19, 19, 19 2023
這需要通過遞回來完成，這是我所做的：
public static boolean isSpecial (int n) {
if((n % 5 != 0) && (n % 2 != 0))
return true;
return(isSpecial(n-1));
}
我t know how to do it by recursion,from what iv讀過這個數字永遠不能被 2 或 5 整除，所以我應該檢查之前的每個數字是否都不能被 2 和 5 整除？
uj5u.com熱心網友回復：
我們僅根據它們的位置從串列中洗掉數字，并完全忽略它們的值。恰好在第一步中，位置 n 上的數字的值是 n。因此，僅考慮數字在串列中的位置而不是其實際值是有用的。
好的，假設我們已經進行了篩選程序的 k - 1 步，現在我們要確定當前位于位置 n 的數字是否會在下一個第 k 步從串列中洗掉。在第 k 步，我們將從串列中洗掉所有位置為 (k 1) 倍數的數字。顯然這里有3種可能性：
n < k 1。
在這種情況下，數字將繼續存在，而且很明顯它將在洗掉程序的所有未來步驟中繼續存在，因為從現在開始，我們將從串列中僅洗掉位置大于 n 的數字。因此，在這種情況下，我們確定數字 n 是特殊的。n 是 k 1 的倍數。
在這種情況下，該數字將從當前步驟的串列中洗掉，因此它并不特殊。否則數字 n 大于 k 1，但不是 k 1 的倍數。
那么該數字將在當前步驟中存活。但是，我們將從它前面的串列 n/(k 1) 個數字中刮擦。我們需要將除法的結果四舍五入。例如，如果 n=7，k=2，我們從串列中洗掉每第三個數字。然后 7/3 = 2 個數字（在位置 3 和 6）將被洗掉在我們在位置 7 的數字前面。因此，在這種情況下，我們的數字在串列中的位置向下移動了 n/(k 1) 和我們進入下一次迭代。
該演算法可以借助附加方法來表達，該方法采用兩個引數 - 步驟 k 和串列中數字的當前位置：
public static boolean isSpecial(int n)
{
return isSpecialOnStep(1, n);
}
private static boolean isSpecialOnStep(int k, int n)
{
if (k 1 > n)
return true;
if (n % (k 1) == 0)
return false;
return isSpecialOnStep(k 1, n - n / (k 1));
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/383348.html
上一篇：帶鑰匙的遞回拼圖