Escreva um programa que acumula
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).
– 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.
– 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.
– 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.
– 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>
#include <stdlib.h>
#define MAX 1000
typedef struct {
int data[MAX];
int top;
} Stack;
int data[MAX];
int top;
} Stack;
void init(Stack *s) {
s->top = -1;
}
s->top = -1;
}
int is_full(Stack *s) {
return s->top == MAX - 1;
}
return s->top == MAX - 1;
}
int is_empty(Stack *s) {
return s->top == -1;
}
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;
}
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–];
}
if (is_empty(s)) {
printf(“Erro: pilha vazia\n”);
exit(1);
}
return s->data[s->top–];
}
int main() {
int n;
Stack s;
init(&s);
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;
}