Ir ao conteúdo
  • Cadastre-se

C preciso resolver esse jogo da exclusão e n tenho ideia de como começar


Posts recomendados

PROGRAMAÇÃO EM C!!usando funções, constantes e vetores.

Hoje vamos jogar o jogo da exclusão, onde existem N (2 ≤ N ≤ 10000 ) é o número de participantes organizados em um círculo e M (1 ≤ M ≤ 1000) é o número de posições que serão puladas para eliminar o próximo jogador dado uma posição atual.

Seguindo um exemplo com N=5 participantes e M=2 posições de pulo. Seguindo o algoritmo de resolução o participante número 3 ganhará o jogo.

Dado uma lista circular com 5 participantes [1,2,3,4,5]. O primeiro participante a ser excluído do jogo será o número de posições M, logo:

Início: [1,2,3,4,5]
Passo1: [1,3,4,5]
Passo2: [1,3,5]
Passo3: [3,5]
Passo4: [3]
Fim.
Dado uma lista circular com 6 participantes [1,2,3,4,5,6] e M=3.

Início: [1,2,3,4,5,6]
Passo1: [1,2,4,5,6]
Passo2: [1,2,4,5]
Passo3: [1,4,5]
Passo4: [1,5]
Passo5: [1]
Fim.


Entrada
Um valor inteiro N e um valor inteiro M.
Saída
Quem foi o vencedor.

  • Confuso 1
  • Triste 1
Link para o post
Compartilhar em outros sites
10 horas atrás, iisraelalves disse:

Dado uma lista circular com 6 participantes [1,2,3,4,5,6] e M=3.

Início: [1,2,3,4,5,6]
Passo1: [1,2,4,5,6]
Passo2: [1,2,4,5]
Passo3: [1,4,5]
Passo4: [1,5]
Passo5: [1]

Isso está certo?

 

O passo a passo seria assim,

 

Início: [1,2,(3),4,5,6] -> três passos a partir do 1 tira o 3
Passo1: [1,2,4,5,(6)] -> três passos a partir do 4 tira o 6
Passo2: [1,2,4,5] -> aqui são três passos a partir de 5?
Passo3: [1,4,5] -> três passos a partir de 4?
Passo4: [1,5]
Passo5: [1]

 

No Passo2 porquê não começa a partir do número 1? Se é circular, após o Passo1 eliminar o 6 não devia começar no 1 que seria o próximo? Aí o 4 que seria tirado do Passo3 e não o 2.

 

 

  • Curtir 1
Link para o post
Compartilhar em outros sites

Teve uma discussão sobre isso nesse forum tempos atrás e eu postei duas soluções até, e em algum momento um programa completo, mas não me lembro dos links exceto esse abaixo. Dê uma olhada nessas funções, em C

 

 

Link para o post
Compartilhar em outros sites
10 horas atrás, JorgeGus disse:

Acho que o segundo exemplo está errado, pra mim seria:

Sim, como comentei acima o Passo3 deve estar errado. Mas o resultado final está certo, o 1 é o último.

 

O exemplo do @arfneto pode ser usado para resolver isso, esta parte:

 

Em 10/12/2019 às 23:24, arfneto disse:

pos = (pos + 1) % M; // conta so os vivos

 

Adaptei para,

pos = (pos + (M - 1)) % n;

 

Essas são as posições que serão "eliminadas" do vetor. M é a variável da posição que não será alterada no loop e n é a variável do número de participantes que será decrementada ( n -= 1). Pode ser usada uma função para mover os elementos do vetor (p.ex vetor[i] = vetor[i + 1]) e outra para imprimir.

 

Com 6 elementos e 3 posições, a saída do meu programa ficou assim,

 

1,2,3,4,5,6,
1,2,4,5,6,0,
1,2,4,5,0,0,
1,2,5,0,0,0,
1,5,0,0,0,0,
1,0,0,0,0,0,

 

Eu apenas movo a posição do elemento para o final e atribuo zero. Os zeros eu só mostrei para ficar mais claro o que eu fiz,

 

Com 5 elementos e 2 posições,

 

1,2,3,4,5,
1,3,4,5,0,
1,3,5,0,0,
3,5,0,0,0,
3,0,0,0,0,

 

Com 5 elementos e 3 posições,

1,2,3,4,5,
1,2,4,5,0,
2,4,5,0,0,
2,4,0,0,0,
4,0,0,0,0,

 

 

Link para o post
Compartilhar em outros sites

 

Em 03/03/2021 às 21:35, JorgeGus disse:

Acho que o segundo exemplo está errado

 

16 horas atrás, Midori disse:

Sim, como comentei acima o Passo3 deve estar errado

 

Pois é :D está errado.

 

o problema provavelmente era para ser como o clássico do Círculo de Josephus, mas a definição não tem a necessária formalidade. E acabou errada: é preciso qualificar se a contagem para o salto é ou não inclusiva em relação á posição inicial. 

 

Esse é o trecho importante:

 

Em 03/03/2021 às 06:39, iisraelalves disse:

onde existem N (2 ≤ N ≤ 10000 ) é o número de participantes organizados em um círculo e M (1 ≤ M ≤ 1000) é o número de posições que serão puladas para eliminar o próximo jogador dado uma posição atual


Se M pode ser 1 como está no enunciado é claro que a contagem não pode ser inclusiva, não começa pelo primeiro elemento. Se fosse assim para M = 1 e N = 10.000 o primeiro cara morre e o programa entra em loop. Para isso, como está por exemplo na definição da Wikipedia e nas descrições comuns desse problema, M deve ser maior que 1 e não inclui o soldado oroginal. No problema original, de séculos atrás, se acredita que M era de fato 2 e cada soldado mataria o soldado á sua direita, seguindo o círculo.

 

Só que aí vem o exemplo onde N = 5 e M = 2. E relembrando...
 

Seguindo um exemplo com N=5 participantes e M=2 posições de pulo.
Seguindo o algoritmo de resolução o participante número 3 ganhará o jogo.

Dado uma lista circular com 5 participantes [1,2,3,4,5]. O primeiro participante a ser excluído
do jogo será o número de posições M, logo:

Início: [1,2,3,4,5]
Passo1: [1,3,4,5]

 

Em geral para M = k se pulam (k-1) elementos na direção desejada. No caso geral se pode seguir claro no sentido anti-horário, já que é o problema do Círculo de Josephus ...  E para M = 1 não há muito sentido, já que seria o efeito dominó :) com os caras caindo mortos um a um e não daria para associar com o lance dos soldados em círculo. Uma animação do possível problema original para M = 2

 

 

 

Link para o post
Compartilhar em outros sites

@lenny44 não entendi. 

 

De todo modo a diferença disso para o problema tradicional é que no problema original é um soldado que mata o próximo e, a menos de um zumbi, o próximo soldado vivo :) é que mataria o soldado a M posições no sentido desejado. 
Nesses problemas "modernos" parece haver um agente assassino que mata os caras de M em M.

 

Link para o post
Compartilhar em outros sites

@iisraelalves Enunciado, os exemplos, a narrativa [...], os passos são coerentes e quando isso importa nenhum argumento corrobora o contrário, até momento. E você fez tentativa sincera solução? Se duvidar compartilhe para mais opinião.  

Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisa ser um usuário para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...

minicurso-montagem-popup.jpg

MINICURSO GRÁTIS!

Como ganhar dinheiro montando computadores!

CLIQUE AQUI E INSCREVA-SE AGORA MESMO!