如何改進此代碼？

Question

我已經開發了一個代碼，用於表示2的權力的數字，我在下面附上相同的代碼。

但問題是，表達的輸出應該是最小長度。

我得到的輸出爲3^2+1^2+1^2+1^2，這不是最小長度。 我需要輸出格式爲：

package com.algo; 
import java.util.Scanner; 

public class GetInputFromUser { 
    public static void main(String[] args) { 
    // TODO Auto-generated method stub 
     int n; 
     Scanner in = new Scanner(System.in); 

     System.out.println("Enter an integer"); 
     n = in.nextInt(); 

     System.out.println("The result is:"); 
     algofunction(n); 
    } 

    public static int algofunction(int n1) 
    { 
     int r1 = 0; 
     int r2 = 0; 
     int r3 = 0; 
     //System.out.println("n1: "+n1); 
     r1 = (int) Math.sqrt(n1); 
     r2 = (int) Math.pow(r1, 2); 
     // System.out.println("r1: "+r1); 
     //System.out.println("r2: "+r2); 
     System.out.print(r1+"^2"); 

     r3 = n1-r2; 
     //System.out.println("r3: "+r3); 
     if (r3 == 0) 
      return 1; 

     if(r3 == 1) 
     { 
      System.out.print("+1^2"); 
      return 1; 
     } 
     else { 
      System.out.print("+"); 
      algofunction(r3); 
      return 1; 
     } 
    } 
} 

Answer 1

動態編程是所有關於這樣一種方式，如果你知道答案，原來的縮小版，你可以用它來回答的主要問題定義問題更快/更直接。這就像應用數學歸納。

在您的特定問題中，我們可以將MinLen（n）定義爲n的最小長度表示。接下來說，既然我們想解MinLen（12），假設我們已經知道了MinLen（1），MinLen（2），MinLen（3），...，MinLen（11）的答案。我們如何用這些小問題的答案來找出MinLen（12）？這是動態規劃的另一半 - 弄清楚如何使用較小的問題來解決更大的問題。如果你想出一些小問題，但它無法幫助你，但無法將它們結合在一起。

對於這個問題，我們可以做一個簡單的說法，「對於12，它是最小長度表示DEFINITELY中有1^2，2^2或3^2。」一般而言，n的最小長度表示將作爲其一部分具有小於或等於n的一些正方形。可能會有更好的語句可以提高運行時間，但我會說現在已經足夠好了。 MinLen（12）= 1^2 + MinLen（11），OR 2^2 + MinLen（8），OR 3^2 + MinLen（3）這個表述意味着MinLen（12）= 1^2 + MinLen（11），OR2^2 + MinLen你檢查它們並選擇最好的一個，現在你將它保存爲MinLen（12）。現在，如果你想解決MinLen（13），你也可以這樣做。

獨奏時的建議： 我自己測試這種程序的方式是插入1,2,3,4,5等，看看它第一次出錯。此外，我碰巧想到的任何假設都是一個好主意，我質疑：「小於n的最大平方數是否會代表MinLen（n）？」是真的嗎？「

您的代碼：

r1 = (int) Math.sqrt(n1); 
r2 = (int) Math.pow(r1, 2); 

體現了這一假設（貪婪的假設），但它是錯誤的，因爲你已經清楚地回答了MinLen（12）可見。

相反，你想要更多的東西是這樣的：

public ArrayList<Integer> minLen(int n) 
{ 
    // base case of recursion 
    if (n == 0) 
     return new ArrayList<Integer>(); 

    ArrayList<Integer> best = null; 
    int bestInt = -1; 
    for (int i = 1; i*i <= n; ++i) 
    { 
     // Check what happens if we use i^2 as part of our representation 
     ArrayList<Integer> guess = minLen(n - i*i); 

     // If we haven't selected a 'best' yet (best == null) 
     // or if our new guess is better than the current choice (guess.size() < best.size()) 
     // update our choice of best 
     if (best == null || guess.size() < best.size()) 
     { 
      best = guess; 
      bestInt = i; 
     } 
    } 

    best.add(bestInt); 
    return best; 
} 

然後，一旦你有你的列表，你可以對它進行排序（不能保證它排在排序順序），並打印出來，你想要的方式。

最後，您可能會注意到，對於插入上述遞歸的較大n值（1000可能太大），它將開始非常緩慢。這是因爲我們不斷重新計算所有小的子問題 - 例如，當我們稱MinLen（4）時，我們計算出MinLen（3），因爲4 - 1^2 = 3。但是我們計算出MinLen（7） - > 3 = 7 - 2^2，但3也是7 - 1^2 - 1^2 - 1^2 - 1^2。越大，它越糟糕。

解決這個問題的方法是讓您快速解決n = 1,000,000或更多的問題，即使用名爲Memoization的技術。這意味着一旦我們找出MinLen（3），我們將它保存在某個地方，讓我們假設一個全球位置來讓它變得容易。然後，每當我們嘗試重新計算它，我們首先檢查全局緩存，看看我們是否已經做到了。如果是這樣，那麼我們只是使用它，而不是重做所有的工作。

import java.util.*; 

class SquareRepresentation 
{ 
    private static HashMap<Integer, ArrayList<Integer>> cachedSolutions; 
    public static void main(String[] args) 
    { 
     cachedSolutions = new HashMap<Integer, ArrayList<Integer>>(); 
     for (int j = 100000; j < 100001; ++j) 
     { 
      ArrayList<Integer> answer = minLen(j); 
      Collections.sort(answer); 
      Collections.reverse(answer); 
      for (int i = 0; i < answer.size(); ++i) 
      { 
       if (i != 0) 
        System.out.printf("+"); 
       System.out.printf("%d^2", answer.get(i)); 
      } 
      System.out.println(); 
     } 
    } 

    public static ArrayList<Integer> minLen(int n) 
    { 
     // base case of recursion 
     if (n == 0) 
      return new ArrayList<Integer>(); 

     // new base case: problem already solved once before 
     if (cachedSolutions.containsKey(n)) 
     { 
      // It is a bit tricky though, because we need to be careful! 
      // See how below that we are modifying the 'guess' array we get in? 
      // That means we would modify our previous solutions! No good! 
      // So here we need to return a copy 
      ArrayList<Integer> ans = cachedSolutions.get(n); 
      ArrayList<Integer> copy = new ArrayList<Integer>(); 
      for (int i: ans) copy.add(i); 
      return copy; 
     } 

     ArrayList<Integer> best = null; 
     int bestInt = -1; 
     // THIS IS WRONG, can you figure out why it doesn't work?: 
     // for (int i = 1; i*i <= n; ++i) 
     for (int i = (int)Math.sqrt(n); i >= 1; --i) 
     { 
      // Check what happens if we use i^2 as part of our representation 
      ArrayList<Integer> guess = minLen(n - i*i); 

      // If we haven't selected a 'best' yet (best == null) 
      // or if our new guess is better than the current choice (guess.size() < best.size()) 
      // update our choice of best 
      if (best == null || guess.size() < best.size()) 
      { 
       best = guess; 
       bestInt = i; 
      } 
     } 

     best.add(bestInt); 

     // check... not needed unless you coded wrong 
     int sum = 0; 
     for (int i = 0; i < best.size(); ++i) 
     { 
      sum += best.get(i) * best.get(i); 
     } 
     if (sum != n) 
     { 
      throw new RuntimeException(String.format("n = %d, sum=%d, arr=%s\n", n, sum, best)); 
     } 

     // New step: Save the solution to the global cache 
     cachedSolutions.put(n, best); 

     // Same deal as before... if you don't return a copy, you end up modifying your previous solutions 
     // 
     ArrayList<Integer> copy = new ArrayList<Integer>(); 
     for (int i: best) copy.add(i); 
     return copy; 
    } 
} 

花了我的程序約5秒跑n = 100,000。顯然，如果我們希望速度更快，並且要解決更大的問題，還有更多的工作要做。現在的主要問題是，在存儲以前答案的全部結果列表時，我們用盡了大量內存。而所有這些複製！你可以做更多的事情，比如只存儲一個整數和一個指向子問題的指針，但我會讓你這樣做。

而由by，1000 = 30^2 + 10^2。