Integer раздел в суммы и продукты
Вот что мне нужно сделать: напишите алгоритм, который разделит заданное целое число на суммы и продукты, но каждое следующее число должно быть больше предыдущего, т.е.
6 = 1+5;
6 = 1+2+3;
6 = 1*2+4;
6 = 2+4;
6 = 2*3;
Базовое целочисленное целое число не будет работать, поскольку оно возвращает числа в другом порядке.
Я не прошу окончательного кода, я просто прошу советов и советов, чтобы я мог двигаться дальше. Большое вам спасибо заранее!
Ответы
Ответ 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.
Легко добавить те круглые скобки. но выход будет выглядеть уродливым. Просто отметив, что это лучше.
Ответ 2
Вот идея:
Используя динамическое программирование, вы можете сохранить все допустимые способы записи числа. Затем, чтобы вычислить допустимые способы записи большего числа, используйте результаты из предыдущего. Будет работать рекурсивно.
Скажем, что 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
Я не думаю, что вы можете рассчитать гораздо эффективнее, чем это. Кроме того, не забудьте запомнить (сохранить в памяти) прогрессивные вычисления действительного (x).
РЕДАКТОР: Забыл о случае 7 = 1 + 2 * 3 и другим нравится. Похоже, что вышеприведенный ответ работает лучше.
Ответ 3
Вот что я пришел, это очень неэффективный метод грубой силы. Он напечатал это:
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 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);
}
}
}
}
}
}
Я оставлю перестановки для читателя.
Ответ 4
Ну, я писал код для кого-то другого с похожим (не одинаковым) вопросом, и он стирался, прежде чем я его разместил:).
Итак, у меня есть код для вас, который делает аналогичную вещь, и вы должны иметь возможность изменить его на все, что хотите.
Этот код показывает все возможности суммирования с заданным числом членов, например для числа 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-statement, который отбрасывает значения, которые вы не хотите (что следующее число должно быть выше предыдущего)
