java - 和と積への整数分割

Question

これが私がする必要があることです:与えられた整数を合計と積に分割するアルゴリズムを書きますが、その後の各数値は前のものよりも大きくなければなりません:

6 = 1+5;
6 = 1+2+3;
6 = 1*2+4;
6 = 2+4;
6 = 2*3;

基本的なパーティション整数アルゴは、異なる順序で数値を返すため、機能しません。

私は最終的なコードを求めているわけではありません。自分で先に進むことができるように、いくつかのヒントやアドバイスを求めているだけです。よろしくお願いします！

Answer 1

public class Perms {

/**
 * @param args
 */
public static int x;
public static void main(String[] args) {
    // TODO Auto-generated method stub

    x = 6;
    rec(x, new int[1000], new String[1000], 0);
}

public static void rec(int n, int all[], String operator[], int size)
{
       if (n==0)
       {
          if (size==1)return;
          System.out.print(x + " =");
          for (int i=0;i<size;i++)
          {
             System.out.print(" " + all[i]);
             if (i!=size-1)
                 System.out.print(" " + operator[i]);
          }
          System.out.println();
          return;
       }
       int i=1;
       if (size>0)
          i = all[size-1]+1;
       for ( ;i<=n;i++)
       {
          operator[size] = "+";
          all[size] = i;
          rec(n-i, all, operator, size+1);
       }

       i=1;
       if (size>0)
          i = all[size-1]+1;
       for (;i<=n;i++)
       {
          float r = n/(float)i;
          if (r == (int)r)
          {
             operator[size] = "*";
             all[size] = i;
             rec(n/i, all, operator, size+1);
          }
       }
    }
}

出力：

6 = 1 + 2 + 3
6 = 1 + 5
6 = 2 + 4
6 = 1 * 2 + 4
6 = 1 * 6
6 = 1 * 2 * 3
6 = 2 * 3

注:操作には優先順位があります (操作は右から左に評価されます)。

例: 20 = 2 * 3 + 7 = (2 * (3 + 7)) = 2 * 10 = 20。

これらの括弧を追加するのは簡単です。ただし、出力は見苦しくなります。そのことに注意するだけで良いです。