鱼C论坛

 找回密码
 立即注册

鱼C作业-约瑟夫问题

热度 1已有 748 次阅读2013-3-7 23:26 |个人分类:鱼C-作业

/**************************************************************************************/
//题目:用循环链表模拟约瑟夫问题,把41个人自杀的顺序编号输出。
//故事情节:
 //   据说著名犹太历史学家 Josephus有过以下的故事:
//在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,
//39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,
//41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,
//然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从,
//Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,
//于是逃过了这场死亡游戏。
/***************************************************************************************/

#include<stdio.h>
#include<stdlib.h>

/*************************************************/
/*链表声明*/
/*************************************************/
typedef int ElementType;
struct Node;
typedef struct Node* PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node
{
 ElementType Element;
 Position Next;
};

/*************************************************/
/*循环链表*/
/*************************************************/
Position Circulate_LinkList(int n)
{
 Position Head=(Position)malloc(sizeof(Node));
 if(Head == NULL)
 {
  printf("动态内存分配失败,程序结束!!");
 }

 int i=1;
 Position p,s;

 p=Head;
   
 if(n != 0)
 {
  while(i <= n)
  {
          s=(Position)malloc(sizeof(Node));
          if(s == NULL)
    {
        printf("动态内存分配失败,程序结束!!!");
    }
          s->Element=i++;
             p->Next=s;
       p=s;
  }
  s->Next=Head->Next;
 }

 free(Head);

 return s->Next;

}

/*************************************************/
/*主函数*/
/*************************************************/
int main()
{
 int n=41;
 int m=3;

 Position Temp;
 Position Point;

    Point=Circulate_LinkList(n);

 m %= n;                                 // m在这里是等于3

 while (Point != Point->Next )           //判断条件就是这个循环链表是不是空链表
 {
  for (int i = 1; i < m-1; i++)
  {
   Point = Point->Next ;
  }

  printf("%d->", Point->Next->Element );

  Temp = Point->Next ;    //删除第m个节点
  Point->Next = Temp->Next ;
  free(Temp);

  Point = Point->Next ;
 }

 printf("%d\n", Point->Element );

 return 0;
}
 

 

 


路过

鸡蛋

鲜花
1

握手

雷人

刚表态过的朋友 (1 人)

发表评论 评论 (1 个评论)

回复 魔火 2013-7-23 11:01
灵活运用了类型别名

facelist

您需要登录后才可以评论 登录 | 立即注册

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 16:47

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

返回顶部