谁能笑到最后,约瑟夫环-Josephus问题求解
一、 简述Josephus问题
N个人站成一环,从1号开始,用刀将环中后面一个人“消灭“”掉,之后再将刀递给下一个人,这样依次处理,最后留下一个幸存者。
二、 求解方法
1. 约瑟夫问题如果使用链表来求解比较麻烦,这里采用循环队列的处理。
约瑟夫问题可以等价为l连续地DeQueue()两次,然后再将第一次DeQueue()的值EnQueue()入队列尾,直到队列中只剩下一个元素。
# 循环队列代码如下:
#include <stdio.h>
#include <stdlib.h> #define MAX 100 /* Maximum size of Queue */ typedef struct _Queue *Queue;
struct _Queue {
int A[MAX];
int Head, Tail;
int Num_of_Items;
}; /* Queue struct and pointer define */ void EnQueue( Queue Q, int x )
{
if ( Q->Num_of_Items < MAX ) {
/* Cycle Queue not full */
if ( Q->Num_of_Items == ) {
Q->Head = Q->Tail = ;
Q->A[] = x;
} else {
Q->Tail = (Q->Tail + ) % MAX; /* Tail insert */
Q->A[Q->Tail] = x;
}
Q->Num_of_Items++;
} else {
printf("Warning: Full Queue!\n");
return;
}
} int DeQueue( Queue Q )
{
if ( Q->Num_of_Items < ) {
/* empty queue */
printf("Warning: Empty Queue!\n");
} else {
int ret = Q->A[Q->Head];
Q->Num_of_Items--;
Q->Head = (Q->Head + ) % MAX;
return ret;
}
}
# 循环队列解约瑟夫问题:
void JosephusByQueue()
{
_Queue Que;
Queue Q = &Que; /* initial */
//Queue Q = (Queue)malloc( sizeof(struct _Queue) );
Q->Num_of_Items = ; int i, j, n, answer;
printf("Enter an integer (1--99):");
scanf("%d", &n); /* Solve Josephus Problem */
/* Step 1: Put all the number between 1 to n to the Queue */
for ( i = ; i <= n; i++ ) {
EnQueue( Q, i);
} /* Step 2: Start killing for n-1 rounds */
for ( i = ; i < n; i++ ) {
j = DeQueue( Q ); /* first dequeue item */
DeQueue( Q );
EnQueue( Q, j );
} answer = Q->A[Q->Head]; /* the last item */
printf("The value of J(%d) is: %d\n", n, answer);
}
2. 每次隔一个人就消灭掉一人,经过一圈,消灭一半,就等于累次除二。等价于二的幂相关问题。
对于Josephus( N ):
[1] 若N为二次幂(N = 2^M),M为幂次。从开始一圈消除偶数,再消除奇数,每次跳过起始的1,最终留下1。
EX 1: J( 8 ): Green : start , Red: delete
2 3 4 5 6 7 8 --> 1 2 3 4 5 6 7 8 --> 1 3 5 7
--> 1 3 5 7 --> 5 --> 1 5 --> 1
[2] 若N为奇数,可化为(N = 2^M + K),先 消除K个人,即经历过2K个人后。又为偶数问题,留下的[ Last=2K+1 ]。
EX 2: J( 10 ) : N = 10, M = 3, K = 2 --> J( 10 ) = 2*k + 1 = 5
公式: N = 2^M + K , K= N - 2^M。 J( N ) = 2 *( N - 2^M ) + 1
求解代码:
/* 数学解法:N = 2^M + K | Last = 2 *( N - 2^M ) + 1 */
void Josephus()
{
int i, n, m_prime, k;
printf("Enter an integer:");
scanf("%d", &n); i = ;
while ( i < n ) {
/* find the largest power of 2 that less than n */
i *= ;
}
m_power = i / ;
k = n - m_power;
printf("The remain one is %d!\n", ( * k + ));
}
主函数:
int main(int argc, char *argv[])
{
printf("Method 1: Math solving\n");
Josephus(); printf("\nMethod 2: Queue solving\n");
return ;
}
参考资料:
[1] 中国大学MOOC-数据结构-台湾清华大学-04BasicDataStructure
[2] 2的幂在约瑟夫环问题的应用https://www.cnblogs.com/sirlipeng/p/5387830.html#undefined
图片来自网络
最新文章
- 7.2WebApi2中的全局异常处理
- SQL --Chater03 聚合与排序
- 在eclipse中安装配置WebDriver
- 前端利器:SASS基础与Compass入门
- SharePoint 2013 内容部署功能简介
- Jdk5.0中出现的新特性
- poj3101
- ThoughtWorks的面试总结
- 一次CMS GC问题排查过程(理解原理+读懂GC日志)
- CF1119C Ramesses and Corner Inversion
- [转]Java调用Javascript、Python算法总结
- SQL DCL 数据控制语句
- Thinkphp框架 表单自动验证登录注册 ajax自动验证登录注册
- LeetCode 7 Reverse Integer &; int
- 【Leetcode】33. Search in Rotated Sorted Array
- StringUtils方法全集(转)
- 内存与cpu的关系
- PAT 1024 Palindromic Number[难]
- Angular5 UI post 请求 输出 文件下载
- Ubuntu下安装Sublime Text3
热门文章
- PowerDesigner表设计转化为excel或者markdown
- 关于 Windows 7 语言包
- 设计模式:仲裁者(Mediator)模式
- antd button
- dailiaojie new
- 【2017.09.15 智能驾驶/汽车电子】汽车高级驾驶辅助ADAS常用传感器厂商:激光雷达篇
- ZT sem_init sem_wait sem_post sem_destroy
- [原]Ping azure
- 轻松bypass360网站卫士WAFSQL注入防护
- 026json和pickle,xml模块