返回首页 - Notes - 2015

约瑟夫环


JavaScript实现

/**
 * 节点结构
 */
var Person = function (data, next) {
    return {
        data: data,
        next: next
    };
};


/**
 * 创建循环链表
 */
var createPeople = function (n) {
    var p = new Person(1, null);
    var head = p;

    for (var i = 2; i <= n; ++i) {
        q = new Person(i, null);
        p.next = q;
        p = q;
    }

    p.next = head;

    return head;
};


/**
 * 执行杀人
 */
var killPerson = function (head, start, step, sum, want) {
    var p = head;

    // 先找到开始喊号的人
    while (p.data !== start) {
        p = p.next;
    }

    // 已经杀掉的人数
    var n = 0;
    // 已经杀掉的人
    var killed = [];
    // 幸存者
    var survivals = [];

    // 确保圈里还有多于1人
    while (p.next !== p) {
        for (var i = 1; i <= step; ++i) {
            t = p;
            p = p.next;
        }
        if ((sum - n) > want) {  // 如果剩余的人数大于想要的人数,那就继续杀
            killed.push(p.data);
        } else {
            survivals.push(p.data);
        }
        ++n;
        t.next = p.next;
        p = p.next;
    }

    survivals.push(p.data);

    // 输出结果
    console.log('Killed: ' + killed);
    console.log('The survival' + (want > 1 ? 's' : '' ) +': ' + survivals);
};


var sum = 10;
// 10人围成一圈
var head = createPeople(sum);
// 从5号开始,每次往后杀第3人,并传递总数和要求最后剩下的人数
killPerson(head, 5, 3, sum, 2);

CoffeeScript

class Person
  constructor: (@data, @next) ->
    data: @data
    next: @next


createPeople = (n) ->
  head = p = new Person 1, null
  for i in [2..n]
    q = new Person i, null
    [p.next, p] = [q, q]
  p.next = head


killPerson = (head, start, step, sum, want) ->
  p = head
  p = p.next while p.data != start

  [n, killed, survivals] = [0, [], []]

  while p.next != p
    [t, p] = [p, p.next] for i in [1..step]
    if (sum - n) > want
      killed.push p.data
    else
      survivals.push p.data
    ++n
    [t.next, p] = [p.next, p.next]

  survivals.push p.data

  console.log "Killed: #{killed}"
  if want > 1
    console.log "The survivals: #{survivals}"
  else
    console.log "The survival: #{survivals}"


sum = 10
head = createPeople sum
killPerson head, 5, 3, sum, 2

date:2015-12-03