Circular LinkList Compatriot Game в Javascript - PullRequest
Новая
       31

Circular LinkList Compatriot Game в Javascript

0 голосов
/ 04 июля 2018

Я нашел этот вопрос в «Структуре данных и алгоритме О'Рейли в Javascript». Согласно легенде, еврейский историк первого века Флавий Иосиф Флавий был о быть захваченным римскими солдатами вместе с группой из 40 соотечественников во время Еврейско-римская война. Еврейские солдаты решили, что они предпочитают самоубийство захватили и разработали план их гибели. Они должны были сформировать круг и убить каждый третий солдат, пока они все не были мертвы. Иосиф и еще один решили, что они не хотел никакой части этого и быстро рассчитал, где они должны были разместить себя так что они будут последними выжившими. Напишите программу, которая позволяет разместить люди в кругу и указать, что каждый человек будет убит. Программа следует определить количество последних двух человек, оставшихся в кругу. Используйте циркулярно связанный список для решения проблемы. "

это мое решение 

function Node(element) {
    this.element = element;
    this.next = null;
}

function LList() {
    this.head = new Node("head");
    this.head.next = this.head;
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.findPrevious = findPrevious;
    this.remove = remove;
    this.advance = advance;
    this.count = count;
}

function remove(item) {
    var prevNode = this.findPrevious(item);
    if (!(prevNode.next == this.head)) {
        prevNode.next = prevNode.next.next;
    }
}
function findPrevious(item) {
    var currNode = this.head;
    while (!(currNode.next == this.head) &&
        (currNode.next.element != item)) {
        currNode = currNode.next;
    }
    return currNode;
}
function display() {
    var currNode = this.head;
    while (!(currNode.next == this.head)) {
        print(currNode.next.element);
        currNode = currNode.next;
    }
}
function count() {
    var currNode = this.head;
    var count = 0;
    while (!(currNode.next == this.head)) {
        count++
        currNode = currNode.next;
    }
    return count;
}
function find(item) {
    var currNode = this.head;
    while (currNode.element != item) {
        currNode = currNode.next;
    }
    return currNode;
}
function insert(newElement, item) {
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}

function advance(item, n) {
    var currNode = this.find(item);
    for (let i = n; i > 0; i--) {
        currNode = currNode.next;
    }
    return currNode;
}



function survivor(number, position) {
    //40 compatriots
    //kill every third soldier. advance by 3
    //last two survivors

    //place n people in a circle
    var compatroits = new LList();
    var currNode = compatroits.head;

    for (let i = 1; i <= number; i++) {
        compatroits.insert(i, currNode.element);
        currNode = currNode.next;
    }

    //kill every mth person in the circle
    //start from head
    var currItem = compatroits.head.element;
    while (compatroits.count() > 2) {
        //advance mth person
        var killNode = compatroits.advance(currItem, position);

        //set new start point to m.next node
        currItem = killNode.next.element;

        //remove mth person
        compatroits.remove(killNode.element);
    }


    //determine the last two people in the circle
    return compatroits.display();
}

Есть ли у кого-нибудь более эффективный способ решения проблемы?

...