PROBLEMA DE JOSEPHUS

BREVIÁRIO ACADÊMICO #2

Trago um algoritmo bastante simples feito na Linguagem de Programação C, que soluciona um problema proposto pelo matemático Flavius Josephus em meados do ano 64. De acordo com lenda, um grupo de rebeldes, dentre eles Josephus, foram encurralados em uma caverna pelo exército inimigo. Preferindo o suicídio à captura, os rebeldes decidiram formar um círculo em que o primeiro deveria matar o soldado diretamente ao seu lado até sobrar apenas um, que sozinho, tiraria a própria vida. Josephus era o único que não queria morrer, e era impossível convencer os demais a se entregar. Então a única saída seria descobrir qual a posição do soldado que iria sobreviver. A solução pode ser obtida resolvendo o problema manualmente, simulando as mortes uma por uma, mas se o número de soldados for muito grande então a contagem fica inviável. Para encontrar tal solução com um número arbitrário de soldados basta conhecer alguns conceitos de potenciação, recorrências e indução finita.

A solução é bastante conhecida e está detalhada em diversos artigos e matérias na internet. O algoritmo a seguir trás todas as soluções de 1 até n, que representa o número de soldados que você escolher. Dessa forma, é possível notar o padrão e visualizar melhor a solução.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){	
	int n, i, j, m[2][10000];
	printf("n = ");
	scanf("%i", &n);
	for(i = 2; i <= n; i++){
		m[0][i] = i;
		for(i = 2; i <= n; i++)
			for(j = 0; j < i; j++){	
				if(pow(2,j) <= i)
					m[1][i] = (2*(i - pow(2,j)) + 1);
			}
		printf("\nRESPOSTA: %i\n\n", m[1][n]);

		for(i = 2; i <= n; i++){
			printf("%i\t", i);
			printf("%i\n", m[1][i]);
		}
	}
	getch();
}

Inicialmente é definido n como o número de soldados, em seguida é calculado a maior potência de base 2 menor ou igual a número de soldados, chamaremos de J.

Ao conhecer J , basta fazer, 2(n – J) + 1.

MÚSICA DA SEMANA #332

ESMERO CONTO #5

Vou começar a registrar a melhor música que conheci durante a semana, seleciono a “Música da Semana” desde 2015 e sempre as sextas-feiras. A música dessa semana é Lady Black da banda britânica Uriah Heep.

Música: Lady in Black
Artista: Uriah Heep
Álbum: Salisbury
Data de Lançamento: 1971

Dama de Preto


Ela veio a mim uma certa manhã
Uma solitária manhã de domingo
Seu longo cabelo balançava ao suave toque do vento de inverno
Eu não sei como ela me encontrou
Porque na escuridão eu andava
E a destruição estava ao meu redor
De uma batalha da qual eu não poderia vencer


Ela perguntou o nome dos meus inimigos
E eu disse que necessitava de alguns homens
Para lutar e matar seus irmãos
Sem pensar sobre amor ou Deus
Implorei para que me desse alguns cavalos
Para que pudesse pisotear meus inimigos
Tamanha era minha vontade
De devorar esse desperdício de vida


Mas ela não pensava em guerras que
Reduziam homens à animais
Tão fácil de serem iniciadas
E impossíveis de terem um fim
E ela, mãe de todos os homens
Que me aconselhou tão sabiamente, então
Temi andar novamente sozinho
E perguntei se ela ficaria


Ó dama, estenda-me a tua mão abertamente
E deixe-me descansar ao teu lado
Tenha fé e acredite na paz, disse ela
E preencheu meu coração com vida


Não há força nos números
Não cometa erros
Mas quando precisar de mim
Fique tranquilo, não estarei longe


Após suas palavras, ela deu-me as costas
E incapaz de dizer qualquer coisa
Permaneci ali e observei até que vi
Seu manto negro desaparecer


Meu trabalho agora nem por isso é mais fácil
Mas agora sei que não estou sozinho
Meu coração se renova
A cada lembrança que tenho daquele dia


E se um dia ela vir até você
Absorve sabiamente todas suas palavras
Faça da coragem dela a sua recompensa
E diga “olá” por mim!

UM VOO PARA O DESCONHECIDO

DUALIDADE CRÔNICA #3

Medo, insegurança, borboletas no estômago. Sonhar é perigoso e é preciso saber se o desejo é genuíno (é possível ?).
A vida nos convida a experienciar, provar além do doce e salgado. As vezes o chocolate quente nos decepciona e as coisas parecem não fazer nenhum sentido. Espero que eu possa sentir a liberdade que está em mim, envolto em chamas depois que renasci.

Marvineo

O POUSO DOS PASSARINHOS

HINOS DE AMBIVALÊNCIA #2

O Pouso dos Passarinhos

Haste torre,
onde pousa os passarinhos
Não sei o que faço
Tabuleiro desalmado
Há meses que não chove
Os carniceiros nem se esforçam
Eu me destruo involuntariamente.

Haste torre,
onde canta os passarinhos
O canto me atordoa
Busco um lugar mais claro
Carrego os pesos mortos,
que em outrora já foram brutos
e difíceis de domar.

Haste torre,
onde comem os passarinhos
Sinto um cheiro podre
Perdi meu cavalo,
perdi para um jogo sem inimigos
Sem estratégias e sem amigos
Já nasci condenado.

Haste torre,
onde voam os passarinhos
Derrubei a torre
Agora grito para eles
Um grito definitivo
Eles fogem, pra longe
Não vão mais voltar.

Haste torre,
onde pousa os passarinhos
Mas eles sempre voltam
Trazem consigo o verão,
Que já vinha em jejum
Esse ano vai ser difícil.
Acho que não vou conseguir.

Lucas Rodrigues

RESFRIADO

DUALIDADE CRÔNICA #2

Resfriado

Estou sempre de sobreaviso
Avisa quando a chuva passar
Que talvez eu vá te ver

Quer saber ?
Eu vou mesmo assim…
Ou melhor
Deixa pra lá
Talvez a travessia ou a chuva
Me lembrem que não vale a pena ficar resfriado por você.

Ando sendo permeável
Permeando por outras realidades
Na tentativa de encontrar conforto em um riso simples, isso ajuda às vezes.

Mas quando baixa a energia
Emerge uma oportunidade.
É hora de acolher as fragilidades, e perceber nesse movimento quando a felicidade irá chegar.

Descobrindo então que não existe peça da parte que falta.

Marques Vinícius

VISÃO DE TÚNEL

DUALIDADE CRÔNICA #1

Visão de túnel

Antes contemplava somente a luz do sol
Com a sua beleza que ofusca olhares
e desconhecia da existência da escuridão
Antes haviam lampejos
Outrora, o nada, dando espaço para o vazio
Antes não conhecia essa tal chama
Tampouco não sabia manejá-la
Ela causava medo, ao mesmo tempo aquecia
Antes não conseguia bipedestar
Mas preferi fazer as pazes com o antes
E no aqui e agora o horizonte
Já consigo vislumbrar
E de pé, saltar
As rotas sempre estiveram ali
Diante de mim
Incontáveis,
Infinitas possibilidades
Que a escuridão não permitia enxergar
E agora? O que fazer com a manifestação da vida ?
O caminho irei trilhar
Meu próprio alimento buscar
Com a chama acesa a me guiar.
Num salto evolutivo
Na corda da vida me equilibro
E assim sobrevivo.

Marques Vinícius

UNIDADES DE MEDIDA

ESMERO CONTO #4

Conversando com meu avô, percebi que com o passar do tempo criamos nossas próprias medidas, definições e classificações. Sem estudos e influências dos meios de comunicação, ele espera as chuvas com trovões de janeiro que ainda não veio.

Esse tipo de conhecimento obtido diretamente da natureza é cada vez mais raro nos dias atuais, pelo fato que existe todos os tipos de informações similares e com mais detalhes. Porém, quando esse conhecimento se concretiza, imagino eu, que a sensação de satisfação é parecida com a de uma grande descoberta científica que também só imagino.

Todos nós seguimos unidades de medidas generalizadas, impostas com um objetivo de uma maior organização e comunicação. Ao comprar um litro de leite normalmente os últimos mililitros azeda, um pão sempre endurece dentre o saco, sempre sobra café frio na garrafa. Isso tudo não ocorre quando você cria suas próprias medidas, que como mencionado, tudo ficará natural ao passar do tempo. Suas ações e atos serão moldados aos seus gostos e tudo acontecerá sem que perceba.

Dia 21 de dezembro iniciou-se o verão, que apesar do atual calor, para ele só iniciará após a última chuva desse mês. Adiantando que para ele o verão vai até as chuvas de março, que por aqui beira os últimos dias, mais de uma semana depois do final “oficial”.

Essa conversa me fez refletir sobre tais unidades de medidas relacionado com a idade, eu com vinte anos, me adaptando para não desperdiçar pão e leite e ele com quase cem anos, transladando em uma semana  a época do verão e nem aí para as explicações astronômicas comprovadas.