Рекурсия и циклы пока в Java - PullRequest
Новая
       76

Рекурсия и циклы пока в Java

1 голос
/ 17 марта 2020

Я пишу рекурсивную программу:

public static List<Integer> method(int n)

, чтобы определить, является ли положительное число n суммой кубов, которые являются положительными (> 0). Пример: учитывая n = 1944 (12 ^ 3 + 6 ^ 3), программа вернет список [12, 6] в порядке убывания. Если n не является суммой кубов, программа должна вернуть пустой список.

Программа должна возвращать значения, которые начинаются с максимально возможного значения для первого элемента, а затем продолжают следовать тому же правилу.

Мой код охватывает базовые случаи и рекурсию, но У меня проблемы с продолжением l oop. При вводе n = 1944 моя программа возвращает список [12] вместо [12, 6].

Ответы [ 2 ]

1 голос
/ 23 марта 2020

Давайте посмотрим на ваше время l oop: 

LinkedList<Integer> result = new LinkedList<Integer>();
boolean b = false;
// Some code omitted here.
while (b = false)
{
    c = (int) Math.cbrt(n - sum);
    seen.add(c);
    method(n, c, seen);
    if (sum == n)
    {
        result = seen;
        return true;
    }
    else
    {
        return false;
    }
}

Во-первых, с while l oop, который всегда имеет false в качестве условия цикла, он ничего не делает вообще.

В любом случае, даже если мы притворимся, что пробеги l oop, независимо от того, какая ветвь взяла if, return будет достигнуто. Итак, ваш while l oop вообще не l oop, даже если его условие было изменено на всегда true. Кроме того, единственное значение, когда-либо присвоенное переменной b, это false, и оно вообще ни для чего не используется.

Кроме того, список result во втором методе всегда пуст. И, поскольку инструкция result = seen; находится прямо перед return, это безобидная инструкция, которая делает result просто бесполезным.

Кроме того, посмотрите на вызов method(n, c, seen);. Он ничего не делает с его возвращаемым значением! Таким образом, даже если в конечном итоге он вернет true, вы все равно продолжите работу, в результате чего будет сгенерировано false.

Кроме того, всякий раз, когда вы добавляете значение к seen, оно никогда не будет удалено. Поскольку seen всегда является одним и тем же списком в каждом из рекурсивных вызовов методов, после добавления туда неправильного номера он никогда не будет удален, чтобы освободить место для чего-то другого.

С этим я Я должен заключить, что ваш алгоритм настолько сломан, что его нужно переписать с нуля.

Кроме того, хотя ваш вопрос не очень ясен, я предполагаю, что все найденные числа должны быть разными. В противном случае можно получить 2 = 1<sup>3</sup> + 1<sup>3</sup>, и каждое число, большее единицы, может быть представлено суммой множества кубов (т. Е. n = 1<sup>3</sup> + 1<sup>3</sup> + 1<sup>3</sup> + ...).

Алгоритм такой:

  • Первый шаг состоит в том, чтобы for считал i с cbrt(n) до 1, пытаясь сформировать кубы.
  • Затем вычтите куб из n и рекурсивно попытайтесь найти сумма куба для полученного числа.
  • Добавьте параметр, чтобы избежать повторения чисел, который на единицу меньше, чем последнее использованное число.
  • Когда куб сформирован, верните число, которое его сформировало. Во внешних вызовах добавьте результат в список непустых внутренних рекурсивных вызовов.
  • Если внутренний рекурсивный вызов выдает пустой список в качестве результата, то текущая итерация for вызвала ошибку число, и мы должны попробовать следующий (если у нас есть следующий).
  • Если for заканчивается без формирования куба, вернуть пустой список.

Вот код: 

import java.util.LinkedList;
import java.util.List;

public class Main {
    public static List<Integer> findCubeSum(int n) {
        return findCubeSum(n, n);
    }

    public static List<Integer> findCubeSum(int n, int max) {
        if (n <= 0) return List.of();
        int c = (int) Math.cbrt(n);
        for (int i = Math.min(c, max); i > 0; i--) {
            int x = i * i * i;
            if (x == n) {
                List<Integer> result = new LinkedList<>();
                result.add(i);
                return result;
            }
            List<Integer> result = findCubeSum(n - x, i - 1);
            if (result.isEmpty()) continue;
            result.add(0, i);
            return result;
        }
        return List.of();
    }

    public static void main(String[] args) {
        System.out.println(findCubeSum(8));    // [2]
        System.out.println(findCubeSum(64));   // [4]
        System.out.println(findCubeSum(1000)); // [10]
        System.out.println(findCubeSum(1072)); // [10, 4, 2]
        System.out.println(findCubeSum(1944)); // [12, 6]
        System.out.println(findCubeSum(4));    // []
        System.out.println(findCubeSum(0));    // []
        System.out.println(findCubeSum(-1));   // []
        System.out.println(findCubeSum(10));   // []
    }
}

См. это работает на ideone .

0 голосов
/ 17 марта 2020

Код, как опубликовано, имеет много проблем. Однако ваш вопрос о public static List<Integer> method(int n): 

public static List<Integer> method(int n)  {
    LinkedList<Integer> seen = new LinkedList<>();
    method(n, 0, seen);
    return seen;
}

Попробуйте изменить

private static boolean method(int n, int c, LinkedList<Integer> seen)

на

private static boolean method(int n, LinkedList<Integer> seen)

потому что вы пересчитываете значение c на c = (int) Math.cbrt(n);

...