Jump to content
Sign in to follow this  
JoaoSantos95

Problema de Josephus - CPAS Junior'07 e PPUP'04

Recommended Posts

JoaoSantos95

Implemente um programa que resolva o problema de Josephus:

Este problema foi assim denominado em homenagem a um historiador do séc. I,

Flavius Josephus, que sobreviveu à guerra entre Romanos e Judeus graças aos seus

talentos matemáticos. A Lenda conta que haviam 41 judeus encurralados pelos

Romanos. Como os seus companheiros preferiam o suicido à rendição, decidiram

formar um círculo e matar sempre a terceira pessoa até não haver mais ninguém

vivo. Josephus, como não estava muito excitado com a ideia de se suicidar,

calculou a posição adequada para sobreviver a este “ciclo vicioso”.

O seu programa deve ler o número N de pessoas no círculo e quantas

pessoas avançará para escolher o próximo a morrer. O resultado será o único

sobrevivente.

Exemplo 1:

Neste exemplo, são considerados 5 Judeus e um incremento de 3 pessoas para escolher o próximo a

morrer.

1(1)          1(3) -> X

2(2)          2          2(1)        2(1)(3)      -> X

3(3)      -> X

4              4(1)      4(2)        4(2)          -> SOBREVIVENTE

5              5(2)      5(3)  -> X

Entrada:

5

3

Saída:

4

Este problema pertence ao enunciado do CPAS Junior'07 mas também pode ser um problema em que apenas muda o enunciado na edição de 2004 do concurso PPUP.

Até agora fiz o seguinte código:

program ex9cpasjunior2007;
var num,n,i,j,t,w,q : integer;
    Vec : array [1..100] of integer;

begin
  ReadLn(num);
  Readln(n);
  
  for i:=1 to num do
   begin
    Vec := i;
   end;
   
  w := num;
   
     for i := 1 to num do
      begin
      
        While (q <= n) do
         begin
         
       if (Vec[i] <> 0)
       then
        begin
         t := (w mod n) + 1;
         q := q + 1;
        end
        
         end;

      w := w - 1;
      Vec[t] := 0;
         
      end;

    for i := 1 to num do
     begin
    if (Vec[i] <> 0)
    then WriteLn(Vec);
     end;

end.

A minha dúvida está em como "eliminar" uma pessoa

EDIT: if (Vec <> 0), no lugar do Vec lê-se Vec (i]

Share this post


Link to post
Share on other sites
carlosf

um modo simples de fazeres isso é, usas um vector (como já tens), depois numeras v[0]=1, v[1]=2 que é o numero do judeu, quando morre passa a 0.. depois é só matares todos menos 1, ou seja tens de repetir o ciclo "que mata" num_judeus - 1 vezes (nessa altura só deve ser 1 judeu <> 0, que é o sobrevivente)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.