10

这是我需要做的：编写一个算法，将给定的整数分成总和和乘积，但后面的每个数字都必须大于前一个数字，即：

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

基本的分区整数算法不起作用，因为它以不同的顺序返回数字。

我不是要最终的代码，我只是要一些技巧和建议，这样我就可以继续自己了。非常感谢您！

4

4 回答 4

2 
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。

添加这些括号很容易。但是，输出看起来很难看。只是注意到那更好。

于 2013-10-28T23:00:06.213 回答
1

这是一个想法：

使用动态编程，您可以存储所有写入数字的有效方式。然后，要计算写入更大数字的有效方法，请使用之前的结果。递归地工作得很好。

假设 valid(x) 是计算 x 的所有有效书写方式的函数。递归：

valid(x) =
1 if x == 1
Or the entire collection of:
For i = 1 to x/2
valid(i) + (x-i)
And
For i = all divisors of x <= sqrt(x)
valid(x) * x/i

我不认为你可以比这更有效地计算。此外，请务必记住（存储在内存中）valid(x) 的渐进式计算。

编辑：忘记了 7 = 1 + 2 * 3 和其他类似的情况。看起来上面的答案效果更好。

于 2013-10-28T23:08:56.793 回答
1

这是我带来的，这是一种非常低效的蛮力方法。它打印出来：

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

资源：

package com.sandbox;

import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class Sandbox {

    public static void main(String[] args) {
        int n = 6;

        List<List<Integer>> numberPermutations = Permutations.getPermutations(n);
        for (Iterator<List<Integer>> iterator = numberPermutations.iterator(); iterator.hasNext(); ) {
            List<Integer> permutation = iterator.next();
            if (permutation.size() <= 1) {
                iterator.remove();  //remove x = x
            }
        }

        Set<List<Character>> symbolPermutations = Permutations.getSymbols(n); //outputs (+), (*), (++), (+*), (*+), (**), ...

        for (List<Integer> numberPermutation : numberPermutations) {
            for (List<Character> symbolPermutation : symbolPermutations) {
                if (numberPermutation.size() - 1 == symbolPermutation.size()) {    //eg: if you've got 1, 2, 3, 4, 5, 6 as numbers, then you want the symbols between them like +, *, *, *, +.  Notice there's one less symbol than the numbers
                    int sum = numberPermutation.get(0);
                    String equation = sum + "";
                    for (int i = 1; i < numberPermutation.size(); i++) {
                        Integer thisInt = numberPermutation.get(i);
                        if (symbolPermutation.get(i - 1) == '+') {
                            sum += thisInt;
                            equation += " + " + thisInt;
                        } else {
                            sum *= thisInt;
                            equation += " * " + thisInt;
                        }
                    }
                    if (sum == n) {
                        System.out.println(sum + " = " + equation);
                    }
                }
            }
        }
    }

}

我将把排列留给读者。

于 2013-10-29T00:01:22.003 回答
0

好吧，我正在为其他有类似（不同）问题的人编写代码，他在我发布之前删除了:)。

所以我有一个代码给你，它做类似的事情，你应该能够将它更改为你想要的任何东西。

此代码显示了给定数量的总和的所有可能性，例如对于数字 7 和数量为 4，它会打印以下结果：

7 = 4+1+1+1
7 = 3+2+1+1
7 = 2+3+1+1
7 = 1+4+1+1
7 = 3+1+2+1
7 = 2+2+2+1
7 = 1+3+2+1
7 = 2+1+3+1
7 = 1+2+3+1
7 = 1+1+4+1
7 = 3+1+1+2
7 = 2+2+1+2
7 = 1+3+1+2
7 = 2+1+2+2
7 = 1+2+2+2
7 = 1+1+3+2
7 = 2+1+1+3
7 = 1+2+1+3
7 = 1+1+2+3
7 = 1+1+1+4

我希望使用这个想法并将其更改为您需要的内容应该不难。

public class JavaApplication25 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int terms = 4;
        int sum = 7;
        int[] array = new int[terms];
        for (int i = 0; i < terms; i++) {
            array[i] = 1;
        }
        boolean end = false;
        int total = 0;
        while (end == false){
            if (sumAr(array) == sum){
                print(array,sum);
                total++;
            }
            end = increase(array, sum);
        }
        System.out.println("Total numbers: " + total);
    }

    public static void print(int[] array, int sum){
        System.out.print(sum + " = ");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i != array.length-1){
                System.out.print("+");
            }
        }
        System.out.println("");
    }

    public static boolean increase(int[] array, int max){
        for (int i = 0; i < array.length; i++) {
            if (array[i] != max){
                array[i]++;
                for (int j = i-1; j >= 0; j--) {
                    array[j]=1;
                }
                return false;
            }
        }
        return true;
    }

    public static int sumAr(int[] array){
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
        }
        return sum;
    }
}

提示：如果您不关心有效性，您可以为所有可能的术语运行此代码（对于数字 7，它可以是 1-7 个术语）并添加一些 if 语句，它会丢弃您不想要的值（下一个数字必须高于以前）

于 2013-10-28T22:40:40.997 回答