菜单

Joseph难点

2019年4月12日 - www6165com

一.先是,我们先来通晓一下什么是Joseph环难题:

讲一个相比有趣的传说:约瑟夫是犹太军事的二个老马,在对抗亚特兰洲大学的起义中,他所指点的部队被粉碎,只剩余残余的队540余名,他们都以钢铁的人,所以不愿投降做叛徒。一批人核定说要死,所以用壹种政策来先后杀死所有人。 
于是乎Joseph提议:每一遍由别的两个人1同杀掉一人,而被杀的人的先后顺序是由抽签决定的,Joseph有机关地抽到了最后一签,在杀了除了她和多余那个家伙之外的末段一位,他劝服了其余二个没死的人投降了亚特兰洲大学。

 

浅显的话正是:

根据如下规则去杀人:

那么程序落成为:

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

#include <stdio.h>
#include <stdlib.h>
#include “Linklist.h”

分析

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

由上述可知,杀掉一位后,重新组合了二个Joseph环,重新组合的约瑟夫环的下标和在此以前的下标关系为
f(n)=(f(n-1)+q)%n。当最后只剩余1位的时候,它的下标为0,大家可由上述的递推关系取得只剩余几人时它的下标,然后再推得只剩余三位时它的下标,一贯推到最后有n个人时,它的下标,就赢得了最后的结果。请注意,那样的解法所获得的坐标是从以0–(n-一)为条件的,假若想博得以1–n为原则下的,直接将所得的结果加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;
}

Joseph环难点:在汉堡人占领乔塔Pat后,3九个犹太人与Josephus及他的爱侣躲到二个洞中,35个犹太人决定宁愿死也毫无被仇敌抓到,于是决定了二个轻生格局,四一私有排成3个圆形,由第贰个人起首报数,每报数到第一位该人就不能够不自杀,然后再由下二个双重报数,直到全体人都自杀身亡截止。但是Josephus
和他的爱人并不想服从。首先从一人开始,越过k-4人(因为第3个体已经被通过),并杀死第k民用。接着,再越过k-一人,并杀死第k私家。这几个进度沿着圆圈一直进展,直到最后只剩余1位留下,这厮就足以一连活着。问题是,给定了和,1开始要站在如啥地点方才能防止被处死?Josephus要他的对象先假装服从,他将情人与和睦布置在第3伍个与第23个地方,于是逃过了这场身故游戏。

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

变化难题

poj上有个变化难点,难题链接:http://poj.org/problem?id=3517,那个题与经典Joseph难点的差异是,它需求首先个干掉的人下标为m,并且下标从1起来。对于这几个标题标求解,我们得以遵照原先方式去做,获得结果后再去运动下标。在原来的题材中,第三个干掉的人下标为q,咱们想办法运动下标使得第二个干掉的人由q变为m,借使n=5,q=2,m=四,
那么原始类别为
1, 2, 3,4,5
借使使得第1次杀死的人为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;
}

你或然感兴趣的小说:

鉴于是循环,直到最终1个人, 全部可以动用特殊的链表: 循环链表。
当链表中只剩余2个因素后,便认为完事了。 即 L->next = L;

输出

末尾能够活下来的人的下标

代码完结:

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

今日看了刹那间Joseph难题,嗯,感觉温馨智力商数欠费:( 照旧来计算下好啦~

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

相关文章

发表评论

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

网站地图xml地图