约瑟夫问题
分类:美高梅-操作

1.首先,我们先来了解一下什么是约瑟夫环问题:

讲一个比较有意思的故事:约瑟夫是犹太军队的一个将军,在反抗罗马的起义中,他所率领的军队被击溃,只剩下残余的部队40余人,他们都是宁死不屈的人,所以不愿投降做叛徒。一群人表决说要死,所以用一种策略来先后杀死所有人。 
于是约瑟夫建议:每次由其他两人一起杀死一个人,而被杀的人的先后顺序是由抽签决定的,约瑟夫有预谋地抽到了最后一签,在杀了除了他和剩余那个人之外的最后一人,他劝服了另外一个没死的人投降了罗马。

 

通俗来说就是:

按照如下规则去杀人:

  • 所有人围成一圈
  • 顺时针报数,每次报到3的人将被杀掉
  • 被杀掉的人将从房间内被移走
  • 然后从被杀掉的下一个人重新报数,继续报3,再清除,直到剩余一人

那么程序实现为:

  链表的定义: 定义为编号即可 所以data项为int

约瑟夫问题。  

typedef struct NODE{
    struct NODE *next;
    int data;
}Node,*Linklist;

 

由于是循环,直到最后一个人, 所有可以使用特殊的链表: 循环链表。 当链表中只剩下一个元素后,便认为完事了。 即 L->next = L;

#include <stdio.h>
#include <stdlib.h>
#include "Linklist.h"

void Print_Linklist(Linklist L)
{
    Linklist head = L;
    printf("List: ");
    while(L->next != head)
    {
        printf("%d ",L->data);
        L = L->next;
    }
    printf("%d ",L->data);
    printf("n");
}

int main()
{
    int i;
    Linklist L;
    Linklist head;
    Linklist Out;
    L = (Node*)malloc(sizeof(Node));
    head = L;
    L->data = 1;
    L->next = head;
    for(i=2;i<=41;i++)
    {
        L->next=(Node*)malloc(sizeof(Node));
        L->next->data = i;
        L->next->next = head;
        L = L->next;
    }
    Print_Linklist(head);
    L = head;
    while(L != L->next)
    {
         for(i=1;i<2;i++)
         {
             L = L->next;
         }
         Out = L->next;
         printf("%2d号 ----> 自杀!n",Out->data);
         L ->next = Out->next;
         L = L->next;
         free(Out);
    }
    printf("幸存者是:%d",L->data);
    return 0;
}

图片 1

代码实现

最后结果是约瑟夫和他的同伴一个站在队伍的第4个,一个站在队伍的第10个,最后只剩下他们两个人。不知道历史上有没有这件事,如果真的有这件事,在这么短的时间内解决这个问题,约瑟夫真他么是个天才,不知道当时他有没有用指针来解决这个问题,还是用普通的数组递归解决。

var node = this.head;var i = 0;while (!(node.next.element == "head")){ node = node.next; i++;}return i;

代码如下:

代码如下:

前言

while { if(this.currentNode.next.element == "head"){ this.currentNode = this.currentNode.next.next; }else{ this.currentNode = this.currentNode.next; } n--;}

传说在公元1 世纪的犹太战争中,犹太历史学家弗拉维奥·约瑟夫斯和他的40 个同胞被罗马士兵包围。犹太士兵决定宁可自杀也不做俘虏,于是商量出了一个自杀方案。他们围成一个圈,从一个人开始,数到第三个人时将第三个人杀死,然后再数,直到杀光所有人。约瑟夫和另外一个人决定不参加这个疯狂的游戏,他们快速地计算出了两个位置,站在那里得以幸存。写一段程序将n 个人围成一圈,并且第m个人会被杀掉,计算一圈人中哪两个人最后会存活。使用循环链表解决该问题。

在初始化链表的时候我们定义一个当前节点,将它赋值为头节点this.currentNode = this.head; ,这样在移动节点的时候就可以用它指向下一个节点。向前移动节点的时候有个地方需要注意,如果当前移动到头节点上需要再向前移动一个节点this.currentNode.next.next

看到这个问题首先想到的是要用到循环链表,还有就是要计算链表中有多少个元素,这两点很重要。再有就是找到当前节点和在链表中向前移动m个节点。下面一一分析:循环链表很容易实现,就是初始化的时候使链表的头节点的下一个指向它自己,这样初始化一个空节点,注意链表的头不是节点。写法如下:this.head.next = this.head;计算链表中有多少个元素也很简单,只需要找到头节点,然后往下走直到再次回到头结点

这里我们假设有10个人,每次数到第三个人的时候这个人自杀,最后输出的结果如下:

/** * 使用循环链表实现解决约瑟夫环问题 * *///链表节点function Node{ this.element = element; this.next = null;}//定义链表类function LList(){ this.head = new Node; this.head.next = this.head; this.find = find; this.insert = insert; this.findPrevious = findPrevious; this.remove = remove; this.currentNode = this.head; //从链表当前节点向前移动n个节点 this.advance = advance; //当前链表中有多少个元素 this.count = count; this.display = display;}//查找节点function find{ var currNode = this.head; while (currNode.element != item){ currNode = currNode.next; } return currNode;}//插入新节点function insert{ var newNode = new Node; var current = this.find; newNode.next = current.next; current.next = newNode;}//查找当前节点的上一个节点function findPrevious{ var currNode = this.head; while (!(currNode.next == null) && (currNode.next.element != item)){ currNode = currNode.next; } return currNode;}//移除当前节点function remove{ var prevNode = this.findPrevious; if(!(prevNode.next == null)){ prevNode.next = prevNode.next.next; }}//向前移动n个节点function advance{ if(this.currentNode.next.element == "head"){ this.currentNode = this.currentNode.next.next; }else{ this.currentNode = this.currentNode.next; } n--; }}//当前链表中有多少个元素function count(){ var node = this.head; var i = 0; while (!(node.next.element == "head")){ node = node.next; i++; } return i;}//输出所有节点function display(){ var currNode = this.head; while (!(currNode.next == null) && !(currNode.next.element == "head")){ document.write(currNode.next.element + ""); currNode = currNode.next; }}var person = new LList();person.insert;person.insert;person.insert;person.insert;person.insert;person.insert;person.insert;person.insert;person.insert;person.insert;person.display();document.write;var n = 3;while { person.advance; person.remove(person.currentNode.element); person.display(); document.write;}

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流。

总结

本文由美高梅网站是多少发布于美高梅-操作,转载请注明出处:约瑟夫问题

上一篇:没有了 下一篇:没有了
猜你喜欢
热门排行
精彩图文