Conceitos Lista Encadeada

Conceitos Lista Encadeada

Uma lista encadeada é uma estrutura de dados do tipo container, ou seja, serve para armazenar elementos em uma certa ordem que oferece operações de acesso geral, tais como inserção, remoção e busca arbitrária. Uma das características mais importantes de uma lista encadeada é seu caráter dinâmico, que permite armazenar um número de elementos limitado apenas pela memória disponível.

Este tipo de estrutura consiste de uma sequência linear de nós dinamicamente alocados, que são encadeados através de ponteiros. Versões mais elaboradas de listas encadeadas utilizam nós com ponteiros para os nós sucessor e antecessor e outras fazem com que o último nó aponte para o primeiro.

Problema de Josephus

Na matemática um exemplo famoso de recorrência é atribuído a Flavius Josephus, um famoso historiador do primeiro século, que durante a guerra Judaica, se encontrava entre um bando de 41 judeus rebeldes encurralados pelos romanos em uma caverna.

Sem chance de fuga o grupo decide pela morte ao invés do aprisionamento, os rebeldes formam um circulo e começariam a partir de certo ponto pular duas pessoas e a matar a terceira pessoa numa direção fixa, a eliminação procede em torno do circulo que irá se tornando menor conforme as pessoas mortas são removidas, até não restar alguém vivo.

Conta à lenda que graça ao talento matemático de Josephus o mesmo conseguiu escapar desta tolice quanto ao suicídio ao encontrar o local no circulo inicial em que será o ultimo.

Determinada a tarefa, para buscar uma solução simples, podemos analisar a simulação grafica, com o seguinte circulo inicial: