Javascript: Задача Иосифа Флавия или Считалка Джозефуса

Описание есть в Вики, а здесь - несложная реализация на Javascript, заодно показывающая пример на двусвязный список. В полях ввода задаются целые положительные числа.

Необязательно интерпретировать задачу так же "кровожадно", как в исходной постановке. Можно считать, что мы просто имеем считалку из k слов, применяемую к кругу из n людей, причём, считать новую цепочку мы начинаем с элемента, следующего за только что удалённым. В дворовых считалках часто начинают считать "с себя" (того, кто считает), но это делает счёт предсказуемей :)

Нумеруем с единицы. Если удалять, например, каждого 8888-го из 99999, скрипт может работать довольно долго, но вычисляется-то он на вашей стороне, а не сервера, так что пусть :) Чтобы увидеть всю цепочку номеров удаляемых элементов, поставьте в значение 1 переменную debug.

Исходник (без обрамления HTML):

<script type="text/javascript">
var debug = 0; //1 - увидеть всю цепочку
var debugList = '';

var JosephusFlaviusProblem = {
 init: function (n) {
  this.head = {};
  var current = this.head;
  for (var i = 0; i < n-1; i++) { //список на js :)
   current.label = i+1;
   current.next = { prev: current };
   current = current.next;
  }
  current.label = n;
  current.next = this.head;
  this.head.prev = current;
  return this;
 },
 delete: function (k) { //извлечение из списка на js :)
  var current = this.head;
  while (current.next !== current) {
   for (var i = 0; i < k-1; i++) {
    current = current.next;
   }
   current.prev.next = current.next;
   current.next.prev = current.prev;
   if (debug) debugList += current.label+' ';
   current = current.next;
  }
  return current.label;
 },
 get: function (val) {
  var s = ''+val;
  s = s.replace (/\s+/g, " ").replace(/(^\s*)|(\s*)$/g, '');
  if (s=='') return NaN;
  var n = Math.abs(parseInt(s));
  if (isNaN(n)) return NaN;
  return n;
 },
 run: function () {
  var n=this.get(document.jform.n.value); document.jform.n.value = n;
  var k=this.get(document.jform.k.value); document.jform.k.value=k
  var jres='';
  if (isNaN(n) || isNaN(k) || (n<1) || (k<1)) 
   jres = 'Введите 2 целых положительных числа'; 
  else {
   debugList = '';
   jres= 'Останется номер: '+this.init(n).delete(k)+
         (debug ? "\n"+'<br>'+debugList : '');
  /*
   n - количество элементов
   k - убирается каждый k-й по кругу
  */
  }
  document.getElementById('jres').innerHTML = jres;
 }
}
</script>
<noscript><div align="center">Извините, для работы приложения нужен включённый Javascript</div></noscript>

<div align="center">
 <form name="jform" method="post" onsubmit="return false;">
  всего: 
  <input type="text" name="n" size="6" maxlength="5" value="" />
  убрать каждого: 
  <input type="text" name="k" size="5" maxlength="4" value="" />
  <input type="button" name="action" value="OK" 
   onclick="JosephusFlaviusProblem.run();return false;" />
 <div id = "jres"></div>
</div>

доносчик внимательно считает кнуты, стремясь не пропустить первый :)

25.04.2016, 12:23 [6687 просмотров]