アルゴリズム：Yに

Question

私たちはこの問題を少し切り替える場合 http://www.geeksforgeeks.org/minimum-number-of-power-terms-with-sum-equal-to-n/

は私が思ってを開始、このgeeksforgeeksページを読んで、代わりになっていた最小数を合計してもらうパワーXとの用語の最小数を返します私たちは関数minPower（power、sum）を書きます：

minPower（2,7）は、7 = 2^2 + 1^2 + 1^2 + 1^2

minPower（2,9）は、9 = 3^2であるため、1を返します。

9 = 2^3 + 1^3のためminPower（3,9）は2を返します

このような関数はどのように記述しますか？

Answer 1

これを解決する最も簡単な方法は、再帰的なグリーディアルゴリズムを使用して、m <= sumのm = p^nを削除し、sumが0になるまで解決します。 p 1.最低限の項で解を受け入れます。あなたがここにいくつかのJavaコードを説明するためにだ用語pow(10, log10(sum)/n)

を使用してpの可能な最大値を見つけることができます

：

public static void main(String[] args) 
{  
    minPower(2, 7); 
} 

public static void minPower(int n, int sum) 
{ 
    if(n < 1) throw new IllegalArgumentException(); 

    int maxPow = (int)Math.pow(10, Math.log10(sum)/n); 

    List<Integer> min = new ArrayList<>(); 
    LinkedList<Integer> terms = new LinkedList<>(); 
    powers(n, sum, maxPow, terms, min);  
    System.out.println(min); 
} 

private static void powers(int n, int sum, int m, LinkedList<Integer> terms, List<Integer> min) 
{ 
    if(sum == 0) 
    { 
     if(min.isEmpty() || terms.size() < min.size()) 
     { 
      min.clear(); 
      min.addAll(terms); 
     } 
     return; 
    } 
    else if(sum < 0) return; 

    for(int i=m; i>0; i--) 
    { 
     terms.addLast(i); 
     powers(n, sum - (int)Math.pow(i, n), i, terms, min); 
     terms.removeLast(); 
    } 
} 

出力：

2,7 
[2, 1, 1, 1] 

2, 9 
[3] 

3, 9 
[2, 1] 

3, 32 
[2, 2, 2, 2]