BigInteger в ForL oop и списки в Java - PullRequest
Новая
       26

BigInteger в ForL oop и списки в Java

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

Я пытаюсь создать и вернуть список BigInteger, который вычисляет заданное целое число n в виде суммы чисел Фибоначчи в порядке убывания. Например, если дать целое число n = 8000, результат будет возвращать [6765, 987, 233, 13, 2].

Я написал код, который вычисляет числа Фибоначчи в список, в то время как указанное число меньше n, но Я не совсем понимаю, как реализовать все остальное.

Ответы [ 2 ]

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

Функция fib мне кажется слишком сложной. Просто вычислите следующий элемент из суммы двух последних элементов: 

public static List<BigInteger> fib(BigInteger n) {
    List<BigInteger> fibs = new ArrayList<>(asList(ONE, ONE));
    for (BigInteger last = ONE; last.compareTo(n) < 0; ) {
        last = last.add(fibs.get(fibs.size() - 2));
        fibs.add(last);
    }
    return fibs;
}

Затем go назад в списке и сохраните элементы, которые вписываются в сумму: 

public static void main(String[] args) {
    BigInteger n = BigInteger.valueOf(8000);
    List<BigInteger> fib = fib(n);
    BigInteger remaining = n;
    for (int i = fib.size() - 1; i >= 0; i--) {
        if (fib.get(i).compareTo(remaining) > 0) {
            fib.remove(i);
        } else {
            remaining = remaining.subtract(fib.get(i));
        }
    }
    Collections.reverse(fib);
    System.out.println(fib);
}
0 голосов
/ 12 марта 2020

Если вы напечатаете fibs, вы поймете, что l oop добавляет две 1, поэтому вам следует удалить строку {fibs.add(BigInteger.ONE); fibs.add(BigInteger.ONE);}.

Теперь, когда у вас есть все числа Фибоначчи, вы начинаете в конце списка и вычитать числа из n, пока значение не будет go отрицательным.

Самый простой способ перебрать список в обратном порядке, это перевернуть список и перебрать его как обычно . 

Collections.reverse(fibs);
for (BigInteger fib : fibs) {
    ...
}

Вы также можете сделать это, не переворачивая список, используя ListIterator для итерации в обратном направлении. 

for (ListIterator<BigInteger> iter = fibs.listIterator(fibs.size()); iter.hasPrevious(); ) {
    BigInteger fib = iter.previous();
    ...
}

Чтобы найти числа, которые можно вычесть из n просто оставьте текущее значение того, что еще нужно уменьшить, т. е. сколько из исходного b остается . 

BigInteger remain = n;
for (BigInteger fib : fibs) {
    if (fib.compareTo(remain) <= 0) {  // if (fib <= remain)
        remain = remain.subtract(fib); //   remain -= fib;
    }
}

Добавьте значения, которые вычтите, в список результатов, и все готово.

...