C ++ Stack Fibinacci Hw Разъяснение проблемы - PullRequest
Новая
       32

C ++ Stack Fibinacci Hw Разъяснение проблемы

0 голосов
/ 16 февраля 2011

Привет, ребята. Мне нужна помощь в понимании моего назначения. Я начинаю с C ++ и не очень много знаю. Я знаю основы стека и последовательности Фибоначчи. Однако я не совсем понимаю проблему, с которой я столкнулся, и мне нужен не код для решения проблемы, а помощь в разъяснении некоторых шагов. Вот как это выглядит:

"Завершив этот проект, вы познакомитесь с использованием рекурсии и созданием ADT в C ++.

Создайте ADT целого стека (вы можете изменить ADS IntStack, предоставленный вам в примечаниях к лекции) так, чтобы он имел максимальную емкость не менее 256 элементов. Также добавьте все, что нужно, чтобы оно распечатывало свое содержимое (слева направо, с верхом стека справа), если оно печатается в o ++ Cstream - например, cout). Этот стек должен быть спроектирован таким образом, чтобы он содержал только значащие значения больше нуля. Значения, меньшие или равные нулю, должны быть напечатаны как '?'.

Напишите рекурсивную реализацию последовательности Фибоначчи, обсуждаемой в классе. Также - создайте экземпляр вашего ADT стека, который сохраняется между вызовами (это не может быть локальная переменная), и на каждом шаге вставляйте в него бессмысленное значение до тех пор, пока значение на этом этапе не будет определено, а затем вытолкните его и нажмите определенное значение и напечатайте весь стек перед возвратом.

Ваша программа должна запросить определение позиции N в последовательности Фибоначчи, а затем вывести результат вызова функции. Пример вывода (включая вывод вашей рекурсивной функции) следующий:

Введите положение в последовательности Фибоначчи, чтобы определить: 5 

?-?-?-1
?-?-?-1
?-?-2
?-?-1
?-3
?-?-1
?-?-1
?-2
5

Fibonacci(5) = 5

Что именно здесь выводится? Распечатывает ли стопку, когда вычисляет 5-ю позицию? Также есть идеи о том, как реализовать Фибоначчи в стек в C ++? Должны ли эти значения храниться в массиве, списке или это не имеет значения? Я нуб, поэтому любая помощь будет высоко ценится. Спасибо

Ответы [ 3 ]

1 голос
/ 16 февраля 2011

Да, это вычисление 5-го числа Фибоначчи (которое оказывается 5, это немного сбивает с толку), но посмотрите на то, что вы вычисляете, когда вызываете Фибоначчи (5), предполагая следующий код для Фибоначчи: 

int fibonacci(int n) {
    if (n <= 1) return n;
    else if (n == 2) return 1;
    else return fibonacci(n-1) + fibonacci(n-2);
}

вот вызовы функций для вычисления Фибоначчи (5): 

f(5)
 -> f(4)
     -> f(3)
         -> f(2)
         -> f(1)
     -> f(2)
 ->f(3)
    -> f(2)
    -> f(1)

Если вы посмотрите на это как на двоичное дерево, вывод, который они вам дали, был обход дерева после заказа, с количеством? глубина этого стека, а число - значение этого узла.

Так что просто делайте то, что делает функция, и каждый раз, когда вы видите return, пишите то, что вы возвращаете (с символом? Перед ним):

  • Первая функция, которая возвращает это первая f (2) на глубине 4: print? -? -? - 1
  • Второе возвращение - это f (1) под ним: print? -? -? - 1
  • Третьим возвращением является родительский элемент для f (2) и f (1), который имеет глубину 3 и значение f (2) + f (1) = 2: print? -? - 2
  • И так до тех пор, пока вы не вернете f (5) на глубину 0 и значение 5
0 голосов
/ 16 февраля 2011

Я оставляю вам печать стека и решаю запутанную часть использования стека для хранения маркера («не значащего» числа) и результата. Вот частичный псевдокод: 

procedure fib(n)
    push a marker (say a zero) to a global stack
    if n is 1 or 2 then
        result = you_know_what
    else
        calculate fib(n-1)
        pop the stack ==> fib_n_minus_1
        calculate fib(n-2)
        pop the stack ==> fib_n_minus_2
        result = fib_n_minus_1 + fib_n_minus_2
    endif

    pop the marker off the stack and discard
    push the result into the stack
    print the stack
end fib

Здесь следует отметить, что fib () не возвращает значение. Вместо этого он помещает возвращаемое значение в глобальный стек.

0 голосов
/ 16 февраля 2011

Разделите всю свою проблему на более мелкие части, которые можно решить / реализовать самостоятельно.В этом случае есть две основные части:

  1. Stack - реализация стандартного класса стека в соответствии с деталями, приведенными в вопросе.Это может помочь перечислить их все в точечной форме.
  2. Фибоначчи - Используйте класс стека для рекурсивной генерации ряда Фибоначчи.Стек - это механизм хранения для этого упражнения.

Пример вывода ?-?-?-1 можно понимать как следующие операции стека: 

push 0
push 0
push 0
push 1
print
...