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

[iisraelalves]

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.

[Midori]

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.

 

 

[lenny44]

@Midori sim esses passos estão certo, ai teria quer percorrer todo o vetor eliminando a cada 3,porém a contagem continua mesmo depois que o numero é eliminado

[arfneto]

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

 

 

[JorgeGus]

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

123456

12456

1245

125

15

1

[Midori]

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,

 

 

[arfneto]

 

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 é  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

 

 

 

[lenny44]

@arfneto ele nao recomeça a contagem,ele apenas continua a contagem logo depois da eliminaçao

[arfneto]

@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.

 

[Ansi C]

@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.