Escreva um programa que acumula n valores da sequência de Fibonacci em uma pilha.

Passo 1

O enunciado pede um programa que armazene os primeiros n valores da sequência de Fibonacci em uma pilha. O conteúdo envolve a definição da sequência de Fibonacci (onde cada termo, a partir do terceiro, é a soma dos dois anteriores) e a implementação de uma pilha (stack) em C, usando um vetor e operações de push/pop.

Passo 2

Definimos a estrutura da pilha em C com um vetor de tamanho máximo e um índice top. A pilha será representada por:
– Um vetor data[MAX] para guardar os elementos;
– Um inteiro top que aponta para o índice do elemento no topo (inicialmente -1).

Passo 3

Implementamos as operações básicas da pilha:
– init(&s): inicializa top = -1;
– is_full(&s): retorna true se top == MAX–1;
– is_empty(&s): retorna true se top == –1;
– push(&s, val): incrementa top e insere val em data[top], tratando overflow;
– pop(&s): retorna data[top] e decrementa top, tratando underflow.

Passo 4

Para gerar a sequência de Fibonacci de forma iterativa usamos duas variáveis: a = 0 e b = 1. No loop de 0 a n–1 fazemos:
– Se i == 0, empurrar a (0) na pilha;
– Se i == 1, empurrar b (1) na pilha;
– Para i ≥ 2, calcular next = a + b, empurrar next e atualizar a = b e b = next.

Passo 5

No main():
– Lemos o valor de n do usuário;
– Inicializamos a pilha;
– Iteramos de i = 0 até n–1 aplicando a lógica acima para gerar e empilhar cada Fibonacci;
– Por fim, opcionalmente, imprimimos os elementos da pilha do topo para a base dando pop até ficar vazia.

Resposta

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
typedef struct {
int data[MAX];
int top;
} Stack;
void init(Stack *s) {
s->top = -1;
}
int is_full(Stack *s) {
return s->top == MAX - 1;
}
int is_empty(Stack *s) {
return s->top == -1;
}
void push(Stack *s, int val) {
if (is_full(s)) {
printf(“Erro: pilha cheia\n”);
exit(1);
}
s->data[++s->top] = val;
}
int pop(Stack *s) {
if (is_empty(s)) {
printf(“Erro: pilha vazia\n”);
exit(1);
}
return s->data[s->top–];
}
int main() {
int n;
Stack s;
init(&s);
printf("Digite o valor de n: ");
scanf("%d", &n);

int a = 0, b = 1;
for (int i = 0; i < n; i++) {
    if (i == 0) {
        push(&s, a);
    } else if (i == 1) {
        push(&s, b);
    } else {
        int next = a + b;
        push(&s, next);
        a = b;
        b = next;
    }
}

printf("Elementos da pilha (do topo para a base):\n");
while (!is_empty(&s)) {
    printf("%d\n", pop(&s));
}

return 0;
}

Exercícios relacionados