最大的連續奇數整數等於一個目標

我目前正在尋找最大數量的連續奇數加在一起以等於一個目標數量。最大的連續奇數整數等於一個目標

我當前的代碼找到連續3個整數看起來像

public class consecutiveOdd { 
    public static void main(String[] args){ 
     int target = 160701; 
     boolean found = false; 

     for(int i = 1; i < target; i++){ 
      if(i + (i+2) + (i+4) == target){ 
       System.out.print(i + " + " + (i+2) + " + " + (i+4)); 
       found = true; 
      } 

     } 
     if(!found){ 
      System.out.println("Sorry none"); 
     } 
    } 
}

我想會有必須的（I + 2）增量while循環建築物迭代但我有開發一種正確的算法麻煩。任何幫助或提示將非常感謝！

最佳， Otterman

來源

2015-10-13 Otterman

您的循環要去看看奇集{1，3，5}也是甚至集{2,4,6}。所以你可能想說i + = 2而不是i ++。順便說一句，我喜歡上面的數學解決方案，而不僅僅是蠻力搜索。 – rajah9

http://mathforum.org/library/drmath/view/65469.html –

供參考：答案是** 391 **：'21 + 23 + 25 + ... + 799 + 801 = 160701' – Andreas

比方說，答案是等於k (k > 0)。然後對於一些奇怪的i，我們可以寫：i + (i + 2) + (i + 4) + ... + (i + 2k - 2) = target。你可以看到這是一個總和arithmetic progression，因此你可以使用一個衆所周知的公式來計算它。應用公式我們可以得到： i = target/k - k + 1。

在此基礎上公式我建議如下算法：

迭代的k值。
如果target/k - k + 1是一個正奇數，更新答案。

簡單的實現。

int answer = -1; 
for (int k = 1;; k++) { 
    int i = target/k - k + 1; 
    if (i <= 0) { 
     break; 
    } 
    // Check if calculated i, can be the start of 'odd' sequence. 
    if (target % k == 0 && i % 2 == 1) { 
     answer = k; 
    } 
}

該算法的運行時間爲O(sqrt(target))。

來源

2015-10-13 22:30:53

綜觀圖案：

對於1被加數，i = target
對於2個加數，該方程爲2*i + 2 = target，所以i = (target - 2)/2
對於3個被加數，該方程爲3*i + 6 = target，所以i = (target - 6)/3
對於4個加數，th Ë方程是4*i + 12 = target，所以i = (target - 12)/4

等等顯然i必須在所有情況下的奇整數。

你可以制定出一般表達式n被加數，並簡化它向你展示一個算法，但你也許能夠看到一個算法已經...

應用@ Rossum的建議：

對於1個被加數，2m + 1 = target
對於2個被加數，2m + 1 = (target - 2)/2，所以m = (target - 4)/4
對於3加數，2m + 1 = (target - 6)/3，所以m = (target - 9)/6
對於4個加數，2m + 1 = (target - 12)/4，所以m = (target - 16)/8

來源

2015-10-13 21:32:33

根據問題顯然'i'在所有情況下都必須是* odd *整數。使用替代'i = 2m + 1'並解決'm'來放寬要求。這樣'm'可以是奇數或偶數。 – rossum

@rossum整潔的建議，我已經添加到答案。 –

的n奇數序列的總和，可以乘以值（n）的數目的平均值（中點m）來計算，所以：

sum = 5 + 7 + 9  = m * n = 7 * 3 = 21 
sum = 5 + 7 + 9 + 11 = m * n = 8 * 4 = 32

如果n是奇數然後m將是奇數，並且如果n甚至然後m將是偶數。

的first和last數字序列可以計算爲：

first = m - n + 1 = 8 - 4 + 1 = 5 
last = m + n - 1 = 8 + 4 - 1 = 11

其他有趣的公式：

m = sum/n 
m = (first + last)/2 
last = first + (n - 1) * 2 = first + 2 * n - 2 
m = (first + first + 2 * n - 2)/2 = first + n - 1

的最長序列將不得不開始與可能的最低first值，意思是1，所以我們得到：

sum = m * n = (first + n - 1) * n = n * n

這意味着任何給定sum的最長序列長度至多可以是sqrt(sum)。

於是開始sqrt(sum)和搜索，直到我們找到一個有效的n：

/** 
    * Returns length of sequence, or 0 if no sequence can be found 
    */ 
private static int findLongestConsecutiveOddIntegers(int sum) { 
    for (int n = (int)Math.sqrt(sum); n > 1; n--) { 
     if (sum % n == 0) { // m must be an integer 
      int m = sum/n; 
      if ((n & 1) == (m & 1)) // If n is odd, mid must be odd. If n is even, m must be even. 
       return n; 
     } 
    } 
    return 0; 
}

結果：

n = findLongestConsecutiveOddIntegers(160701) = 391 
m = sum/n = 160701/391 = 411 
first = m - n + 1 = 411 - 391 + 1 = 21 
last = m + n - 1 = 411 + 391 - 1 = 801

由於sqrt(160701) = 400.875...，結果在迭代發現（ 400至391，含）。

結論：連續奇數的，以平等160701

金額最大：

21 + 23 + 25 + ... + 799 + 801 = 160701

來源

2015-10-13 22:35:03 Andreas

最大的連續奇數整數等於一個目標

回答

相關問題