Xpoint
   [напомнить пароль]

2^2^...^2

Метки: [без меток]
2008-12-22 15:47:44 [обр] nikov[досье]
Такая вроде бы несложная задача. Надо написать алгоритм, который принимает натуральное число n, и вычисляет, сколько различных значений может принимать выражение 2^2^...^2 (n двоек, знак ^ означает возведение в степень) при всевозможных расстановках скобок. Например, при n=3 возможны два варианта расстановки скобок:(2^2)^2 и 2^(2^2), но они дают одинаковое значение, поэтому результатом алгоритма будет 1.
Решение методом грубой силы (посчитать результаты и сравнить), естественно, умирает уже при небольших n. Надо искать какую-то закономерность. Вроде бы анализ упрощается, если выражение дважды прологарифмировать по основанию 2, но требуемый алгоритм мне написать так и не удалось.
спустя 5 часов [обр] Иванов Михаил aka Ivanych(0/70)[досье]
Скобки могут быть вложенными?
спустя 6 минут [обр] nikov[досье]
Иванов Михаил aka Ivanych[досье] Да
спустя 1 день 18 часов [обр] Rumata(0/3)[досье]

Попробуйте рассмотреть выражение как бинарное дерево, в котором операции являются узлами, а числа - листьями.
Например, для n = 3 деревья могли бы выглядеть следующим образом:

2 ^ ( 2 ^ 2 )

  ^
 / \ 
2   ^
   / \ 
  2   2


( 2 ^ 2 ) ^ 2

    ^
   / \ 
  ^   2
 / \ 
2   2

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

спустя 17 часов [обр] Иванов Михаил aka Ivanych(0/70)[досье]
Rumata[досье]
Это вы изложили ту-же задачу, вид сбоку.
Powered by POEM™ Engine Copyright © 2002-2005