约瑟夫经典问题扩展成双向约瑟夫问题

  • 更新时间:2022-10-10 09:24:05
  • 编辑:容宏达

约瑟夫问题是一个经典的问题,我们不妨将这个经典问题进行扩展,变成一个双向的约瑟夫问题。

已知 n 个人(不妨分别以编号 1,2,3,...,n 代表 )围坐在一张圆桌周围,首先从编号为 k 的人从 1 开始顺时针报数,1, 2, 3, ...,记下顺时针数到 m 的那个人,同时从编号为 k 的人开始逆时针报数,1, 2, 3, ...,数到 m 后,两个人同时出列。然后从出列的下一个人又从 1 开始继续进行双向报数,数到 m 的那两个人同时出列,...;。依此重复下去,直到圆桌周围的人全部出列。直到圆桌周围只剩一个人为止。

如果双向报数报到 m 时落在同一个人身上,那本次出列的只有一个人。

例如:5,1,2。则总共5个人,从1开始顺时针报数,数到2,定位编号2;同时从1开始报数数到2,定位编号5;2和5同时出列。然后继续开始报数,顺时针报数3,4,定位到4;逆时针报数4,3,定位3;4和3同时出列。最后剩余的为编号1。输出为:2-5,4-3,1,。

如果输入:6,2,3。则输出:4-6,2,1-3,5,。其中第2次只输出一个2,表示第二次双向报数时,恰好都落在编号2上,所以只有一个编号出列。

输入:

n,k,m

输出:

按照出列的顺序依次输出编号。同时出列编号中间用减号"-”连接。

非法输入的对应输出如下

a)

  • 输入:n、k、m任一个为0
  • 输出:n,m,k must bigger than 0.

b)

  • 输入:k>n
  • 输出:k should not bigger than n.

测试输入

1,0,0
1,2,1
5,1,2

测试输出

n,m,k must bigger than 0.
k should not bigger than n.
2-5,4-3,1,

源代码

#include<stdio.h> 
#include<malloc.h> 
#include<stdlib.h> 
typedef int ElemType; 
int n,m,k; //定义一个全局变量  
typedef struct DuLNode    //双向循环链表结构 
{ 
  ElemType data; 
  struct DuLNode *prior; 
  struct DuLNode *next; 
}DuLNode,*DuLinkList;   
void Create(DuLinkList &H)  //创建带头结点的双向循环链表  
{ 
  DuLinkList p,q; 
  int i; 
  H=(DuLinkList)malloc(sizeof(DuLNode));  
  p=H; 
  q=H; 
  for(i=1;i<=n;i++) 
  { 
    p=(DuLinkList)malloc(sizeof(DuLNode)); 
    p->data=i; 
    p->prior=q; 
    q->next=p; 
    q=p; 
  } 
  p->next=H; 
  H->prior=p; 
} 
void Delete(DuLinkList &P) //删除结点  
{ 
  P->prior->next=P->next; 
  P->next->prior=P->prior; 
} 
int main() 
{ 
  int i; 
  DuLinkList H,l,R,right,left; //分别用以表示头结点,l和R都用于找k的值,向右(顺时针),向左(逆时针)  
  scanf("%d,%d,%d",&n,&k,&m);  
    if(!n||!k||!m) 
    { 
      printf("n,m,k must bigger than 0.\n"); 
      return 0;   
    } 
    if(k>n) 
    { 
      printf("k should not bigger than n.\n"); 
      return 0; 
    }     
    Create(H); 
    R=H->next ; 
    while(R->data!=k) 
    { 
      R=R->next; 
    } 
    l=R; 
    while(n) 
    { 
      right=R; 
      left=l; 
      for(i=1;i<m;i++) 
      { 
        right=right->next; 
        left=left->prior; 
        //遇见头结点需要特殊处理 
        if(right==H) 
          right=right->next; 
        if(left==H) 
          left=left->prior; 
      } 
      R=right->next; 
      l=left->prior; 
      if(R==H) 
        R=R->next; 
      if(l==H) 
        l=l->prior; 
      if(right!=left) 
      { 
        n=n-2; 
        printf("%d-%d,",right->data,left->data); 
        Delete(right); 
        Delete(left); 
      } 
      else 
      { 
        n=n-1; 
        printf("%d,",right->data); 
        Delete(right);  
      } 
    } 
    printf("\n");  
} 

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对码农之家的支持。如果你想了解更多相关内容请查看下面相关链接

相关教程

  • C语言实现C++继承和多态的实例内容

    本文主要给大家简单讲诉了C和C++的区别以及如何使用C语言模拟实现C++继承和多态,并附上示例代码,是篇相当不错的文章,推荐给喜欢C语言的小伙伴们

    发布时间:2021-06-10

  • VC++中进程与多进程管理的方法详解

    这篇文章主要介绍了VC++中进程与多进程管理的方法,以实例形式详细分析了进程与多进程管理中所涉及的进程、子进程、进程的互斥运行与进程的结束等概念与具体实现方法,非常具有参考借鉴价值,需要的朋友可以参考下

    发布时间:2021-05-28

  • 浅谈C++函数声明后面加throw()的作用(必看)

    下面小编就为大家带来一篇浅谈C++函数声明后面加throw()的作用(必看)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧

    发布时间:2022-04-14

  • C++实现数字转换为十六进制字符串的方法

    这篇文章主要介绍了C++实现数字转换为十六进制字符串的方法,涉及C++操作数字与字符串转换的相关技巧,需要的朋友可以参考下

    发布时间:2022-04-16

  • VC++文件监控之FindFirstChangeNotification

    VC++文件监控之FindFirstChangeNotification

    给大家整理一篇关于VC++的教程,因为ReadDirectoryChangesW 上次测试发现不能多级目录监控,所以尝试用FindFirstChangeNotification来实施文件监控,需要的朋友可以参考下

    发布时间:2022-06-23

  • JNI实现最简单的JAVA调用C/C++实例代码讲解

    这篇文章主要介绍了JNI实现最简单的JAVA调用C/C++代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2019-09-02

  • C/C++指针和取地址的方法

    C/C++指针和取地址的方法,需要的朋友可以参考一下

    发布时间:2022-04-01

  • C++常量详解一(常量指针与常量引用的初始化)

    为网友们分享了关于C++的教程,这篇文章主要介绍了C++常量详解一(常量指针与常量引用的初始化),需要的朋友可以参考下

    发布时间:2022-07-25

  • C++编译器无法捕捉到的8种错误实例分析

    这篇文章主要介绍了C++编译器无法捕捉到的8种错误,是深入学习C++所必须加以掌握的排错技能,需要的朋友可以参考下

    发布时间:2021-06-09

  • C++中拷贝构造函数的使用

    大家好,本篇文章主要讲的是C++中拷贝构造函数的使用,感兴趣的同学赶快来看一看吧,对你有帮助的话记得收藏一下

    发布时间:2022-04-21

用户留言