澳门新萄京PHP落成的遵照单向链表解决Joseph环难
分类:澳门新萄京

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("-号 ----> 自杀!n",Out->data);
         L ->next = Out->next;
         L = L->next;
         free(Out);
    }
    printf("幸存者是:%d",L->data);
    return 0;
}

澳门新萄京 1

本文实例讲述了PHP实现的基于单向链表解决约瑟夫环问题。分享给大家供大家参考,具体如下:

什么是约瑟夫环?
其实百度有说
http://baike.baidu.com/view/717633.htm

约瑟夫环问题:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

以一个传说中的问题为例子,提供源代码
澳门新萄京PHP落成的遵照单向链表解决Joseph环难题示例,叁个小笔记。主要是能够通过这个问题,了解如何来操作循环链表

更多的类似问题是:n个人围成圈,依次编号为1,2,..,n,现在从1号开始依次报数,当报到m时,报m的人退出,下一个人重新从1报起,循环下去,问最后剩下那个人的编号是多少?

在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏

代码实现:

最后输出结果为最后一个存活的人的编号

<?php
class Node{
  public $value;   // 节点值
  public $nextNode;  // 下一个节点
}
function create($node, $value){
  $node->value = $value;
}
function addNode($node, $value){
  $lastNode = findLastNode($node);
  $nextNode = new Node();
  $nextNode->value = $value;
  $lastNode->nextNode = $nextNode;
}
/* 找到最后的节点 */
function findLastNode($node){
  if(empty($node->nextNode)){
    return $node;
  }else{
    return findLastNode($node->nextNode);
  }
}
/* 删除节点 必须head为引用传值 */
function deleteNode(&$head, $node, $m, $k = 1){
  if($k   1 == $m){
    if($node->nextNode == $head){
      $node->nextNode = $node->nextNode->nextNode;
      $head = $node->nextNode;
      return $node->nextNode;
    }else{
      $node->nextNode = $node->nextNode->nextNode;
      return $node->nextNode;
    }
  }else{
    return deleteNode($head, $node->nextNode, $m,   $k);
  }
}
/* 节点数 */
function countNode($head, $node, $count = 1){
  if($node->nextNode == $head){
    return $count;
  }else{
    return countNode($head, $node->nextNode,   $count);
  }
}
function printNode($head, $node){
  echo $node->value . ' ';
  if($node->nextNode == $head) return;
  printNode($head, $node->nextNode);
}
function show($data){
  echo '<pre>';
  print_r($data);
  echo '</pre>';
}
$head = new Node();
create($head, 1);
addNode($head, 2);
addNode($head, 3);
addNode($head, 4);
addNode($head, 5);
addNode($head, 6);
addNode($head, 7);
addNode($head, 8);
addNode($head, 9);
addNode($head, 10);
addNode($head, 11);
addNode($head, 12);
$lastNode = findLastNode($head);
$lastNode->nextNode = $head;
$count = countNode($head, $head);
$tmpHead = $head;
while ($count > 2) {
  $tmpHead = deleteNode($head, $tmpHead, 3, 1);
  $count = countNode($head, $head);
}
printNode($head, $head);

 

更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《PHP基本语法入门教程》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》及《php程序设计算法总结》

 

希望本文所述对大家PHP程序设计有所帮助。

// 约瑟夫问题(循环链表).cpp
// Win32控制台程序
#include "stdafx.h" 
#include <stdlib.h> 

typedef struct JOSEPH_NODE 
{ 
    int iNum;   // 编号
    struct JOSEPH_NODE * pNext;
} JOSEPH_NODE_S; 

// pJosephStart结点的下一个结点就是要杀死的人,删除该结点
void Delete_Next_Joseph(JOSEPH_NODE_S * pJosephStart) 
{ 
    JOSEPH_NODE_S * pJose = pJosephStart->pNext; 
    pJosephStart->pNext = pJose->pNext; 
    free(pJose); 
} 

// 释放链表
void Destroy_Joseph(JOSEPH_NODE_S * pJosephHead) 
{ 
    while (pJosephHead->pNext != pJosephHead) 
    {
        Destroy_Joseph(pJosephHead); 
    } 
    free(pJosephHead);
} 

// 初始化链表
int Init_Joseph(int iCount, JOSEPH_NODE_S ** ppJosephHead) 
{ 
    if (iCount < 1)
    { 
        return 0; 
    } 

    JOSEPH_NODE_S * pJoseNew; 
    JOSEPH_NODE_S * pJoseCur;
    int iSize = sizeof(JOSEPH_NODE_S); 
    pJoseNew = (JOSEPH_NODE_S *)malloc(iSize); 

    if (pJoseNew == nullptr) 
    { 
        return 0; 
    } 

    pJoseNew->iNum = 1; 
    pJoseNew->pNext = pJoseNew;
    *ppJosephHead = pJoseNew; 
    pJoseCur = pJoseNew; 

    // 链表添加结点
    for (int i = 1; i < iCount; i  ) 
    { 
        pJoseNew = (JOSEPH_NODE_S *)malloc(iSize); 

        if (pJoseNew == nullptr) 
        { 
            Destroy_Joseph(*ppJosephHead); 
            return 0; 
        } 

        pJoseNew->iNum = i   1; 
        pJoseNew->pNext = *ppJosephHead; 

        pJoseCur->pNext = pJoseNew; 
        pJoseCur = pJoseNew; 
    } 

    return 1;
} 

// 得到最后一个存活的人
// iCount:总人数
// iSkip:每隔多少个人就杀死一个人
int GetLastNode_Joseph(int iCount, int iSkip) 
{ 
    JOSEPH_NODE_S * pJoseph = nullptr; 
    JOSEPH_NODE_S * pJoseStart = nullptr; 

    if (Init_Joseph(iCount, &pJoseph) != 1) 
    { 
        printf("初始化失败n");
        return 0; 
    }
    pJoseStart = pJoseph; 

    // 每隔0个人杀死,最后一个人存活
    if (iSkip == 0) 
    { 
        while (pJoseStart->pNext->pNext != pJoseStart) 
        { 
            Delete_Next_Joseph(pJoseStart); 
        } 

        printf("Final Num: %dnn", pJoseStart->pNext->iNum); 
        free(pJoseStart->pNext); 
        free(pJoseStart); 

        return 1; 
    } 

    // 每隔iSkip个人杀死一个人
    // 直到剩下1个人,剩下最后一个结点的pNext会指向自己
     while (pJoseStart->pNext != pJoseStart) 
    { 
        for (int i = 1; i < iSkip; i  ) 
        { 
            pJoseStart = pJoseStart->pNext; 
        } 

        Delete_Next_Joseph(pJoseStart); 

        pJoseStart = pJoseStart->pNext; 
    } 

    printf("Final Num: %dnn", pJoseStart->iNum); 

    free(pJoseStart); 


    return 1; 

} 

int main() 
{ 
    GetLastNode_Joseph(41, 2); 

    return 0; 

}

您可能感兴趣的文章:

  • php解决约瑟夫环示例
  • php实现约瑟夫问题的方法小结
  • 约瑟夫环问题的PHP实现 使用PHP数组内部指针操作函数
  • php约瑟夫问题解决关于处死犯人的算法
  • PHP使用栈解决约瑟夫环问题算法示例
  • PHP基于递归实现的约瑟夫环算法示例
  • PHP实现约瑟夫环问题的方法分析
  • PHP基于关联数组20行代码搞定约瑟夫问题示例
  • php基于环形链表解决约瑟夫环问题示例
  • PHP环形链表实现方法示例
  • php使用环形链表解决约瑟夫问题完整示例

 

本文由澳门新萄京发布于澳门新萄京,转载请注明出处:澳门新萄京PHP落成的遵照单向链表解决Joseph环难

上一篇:浏览器预览PHP文件时顶端现身空白影响布局解析 下一篇:没有了
猜你喜欢
热门排行
精彩图文