http://blog.csdn.net/zhuimengzh/article/details/6727221

用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。写出C程序

 

// 用户输入M,N值，从1至N开始顺序// 循环数数，每数到M输出该数值，// 直至全部输出#include 
     
      // 节点typedef struct node{    int data;    node* next;}node;// 创建循环链表void createList(node*& head, node*& tail, int n){    if(n<1)    {        head = NULL;        return ;    }    head = new node();    head->data = 1;    head->next = NULL;       node* p = head;    for(int i=2; i
      
       next = new node();        p = p->next;        p->data = i;        p->next = NULL;    }       tail = p;    p->next = head;}// 打印循环链表void Print(node*& head){    node* p = head;       while(p && p->next!=head)    {        printf("%d ", p->data);        p=p->next;    }    if(p)    {        printf("%d\n", p->data);    }}// 用户输入M,N值，从1至N开始顺序// 循环数数，每数到M输出该数值，// 直至全部输出void CountPrint(node*& head, node*& tail, int m){    node* cur = head;    node* pre = tail;       int cnt = m-1;    while(cur && cur!=cur->next)    {        if(cnt)        {            cnt--;            pre = cur;            cur = cur->next;        }        else        {            pre->next = cur->next;            printf("%d ", cur->data);            delete cur;            cur = pre->next;            cnt = m-1;        }       }       if(cur)    {        printf("%d ", cur->data);        delete cur;        head = tail = NULL;    }    printf("\n");}int main(){    node* head;    node* tail;    int m;    int n;    scanf("%d", &n);    scanf("%d", &m);    createList(head, tail, n);    Print(head);    CountPrint(head, tail, m);system("pause");    return 0;}
      
     

 

 

约瑟夫环问题算法

已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编

号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报

数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全

部出列。

　　例如：n = 9, k = 1, m = 5

　【解答】

　　出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。

 

链表方法

　　这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三

个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据

结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head

　　解决问题的核心步骤：

　　1.建立一个具有n个链结点，无头结点的循环链表

　　2.确定第1个报数人的位置

　　3.不断地从链表中删除链结点，直到链表为空

 

/*约瑟夫环*/ 

#include   
     
       #include   
      
        typedef   struct   node {   int   data;   struct   node   *next; }LNode; main() {   LNode*   Create(int,int);   LNode*   GetNode(LNode   *);   int   Print(LNode   *,int);   LNode   *p;   int   n,k,m;   do   {     printf   ( "输入总人数 ");     scanf   ( "%d ",&n);   }   while   (n <=0);   do   {     printf   ( "输入开始人的序号(1~%d) ",n);     scanf   ( "%d ",&k);   }   while   (k <=0   ||   k> n);   do   {     printf   ( "输入间隔数字 ");     scanf   ( "%d ",&m);   }   while(m <=0);   p=Create(n,k);   Print(p,m);   return   0; }； LNode*   Create(int   n,int   k)/*创建循环链表*/ {   int   start=k-1;   LNode   *s,*p,*L=0,*t;   if   (start==0)   start=n;   while   (n!=0)   {     s=(LNode   *)malloc(sizeof(LNode));     if   (L==0)   p=s;     if   (n==start)   t=s;     s-> data=n;     s-> next=L;     L=s;     n--;   }   p-> next=L;   return   t; } LNode*   GetNode(LNode   *p)/*出队函数*/ {   LNode   *q;   for   (q=p;q-> next!=p;q=q-> next);   q-> next=p-> next;   free   (p);   return   (q); } Print(LNode   *p,int   m)/*输出函数*/ {   int   i;   printf   ( "出队编号:\n ");   while   (p-> next!=p)   {     for   (i=1;i <=m;i++)       p=p-> next;     printf   ( "%d   ",p-> data);     p=GetNode(p);   }   printf( "%d\n ",p-> data);   return   0; }