Ajuda! Estruturas de dados. Alocação estática de memória. Listas,

[FabioArgenton]

DESAFIO

Várias áreas da ciência da computação usam domínios simples e abstratos para estudos analíticos e empíricos. Por exemplo, algumas das primeiras pesquisas de inteligência

artificial nas áreas de planejamento e robótica usavam o mundo dos blocos, no qual um braço de robô realizava tarefas envolvendo a manipulação de blocos.

Este desafio consiste em modelar um Mundo dos Blocos bem simples, que vai funcionar de acordo com certas regras e restrições.

O problema consiste em analisar uma série de comandos que instruem um braço de robô em como manipular os blocos que estão sobre uma mesa. Inicialmente, existem n blocos sobre a mesa (numerados de 0 a n-1), como mostra a figura a seguir.

------------------------------

|0| |1| |2| |3| |4| ....|n-1|

------------------------------

O problema começa com cada bloco na sua posição inicial sobre a mesa e, depois de uma série de comandos válidos, deve terminar em uma configuração final. Na figura a seguir é apresentado um exemplo para 5 blocos (n=5), sendo ( a ) a configuração inicial e ( b ) a configuração final.

----------------------------|2|---------|1|

|0|-|1|-|2|-|3|-|4|------|0|---------|4|-|5|

------------------------------------------------

----------( a )------------------( b )

Os comandos válidos para o braço de robô manipular os blocos são listados a seguir.

Usa-se a para indicar o bloco em movimento e b como bloco de referência.

*mover a acima b: move o bloco a para cima do bloco b retornando eventuais blocos

que já estiverem sobre a ou b para as suas posições originais.

*mover a topo b: coloca o bloco a no topo do monte onde está o bloco b retornando

eventuais blocos que já estiverem sobre a às suas posições originais.

*empilhar a acima b: coloca o bloco a juntamente com todos os blocos que estiverem

sobre ele em cima do bloco b, retornando eventuais blocos que já estiverem sobre b

as suas posições originais.

*empilhar a topo b: coloca o bloco a juntamente com todos os blocos que estiverem

sobre ele no topo do monte onde está o bloco b.

*encontrar maior: encontra o maior elemento da pilha mais alta e o devolve para a

posição inicial.

*sair: termina a execução.

Qualquer comando no qual a = b ou no qual a e b estejam na mesma pilha de blocos é um comando ilegal e deve ser ignorado, não alterando a configuração dos blocos.

Os arquivos de entrada e saída devem obedecer aos seguintes formatos:

*Arquivo de Entrada: o arquivo começa com um único número inteiro n na primeira linha representando o número de blocos do seu Mundo dos Blocos, sendo

0 < n < 25. Esse número de blocos será seguido por uma sequência de comandos, um por linha. O programa deve processar todos os comandos até encontrar o

comando sair. Assumir que todos os comandos estão no formado definido anteriormente, ou seja, não haverá erros de sintaxe nos comandos.

*Arquivo de Saída: a saída consiste da configuração final do seu Mundo dos Blocos. Em cada linha deve aparecer o número da posição original seguida de dois pontos

( : ). Se existir pelo menos um bloco naquela posição, os dois pontos devem ser seguidos pela lista de blocos que aparecem naquela pilha separados por um espaço

em branco. Deve existir uma linha no arquivo de saída para cada posição, ou seja, n linhas sendo n é o número inteiro na primeira linha do arquivo de entrada.

Para o exemplo mostrado na figura ( b ), os arquivos de entrada e saída são listados a seguir. Ressalta-se que diferentes arquivos de entrada podem levar a uma mesma

configuração final.

Entrada:-------------------Saída:

5----------------------------0: 0 2

mover 3 acima 0---------1:

move 2 topo 4-----------2:

empilhar 4 acima 0------3: 3 1

empilhar 1 topo 3--------4: 4

encontra maior

sair

Dúvidas:

1º Preciso analisar o problema proposto e definir as estruturas de dados estáticas para a sua resolução

2º Preciso definir as funções necessárias para a implementação dos quatro primeiros comandos definidos no desafio e o “sair”, utilizando as estruturas de dados com alocação estática de memória definida na Etapa 1.

3º Preciso fazer um programa que leia um arquivo de entrada, execute todos os comandos presentes nesse arquivo e gere um arquivo de saída, no formato definido anteriormente no desafio.

Obs: Sou iniciante em programação

[Felipe Amadio]

Dúvidas:

1º Preciso analisar o problema proposto e definir as estruturas de dados estáticas para a sua resolução

2º Preciso definir as funções necessárias para a implementação dos quatro primeiros comandos definidos no desafio e o “sair”, utilizando as estruturas de dados com alocação estática de memória definida na Etapa 1.

3º Preciso fazer um programa que leia um arquivo de entrada, execute todos os comandos presentes nesse arquivo e gere um arquivo de saída, no formato definido anteriormente no desafio.

Obs: Sou iniciante em programação

Cara, essas duvidas foi você realmente quem redigiu? Sendo iniciante em programação?

Enfim, você não pensou nada no problema? não definiu nada?

Po, aposto que muitos que vão ler este tópicos terão varias ideias, mas o principal é você tê-las! Não acho justo e nem acho que faça sentido você colocar um problema, não abordar nenhuma solução pra ele, e ficar esperando!

Eu tenho sim algumas ideias de como realizar isso, mas acho que quem tem que ter as ideias é voce!

Então, eu vou dar algumas ideias. Voce deve ter uma estrutura que represente cada posição, e vai retirando e adicionando elementos em cada estrutura, de acordo com os coomandos. Sugiro 2 coisas para voce usar como estruturas

-Vetores (na verdade, como serão N vetores, então pode ser uma matriz, inicialmente de 25 x 25 posições, já que 25 é o tamnaho maximo)

-Listas Encadeadas. Voce sabe o que são listas encadeadas? já ouviu falar? sabe como funciona? De uma procurada, são estruturas bem poderosas, que permitem uma manipulação muito mais "livre" do que vetores ou matrizes.

[FabioArgenton]

Primeiramente obrigado pela ajuda Felipe,

Cara por incrível que pareça este é um desafio para 3º semestre de TADS, segundo o cronograma de aulas estaremos vendo lista filas e pilhas lá pra 3º semana do semestre e na minha opinião teremos alguma noção pra realizar este desafio lá pra 10º semana do 3º semestre e acredite temos que entregar metade do desafio em março, postei apenas para ajudas e dicas, não espero que alguém resolva pra mim apenas me dê uma luz pra eu poder realizar este desafio já que temos pouco tempo para entregá-lo mais uma vez obrigado pelas dicas.

Se alguém tiver mais alguma dica galera postem ai toda ajuda será necessária Obrigado.

[FabioArgenton]

#include <stdio.h>
#include <stdlib.h>
#define TAM 25    //Definindo tamanho da Pilha

//Variáveis Globais:
            
int sentinela=0; //Apontador responsavel por todo o esquema
int stack[TAM];  //Vetor de 5 elementos

//Funções:
void push(int valor){             //Empilhar Se a pilha não estiver cheia
     if(sentinela>=TAM)           //Caso esteja cheia(SE Apontador>=vetor (esta acima de 4))
        printf("\nEsta Cheia");   //Mostra Pilha Cheia
     else                         //SENÃO
         {
           stack[sentinela]=valor;//Inserir o valor onte apontador aponta
           sentinela++;           //Apontador aponta pro próximo
         }
};

void pop(){                    //Desempilhar Se a pilha não estiver vazia
     if(sentinela==0)          //SE apontador for igual a 0(estiver na posição 0 do vetor)
        printf("\nEsta Vazia");//Mostra Pilha Vazia
     else                      //SENÃO   
        sentinela--;           //Apontador desce uma posição
};

int top(){                        //Mostrar o elemento do topo Se pilha não estiver Vazia
    if (sentinela==0)             //SE apontador for igual a 0(estiver na posição 0 do vetor)       
         printf("\nEsta Vazia");  //Mostra Pilha Vazia
    else                          //SENÃO
        return stack[sentinela-1];//Retorna Vetor de Apontador-1 (Vai retornar no printf do programa)
};

int empty(){                     //Mostra se a Pilha esta vazia 
    if(sentinela==0)             //SE apontador for igual a 0(estiver na posição 0 do vetor)
      printf("\nEsta Vazia");    //Pilha vazia
    else                         //SENÃO
      printf("\nNao esta Vazia");//Contem algum elemento dentro do vetor
};

int full(){                      //Mostra se a pilha esta cheia
    if(sentinela>=TAM)           //SE apontador>=tamanho do vetor(esta acima de 4)
      printf("\nEsta Cheia");    //Mostra Pilha cheia   
    else                         //SENÃO
      printf("\nNao esta Cheia");//Pilha não esta cheia - ainda há espaço   
};        

int main(int argc, char *argv[])
{
    push(5);              //Empilha 5
    push(8);              //Empilha 8 em cima do 5 
    printf("%d",top());   //Mostra o que esta no topo (8)
    pop();                //Desempilha o que esta no topo (tira 8)
    printf("\n%d",top()); //Mostra o que esta no topo (5)
    empty();              //Mostra se a Pilha esta vazia
    full();               //Mostra se a pilha esta cheia
    
//Resultado: 8,5 
//Não esta vazia
//Não esta cheia 

  system("PAUSE>>null");    
  return 0;
}