Прежде всего, извините за свое форматирование, я не могу использовать изображения для отображения уравнений, потому что это мой первый пост.
Начнем с обзора Collatz Conjecture. Мы знаем, что рассматриваемый ряд называется серией галоидов по отношению к поведению всех чисел 2 n где n - положительное целое число. Серия определяется путем рекурсивного изменения значения на основе того, является ли значение нечетным или четным.
- Если число четное, разделить его на две части.
- Если число нечетное, утроите его и добавьте.
Чтобы обратить вспять этот процесс, существует потенциально два результата для одного числа. Например, как 5 и 32 оценки до 16.
- 5 нечетно, (3 * 5) + 1 = 16
- 32 четно, 32/2 = 16
Чтобы найти обратную функцию, мы должны учитывать, что для каждого числа может быть два ответа. Нам также необходимо определить, какой правильный ответ. Действительный ответ от обратной функции должен быть быть положительным, целым числом.
Теперь мы делаем некоторую алгебру, чтобы прийти к обратным. Определите a как результат одной итерации серии Halestone.
Решить для п:
н
3n + 1 = а 2 = а
а - 1
п = п = 2а
Итак, теперь у нас есть новые правила. Мы знаем, что n = 2a всегда будет оцениваться положительным целым числом, поэтому это выражение всегда верно. Однако другое уравнение оценивает только положительное целое число, если a - 1 делится на 3. Каждый другой экземпляр не собирается возвращать целое целое число, а скорее обращается к бесконечному числу трех или шести. Эти десятичные числа неприемлемы и будут выброшены. Обратите внимание, как входное значение 4 возвращает 1 в качестве одного из ответов
Чтобы начать думать о коде, мы должны разложить предложенное дерево на слои. Аналогично горизонтальному расслоению this image. Для каждой итерации каждая ветвь может разделиться на две отдельные ветви. Это означает, что нам нужно хранить неизвестное количество чисел, когда мы перебираем дерево.
Это то, что я придумал. По сути, это все еще просто поток данных, который нужно отформатировать во что-то читаемое. Он должен потерпеть неудачу, если используется либо размер стека, либо количество параллельных ветвей превышает 2 - 1. Это связано с характером массивов.
public static void main(String args[]) throws InterruptedException {
ArrayList<BigInteger> tree = new ArrayList<BigInteger>();
tree.add(BigInteger.valueOf(2));
System.out.println(1);
while (true) {
// Store a snapshot of the current tree so new branches created don't mess with
// the iteration process.
BigInteger[] originalTree = tree.toArray(new BigInteger[tree.size()]);
// Keep track of new branches added during each step for index alignment in
// the stepping method.
int newBranchCount = 0;
// Iterate over the values of the original tree.
for(int i = 0; i < originalTree.length; i++) {
// Evaluate branch
stepBranch(tree, originalTree[i], i + newBranchCount);
// Update branch count after step.
newBranchCount = tree.size() - originalTree.length;
}
}
}
/*
* Given the tree to mutate, a value from a mutation free version of the tree,
* and the current working index of the tree:
* Evaluate whether or not to add a new odd valued branch and report new value(s).
*/
public static void stepBranch(ArrayList<BigInteger> tree, BigInteger branch, int index) throws InterruptedException {
// If (n + 1) is divisible by three, do so and create a new branch to store the new value
if (branch.subtract(BigInteger.ONE).mod(BigInteger.valueOf(3)).equals(BigInteger.ZERO)) {
// If the input is 4, the output is 1 which appears earlier, therefore requires no attention.
if(!branch.equals(BigInteger.valueOf(4))) {
// Create new value.
BigInteger odd = branch.subtract(BigInteger.ONE).divide(BigInteger.valueOf(3));
// If the output is even, it doesn't fit the requirements for an odd cell.
if(!odd.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
tree.add(index + 1, odd);
System.out.println(tree.get(index + 1));
}
} else {
System.out.println(1);
}
Thread.sleep(500);
}
// The original branch, not considering a new branch if one was created, is
// multiplied by 2 so as to check for a new odd node in the next iteration.
tree.set(index, branch.multiply(BigInteger.valueOf(2)));
System.out.println(tree.get(index));
Thread.sleep(500);
}
Надеюсь, это помогло!
Вы изменяете только число, если оно делится на 2 или 3. Цикл ничего не делает для других чисел. –
Итак, как я могу сгенерировать в своем коде нечетные числа, как на картинке? Https: //rjlipton.files.wordpress.com/2012/12/compressed_tree_on_1_max_depth_10_max_nodes_100_percent-60.png – mandre96
Выполнение чего-то для нечетных чисел может быть началом ... –