Как реализовать механизм перебора уникальных значений в массиве с помощью рекурсии? (для решения задачи поиска чисел Армстронга)
Задача такова: нужно найти все числа Армстронга, меньше N. Один источник подсказал, что перебор "уникальных" комбинаций можно осуществить с помощью массива long[], длинной в N ячеек. Сначала заполняем все ячейки числом 9. Затем проводится уменьшение на 1 значения в [0] элементе массива до тех пор, пока это значение не достигнет 0. Тогда уменьшается значение элемента с индексом [1], а все предыдущие элементы также получают это новое значение. Пример: [0, 9, 9] становится [8, 8, 9]. После этого массив снова декрементируется по описанной выше схеме, начиная с [0] элемента.
Что-то подсказывает что это проще реализовать через рекурсию, но как?
Пока получился только такой корявый кусок кода:
int[] target = new int[numbLength(N)];
Arrays.fill(target, 9);
// очередная попытка написать рабочий цикл
for (int i = 0; i < target.length; i++) {
for (int j = 8; j >= 0 ; j--) {
for (int k = i; k >= 0; k--)
target[k] = j;
if (i != 0) {
for (int m = target[0]; m >= 0; m--) {
target[0] = m;
System.out.println(Arrays.toString(target));
}
}
else
System.out.println(Arrays.toString(target));
}
}
Ответы (1 шт):
В своё время решал по схеме предложенной тут.
По Вашему предложению. Массив скорее всего (это не точно) придётся копировать по значению, а не по ссылке. Если это не сделать, то это может привести к непонятным изменениям в самом массиве. На этом утверждении не настаиваю, т.к. точно не уверен в нём. Но если это так, то это дикие, для данной задачи, накладные расходы на память. Один массив int длиной 1E6 это 4Mb. И это умножить на количество рекурсий.
Не знаю какие условия у Вас стоят, но когда я её решал, то меня ограничивали по времени и памяти. И как по мне задача не особо напрашивается на рекурсию.
З.Ы. К делу абсолютно не относится, но сама задача абсолютно бесполезная. Единственный её плюс - понимание того, что тупой перебор - плохой вариант. И всё. Это не стоит затраченного времени на реализацию и попытку придумать что-то интересное:(