OEIS A002845: Количество различных значений, принятых 2 ^ 2 ^ & hellip; ^ 2 (с n 2 и круглыми скобками, вставленными всеми возможными способами)
Как будто вы пытаетесь получить доступ к объекту, который является null. Рассмотрим ниже пример:
TypeA objA;
. В это время вы только что объявили этот объект, но не инициализировали или не инициализировали. И всякий раз, когда вы пытаетесь получить доступ к каким-либо свойствам или методам в нем, он будет генерировать NullPointerException, что имеет смысл.
См. Также этот пример:
String a = null;
System.out.println(a.toString()); // NullPointerException will be thrown
2 ответа
Просто представьте числа в повторной базе 2: a Num имеет (возможно, пустой) список различных дочерних элементов x1,...,xp типа Num, так что Num([x1,...,xp]) == 2^x1 + ... + 2^xp.
Это определяет уникальный способ записи неотрицательного целого числа; не забудьте отсортировать показатели так, чтобы сравнение имело смысл. Равенства:
-
2^x + 2^x == 2^(x+1) == Num([x+1]) -
2^x + 2^y == Num([x,y])приx != y -
(2^2^x)^2^y == 2^2^(x+y) == Num([Num([x+y])])
наряду с ассоциативностью / Коммутативность сложения позволяет добавлять произвольные числа и вычислять x^y для чисел вида 2 ^ 2 ^ k; этот класс чисел содержит 2 (с k = 0) и закрыт согласно ^, так что это гарантирует, что все числа, которыми мы должны манипулировать, имеют такую форму.
Кроме того, определенные выше равенства никогда не увеличивают количество узлов в дереве, поэтому все Num имеют размер O(n).
Таким образом, временная сложность фактически равна O(C * n^k), которая квазилинейна в C (C - это (n-1) -ое каталонское число).
Один из подходов, который намного лучше, чем грубая сила (но, по общему признанию, все еще дорогой), заключается в использовании понятия «стандартная форма» в первой связанной статье. Получив n, сгенерируйте каждую стандартную форму степени n, оцените ее и сохраните все значения в наборе. В конце проверьте размер набора.
Грамматика для стандартной формы:
S -> (2 ^ P)
P -> (S * P)
P -> S
S -> 2
Вы начинаете с S, и в конце у вас должно быть n терминалов (т.е. 2 с).