PHP实现的依据单向链表消除Joseph环难题示例,Joseph难点

by admin on 2019年3月20日

1.率先,大家先来询问一下哪些是Joseph环难题:

讲三个相比较有意思的传说:Joseph是犹太军队的一个战将,在对抗开普敦的首义中,他所教导的行伍被重创,只剩下残余的军事40余人,他们都是强项的人,所以不愿投降做叛徒。一群人决定说要死,所以用一种政策来先后杀死全体人。 
于是乎Joseph建议:每便由其他五个人一道杀掉一位,而被杀的人的先后顺序是由抽签决定的,Joseph有机关地抽到了最后一签,在杀了除了她和多余那个家伙之外的尾声1个人,他劝服了其它三个没死的人投降了布加勒斯特。

 

伊始来说正是:

遵守如下规则去杀人:

  • 全体人围成一圈
  • 顺时针报数,每趟报到3的人将被杀掉
  • 被杀掉的人将从房间内被移走
  • 然后从被杀掉的下一位重复报数,继续报3,再清除,直到剩下1个人

那么程序已毕为:

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

  

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

PHP实现的依据单向链表消除Joseph环难题示例,Joseph难点。 

由于是循环,直到最后一人, 全数能够行使尤其的链表: 循环链表。
当链表中只剩余3个元素后,便觉得完事了。 即 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;
}

home88一必发 1

1.第壹,我们先来询问一下怎样是Joseph环难题:

明日看了须臾间Joseph难题,嗯,感觉自个儿智力商数欠费:( 照旧来计算下好啦~

本文实例讲述了PHP实现的根据单向链表化解Joseph环难题。分享给我们供大家参考,具体如下:

讲多个比较有趣的逸事:Joseph是犹太军队的一个主力,在抵抗汉堡的首义中,他所指引的大军被克服,只剩余残余的大军40余人,他们都以钢铁的人,所以不愿投降做叛徒。一群人决定说要死,所以用一种政策来先后杀死全体人。
于是乎约瑟夫提议:每一回由其余四人合伙杀掉1位,而被杀的人的先后顺序是由抽签决定的,约瑟夫有预谋地抽到了最后一签,在杀了除了她和剩余那家伙之外的末梢一位,他劝服了此外贰个没死的人投降了波士顿。

问题

Joseph是犹太军事的1个老马,在抵御罗马的起义中,他所教导的武装力量被粉碎,只剩余残余的武装力量40余人,他们都以钢铁的人,所以不愿投降做叛徒。一群人核定说要死,所以用一种政策来先后杀死全体人。
于是乎Joseph提议:每一遍由其余几个人共同杀掉壹位,而被杀的人的先后顺序是由抽签决定的,Joseph有对策地抽到了最终一签,在杀了除去他和剩下那家伙之外的末了一位,他劝服了其余三个没死的人投降了拉各斯。

我们以此规则是如此定的:
在一间房间总共有n个人(下标0~n-1),只好有最后一位活命。

规行矩步如下规则去杀人:
全数人围成一圈
顺时针报数,每便报到q的人将被杀掉
被杀掉的人将从房间内被移走
接下来从被杀掉的下一人另行报数,继续报q,再清除,直到剩余1位

约瑟夫环难题:在奥克兰人攻克乔塔Pat后,3五个犹太人与Josephus及他的对象躲到3个洞中,肆12个犹太人决定宁愿死也决不被敌人抓到,于是决定了三个轻生模式,41私人住房排成1个圆形,由第③个人先导报数,每报数到第③个人该人就非得自杀,然后再由下3个重复报数,直到全部人都自杀身亡截至。不过Josephus
和他的爱侣并不想服从。首先从壹人开头,越过k-4个人(因为第①私有已经被通过),并杀死第k私有。接着,再越过k-1人,并杀死第k个体。那个历程沿着圆圈一向开始展览,直到最后只剩余壹位留下,这厮就足以继续活着。难题是,给定了和,一初阶要站在怎么地点才能防止被处决?Josephus要他的心上人先假装遵守,他将对象与和谐配置在第一四个与第一十个职务,于是逃过了这一场亡故游戏。

PHP实现的依据单向链表消除Joseph环难题示例,Joseph难点。通俗来说正是:

输入

人的个数 : n
每一遍报到q 就会被杀死 的 q

更加多的类似题材是:n个人围成圈,依次编号为1,2,..,n,今后从1号开头逐项报数,当报到m时,报m的人脱离,下一位另行从1报起,循环下去,问最终剩余那家伙的数码是稍微?

根据如下规则去杀人:
全数人围成一圈
home88一必发,顺时针报数,每趟报到3的人将被杀掉
被杀掉的人将从房间内被移走
然后从被杀掉的下一人再次报数,继续报3,再清除,直到剩下1个人

输出

最后能够活下来的人的下标

代码落成:

那正是说程序达成为:

连带分析

1、https://blog.csdn.net/tingyun\_say/article/details/52343897
2、http://www.cnblogs.com/kkrisen/p/3569281.html\#undefined

<?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);

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

分析

先是次报数杀掉的是下标为(q-1)人
q       0
q+1     1
:       :
:        :
n-1     n-q-1
0      n-q
1      n-q+1
:        :
:        :
q-2     n-2

由上述可知,杀掉一位后,重新构成了二个Joseph环,重新构成的Joseph环的下标和事先的下标关系为
f(n)=(f(n-1)+q)%n。当最终只剩余1位的时候,它的下标为0,大家可由上述的递推关系获得只剩余四人时它的下标,然后再推得只剩下二人时它的下标,一直推到最终有n个人时,它的下标,就拿走了最后的结果。请注意,这样的解法所得到的坐标是从以0–(n-1)为尺度的,假若想赢得以1–n为标准下的,直接将所得的结果加1就好了,很直观的解释正是将下标值加1。
另四个表达:
f(1, 1) = 1;
f(n, k) = (f(n-1, k) + k – 1)%n + 1;

#include "stdafx.h"
#include <iostream>
using namespace std;

int main()
{
    int n, q;
    cin >> n >> q;
    if (n == 0)
        return 0;
    int result = 0;
    for (int i = 2; i <= n; i++)
        result = (result + q ) % i;

    return result+1;
}

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

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

变动难题

poj上有个转移难题,标题链接:http://poj.org/problem?id=3517,这些题与经典Joseph难点的界别是,它须要首先个干掉的人下标为m,并且下标从1方始。对于那个题材的求解,大家得以依照原先格局去做,获得结果后再去运动下标。在原先的难点中,第②个干掉的人下标为q,大家想方法运动下标使得第一个干掉的人由q变为m,要是n=5,q=2,m=4,
那么原始系列为
1, 2, 3,4,5
万一使得第③回杀死的人为m, 那么连串应为
3 , 4 , 5 ,1 , 2
那正是说由地点的什么获得上面包车型大巴结果
f(下)= (f(上)+m-k)%n

// yuesefu.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

int main()
{
    int n, q, m;
    cin >> n >> q>> m;
    if (n == 0)
        return 0;
    int mid = 0;
    for (int i = 2; i <= n; i++)
        mid = (mid + q ) % i;
    int result = 0;
    result = (mid + 1 + m - q) % n;
    if (result < 0) result = result + n;
    return result;
}

盼望本文所述对大家PHP程序设计有着支持。

出于是循环,直到最终1位, 全数可以使用12分的链表: 循环链表。
当链表中只剩余一个成分后,便觉得完事了。 即 L->next = L;

留个坑

一 、打字与印刷每一次淘汰的人
https://blog.csdn.net/coder\_pig/article/details/50268099
2、如何用python实现?

index, step = 0, 3    
while len(a) > 1:
    index = (index + step - 1) % len(a)    
    print('kill No.', a[index])
    del a[index]
print('\nWinner is', a[0])

你大概感兴趣的稿子:

  • php解决Joseph环示例
  • php完成Joseph难点的法门小结
  • 约瑟夫环难点的PHP完毕使用PHP数组内部指针操作函数
  • phpJoseph难题一蹴而就有关镇压犯人的算法
  • PHP使用栈化解Joseph环难题算法示例
  • PHP基于递归达成的Joseph环算法示例
  • PHP完结Joseph环难题的章程分析
  • PHP基于关联数组20行代码消除Joseph难题示例
  • php基于环形链表化解约瑟夫环难点示例
  • PHP环形链表达成格局言传身教
  • php使用环形链表化解Joseph难点总体示例

#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;
}

home88一必发 2

本文永久更新链接地址

home88一必发 3

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图