【数据结构】Joseph难点 C语言链表完结

壹.先是,大家先来打听一下怎么着是约瑟夫环难点:

讲2个相比较好玩的传说:约瑟夫是犹太军队的二个新秀,在对抗休斯敦的首义中,他所携带的武装力量被重创,只剩余残余的武装40余名,他们都以坚强的人,所以不愿投降做叛徒。一群人核定说要死,所以用1种政策来先后杀死全部人。 
于是Joseph提议:每便由别的四人合伙杀掉1个人,而被杀的人的先后顺序是由抽签决定的,Joseph有预谋地抽到了最后一签,在杀了除了她和多余那家伙之外的尾声1人,他劝服了别的三个没死的人投降了奥斯6。

 

浅显的话正是:

依照如下规则去杀人:

  • 全体人围成壹圈
  • 顺时针报数,每一趟报到三的人将被杀掉
  • 被杀掉的人将从房间内被移走
  • 下一场从被杀掉的下一位再一次报数,继续报叁,再清除,直到剩余一位

那么程序完成为:

  链表的定义: 定义为编号即可 所以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

出于是循环,直到最后1人, 全数能够选拔异乎平常的链表: 循环链表。
当链表中只剩余3个成分后,便觉得完事了。 即 L->next = L;

问题

Joseph是犹太军队的叁个良将,在对抗亚特兰洲大学的首义中,他所带领的行5被重创,只剩余残余的军事40余人,他们都以坚强的人,所以不愿投降做叛徒。一堆人核定说要死,所以用一种政策来先后杀死全数人。
于是Joseph建议:每趟由此外四个人联手杀掉1个人,而被杀的人的先后顺序是由抽签决定的,约瑟夫有心计地抽到了最后壹签,在杀了除了她和剩余那个家伙之外的末段一位,他劝服了别的1个没死的人投降了杜塞尔多夫。

咱俩以此规则是那样定的:
在一间房间总共有n个人(下标0~n-一),只能有最终壹个人活命。

依据如下规则去杀人:
全部人围成一圈
顺时针报数,每回报到q的人将被杀掉
被杀掉的人将从房间内被移走
接下来从被杀掉的下一位再也报数,继续报q,再清除,直到剩余一个人

代码落成:

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、https://blog.csdn.net/tingyun\_say/article/details/52343897
2、http://www.cnblogs.com/kkrisen/p/3569281.html\#undefined

越多的接近题材是:n个人围成圈,依次编号为一,2,..,n,今后从一号开端逐项报数,当报到m时,报m的人脱离,下一位重新从1报起,循环下去,问最后剩余那家伙的号子是多少?

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”);
}

输出

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

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

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

输入

人的个数 : n
老是报到q 就会被杀死 的 q

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

发表评论

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