4

与えられた数が与えられた集合の合計であるかどうかを見つけようとしています。たとえば、次の理由により、数12は集合の合計です。s{3,2}

3+3+3+3=12
or
2+2+2+2+2+2=12

ただし、で数値を作成できないため14、の合計ではありません。再帰のみを使用し、ループを使用せずにJavaでコードを記述しようとしています。コードは次のとおりです。s{8,10}14sums of s

   public static boolean isSumOf(int[]s,int n)
   {
     return isSumOf(s,n,0,0,0);
   }


   private static boolean isSumOf(int[]s,int n,int i,int sum,int m)
   {
       boolean with=false;
       boolean without=false;

       if(i==s.length)
        return false;

       if(sum==n)   
        return true;

       if(m<=n)
        {
            with=isSumOf(s,n,i,sum+s[i]*m,m++);
            without=isSumOf(s,n,i,sum,m++);            
        }
       else
        {
            i=i++;
            m=0;
            isSumOf(s,n,i,sum,m);
        }

       return (with||without); 

   }

コードは正常にコンパイルされていますが、テストを実行するとstackOverFlowErrorが発生します。テストのコードは次のとおりです。

  public static void main(String[]args)
  {  
      int[]a={18,10,6};
      int x=18+10+6;
      System.out.println(Ex14.isSumOf(a,x));
  }

助けてください！！！

4

3 に答える 3

2

これは悪く見えます：

with=isSumOf(s,n,i,sum+s[i]*m,m++);
without=isSumOf(s,n,i,sum,m++);

使用する

with=isSumOf(s,n,i,sum+s[i]*m,++m);
without=isSumOf(s,n,i,sum,++m);

m呼び出されたメソッドで1つ高くしたい場合。

それ以外は、変数の命名が不十分なため、コードが何をするのかわかりません。

また、この行：

i=i++;

効果はありません。インクリメントする場合は、次のいずれかに置き換えてくださいi。

i++;
i += 1;
i = i + 1;
i = ++i;

そして、あなたが呼び出しの結果を使用しない場合

isSumOf(s,n,i,sum,m);

それを呼んでも意味がありません。

于 2012-11-30T09:02:43.467 に答える
0

これはうまくいくようです-そして、あなたが既成の答えを望まないという兆候は見られません（これが宿題だったらあなたが言うと確信しています）ので、ここに行きます：

public class IsSumOf {
  // set - The numbers allowed.
  // total - The number I want to achieve.
  // i - Where we are in the set.
  // sum - List of numbers used so far.
  // n - The number we just subtracted (or 0 if none).
  // Note that sum and n are only used for the printing of the route.
  private static boolean isSumOf(int[] set, int total, int i, LinkedList<Integer> sum, int n) {
    // Found the set if we are now at 0.
    boolean is = (total == 0);
    // Look no further if no more to try.
    if ( total > 0 ) {
      // Look no further if we've exhausted the array.
      if ( i < set.length ) {
        // Try or consume this number in the set (or not) and try again.
        is = isSumOf(set, total - set[i], i, sum, set[i] ) 
                || isSumOf(set, total - set[i], i+1, sum, set[i] ) 
                || isSumOf(set, total, i+1, sum, 0 ) ;
      }
    }
    // Keep track of the route.
    if ( is && sum != null && n != 0) {
      // Add backwards so we get the order right when printed.
      sum.addFirst(n);
    }
    return is;
  }

  // Jump-off point.
  public static boolean isSumOf(int[] set, int total, LinkedList<Integer> sum) {
    // Empty the list.
    sum.clear();
    // Start at 0 in the array.
    return isSumOf(set, total, 0, sum, 0);
  }

  public static void main(String[] args) {
    LinkedList<Integer> sum = new LinkedList<Integer>();
    int[] a = {18, 10, 6};
    int x = 18 + 10 + 6;
    System.out.println(Arrays.toString(a)+" ("+x+") = "+(isSumOf(a, x, sum)?Arrays.toString(sum.toArray()):"-"));
    x += 1;
    System.out.println(Arrays.toString(a)+" ("+x+") = "+(isSumOf(a, x, sum)?Arrays.toString(sum.toArray()):"-"));
    int[] b = {3,2};
    x = 12;
    System.out.println(Arrays.toString(b)+" ("+x+") = "+(isSumOf(b, x, sum)?Arrays.toString(sum.toArray()):"-"));
    x += 1;
    System.out.println(Arrays.toString(b)+" ("+x+") = "+(isSumOf(b, x, sum)?Arrays.toString(sum.toArray()):"-"));
    int[] c = {2,3};
    x = 12;
    System.out.println(Arrays.toString(c)+" ("+x+") = "+(isSumOf(c, x, sum)?Arrays.toString(sum.toArray()):"-"));
    x += 1;
    System.out.println(Arrays.toString(c)+" ("+x+") = "+(isSumOf(c, x, sum)?Arrays.toString(sum.toArray()):"-"));
  }
}

たどったルートを印刷するように編集しました。

プリント：

[18, 10, 6] (34) = [18, 10, 6]
[18, 10, 6] (35) = -
[3, 2] (12) = [3, 3, 3, 3]
[3, 2] (13) = [3, 3, 3, 2, 2]
[2, 3] (12) = [2, 2, 2, 2, 2, 2]
[2, 3] (13) = [2, 2, 2, 2, 2, 3]
于 2012-11-30T10:13:32.933 に答える
0

少し違う戦略を使います

public static void main(String[] args)
{
    int[] s = { 4, 5 };
    System.out.println(isSumOf(s, 13)); // true
    System.out.println();

    int[] s1 = { 4, 9, 3 };
    System.out.println(isSumOf(s1, 15)); // true
    System.out.println();

    int[] s2 = { 4, 9, 3 };
    System.out.println(isSumOf(s2, 5)); // false
    System.out.println();

    int[] s3 = { 3, 2 };
    System.out.println(isSumOf(s3, 12)); // true
    System.out.println();

    int[] s4 = { 8, 10 };
    System.out.println(isSumOf(s4, 14)); // false
    System.out.println();
}

public static boolean isSumOf(int[] s, int n)
{
    return isSumOf(s, n, 0, 0, "");
}

private static boolean isSumOf(int[] s, int n, int i, int sum, String builder)
{
    if (sum == n) // if we found a subset
    {
        System.out.println(builder);
        return true;
    }

    if (i == s.length || sum > n) // 1. boundaries checks 2. if subset is greater then n
        return false;

    boolean with = isSumOf(s, n, i, sum + s[i], builder + s[i] + " "); // try to sum "s[i]", note that we can sum the
                                                                        // same "s[i]" multiple times

    boolean without = isSumOf(s, n, i + 1, sum, builder); // try to skip "s[i]" and instead to sum "s[i+1]"

    return with || without;
}
于 2021-05-05T16:33:39.537 に答える