Задача Иосифа Флавия

[Vallez]

Задача Иосифа Флавия

Сущ-т легенда что Иосиф Флавий выжил и стал известным благодоря математической одаренности. В ходе Иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство в плену, воины решили выстроится в круг и последовательно убивать каждого 3го из живых до тех пор пока е останется ни одного человека. Однако Иосиф на ряду с 1 из единомышленников счел подобный конец бессмысленным - он быстро вычеслил места в круге на которые себя и товарища. И лишь поэтому остался жив.
Определить номера уцелевших.

//каждого k убиваем
$k = 3;
//всего n войнов
$n = 8;
    //исключаем каждого $k-го
    //создаем 41 иудейского война
    $warriors = range(1,$n);
    $i=0;
    $offset=0;
  while(count($warriors)>=$k) {
       
        if($i%$k==0) { //убиваем этого
            $offset = ($offset+2) % count($warriors);
            array_splice($warriors, $offset, 1);
       }
	$i++;
   }

    echo implode(',',$warriors);
if(count($warriors) > 1) {echo " wars remained are live";}else{echo "warrior remained it is live";}

при

//каждого k убиваем
$k = 3;
//всего n войнов
$n = 9;

проблем нету

при

//каждого k убиваем
$k = 7;
//всего n войнов
$n = 8;

1,2,4,5,7,8 wars remained are live


как решить проблему ?
может я гдето в алгоритме ошибся уже 3 часа мучаюсь

 

[x-yuri]

убери $offset и сделай два цикла

 

[Vallez]

неа

1,2,4,5,7,8 wars remained are live

-~{}~ 23.01.09 02:38:

извини конечно но можешь расписать так как я нефига не сплю 4 день и мозг уже не варит

 

[x-yuri]

и что такое проблем нету?

-~{}~ 23.01.09 01:41:

внешний цикл - по этапам (убивание каждого 3-го), внутренний - убивает воинов для текущего этапа. Не надо это все в один цикл пихать

 

[Vallez]

а теперь коронный момент который я сам заметил токо на зачёте :-D
//каждого k убиваем
$k = 7;
//всего n войнов
$n = 8;
1,2,4,5,7,8 wars remained are live

а мы видь убиваем каждого 7...

-~{}~ 23.01.09 02:43:

извини туплю......

-~{}~ 23.01.09 02:44:

а можно в коде а то всё финиш я уже соображать не могу... а в 12 сдавать....

 

[x-yuri]

я на самом деле тоже туплю
зачем тебе два счетчика? и зачем ты проверяешь каждого воина? убивай в цикле воина и переходи к следующему, которого надо убить
короче "мочи всех по очереди" ;-)

 

[Vallez]

тоже пробовал делать но тогда не фига не катит
12_45_78
_2_45_78
_2_4__78
___4__78
___4__7_

-~{}~ 23.01.09 02:57:

это если шаг 3 брать
p.s:так норм пашет

 

[x-yuri]

тоже пробовал делать но тогда не фига не катит

покажи код для одного счетчика и инкремента его на $k

-~{}~ 23.01.09 07:00:

//создаем 41 иудейского война

улыбнуло)

 

[Nicholas]

Забавная задача, напомнила офигенный фильм грузино-французского производства: Тринадцать.

Мое решение (код написан минут за пятнадцать, поэтому просьба строго не пинать =):

$n      = 3;  // Шаг
$count  = 41; // Количество
$killer = 1;  
$warriors = range(1, $count);

echo implode('|', $warriors) . "\n";

// Начинаем умирать =)
while (true)
{
  $live = 0; // Количество живых (подсчитывается после полного прохода круга)
  for ($i = 0; $i < $count; ++$i)
  {
    // Этот воин уже мертв =)
    if ($warriors[$i] == '*')
    {
      continue;
    }
    
    $live++;
    if ($killer++ % $n == 0)
    {
      $warriors[$i] = '*';
    }
  }
  
  // Если живых осталось меньше двух - задача решена.
  if ($live < 3)
  {
    break;
  }

  echo implode('|', $warriors) . "\n";
}

Имеем следующий выдод:

1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29|30|31|32|33|34|35|36|37|38|39|40|41
1|2|*|4|5|*|7|8|*|10|11|*|13|14|*|16|17|*|19|20|*|22|23|*|25|26|*|28|29|*|31|32|*|34|35|*|37|38|*|40|41
*|2|*|4|*|*|7|8|*|*|11|*|13|*|*|16|17|*|*|20|*|22|*|*|25|26|*|*|29|*|31|*|*|34|35|*|*|38|*|40|*
*|2|*|4|*|*|*|8|*|*|11|*|*|*|*|16|17|*|*|*|*|22|*|*|25|*|*|*|29|*|31|*|*|*|35|*|*|38|*|*|*
*|2|*|4|*|*|*|*|*|*|11|*|*|*|*|16|*|*|*|*|*|22|*|*|25|*|*|*|*|*|31|*|*|*|35|*|*|*|*|*|*
*|2|*|4|*|*|*|*|*|*|*|*|*|*|*|16|*|*|*|*|*|22|*|*|*|*|*|*|*|*|31|*|*|*|35|*|*|*|*|*|*
*|*|*|4|*|*|*|*|*|*|*|*|*|*|*|16|*|*|*|*|*|*|*|*|*|*|*|*|*|*|31|*|*|*|35|*|*|*|*|*|*
*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|16|*|*|*|*|*|*|*|*|*|*|*|*|*|*|31|*|*|*|*|*|*|*|*|*|*

Выживают 16 и 31 воины

 

[x-yuri]

$k = 3; 
$n = 41; 
$warriors = range(1,$n); 
$i=$k-1;
while( count($warriors) >= $k ) {
	array_splice( $warriors, $i, 1 );
	$i += $k-1;
	if( $i >= count($k) )
		$i = $i % count($warriors);
}
var_dump($warriors);