• ♦  Josephu 问题,...
• ♦  算法和数据结构
• ♦  数据结构与算法基本程序...
• ♦  [算法] 进制转换 数...

    更多相关推荐...

  JosePhu问题是这样说的:

   Josephu  问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列
   既然如此,定义一个无头的循环链表可以轻松解决此问题!
   首先,定义数据结构 包含序号和一个指针  (PS:这类的我就不说了,反正看数据结构肯定知道链表的结构)
创建有n个节点的链表,然后把链表节点标示的数字设置为1 2 3 ... n 然后从k个节点开始,从1数起,一直数到为m的时候,打印出来这个序号,然后从链表中删除,然后继续下一个节点从1计数 一直到链表为空
 下面是实现的代码

/***********************************************************
************************************************************
************************************************************/

[code]
1 #include "iostream.h" 
2 #include "windows.h" 
3 typedef struct Josephu 
4 { 
5     int num; 
6     Josephu *pNext; 
7 }Jose,*pLink; 
8 
9 pLink CreateRing(int n);        //建立循环链表 
10 pLink DelLink(pLink pDel);        //删除节点 
11 void JosePhuToDel(pLink pJose,int num,int step,int k);        //解决JosePhu问题 
12 void main() 
13 { 
14     int num,step,k; 
15     pLink pJose; 
16     cout＜＜"请输入全部人数: "; 
17     cin＞＞num; 
18     if(num＜0) 
19         num=-num;            //确保为正数 
20     cout＜＜"请输入报数人序号: "; 
21     cin＞＞k; 
22     if(k＜0) 
23         k=-k;     
24     cout＜＜"请输入序号为几出列: "; 
25     cin＞＞step; 
26     if(step＜0) 
27         step=-step; 
28 
29     pJose=CreateRing(num); 
30     JosePhuToDel(pJose,num,step,k); 
31 } 
32 
33 pLink CreateRing(int n) 
34 { 
35     pLink pHead=NULL; 
36     pLink pTail=NULL; 
37     for(int i=0;i＜n;i++) 
38     { 
39         if(0==i)            //创建第一个节点 
40         { 
41             pTail=new Jose; 
42             pHead=pTail; 
43         } 
44         else 
45         { 
46             pTail-＞pNext=new Jose;         
47             pTail=pTail-＞pNext; 
48         } 
49         pTail-＞num=i+1;            //初始化 
50         pTail-＞pNext=NULL; 
51     } 
52     pTail-＞pNext=pHead;            //最后围成循环链表 
53     return pHead;     
54 } 
55 
56 pLink DelLink(pLink pDel) 
57 { 
58     pLink sTemp; 
59     sTemp=pDel; 
60     while(pDel-＞pNext!=sTemp) 
61     { 
62     pDel=pDel-＞pNext;            //找到节点 
63     } 
64     pDel-＞pNext=sTemp-＞pNext; 
65     delete sTemp;        //删除 
66     return pDel-＞pNext;            //返回下一个 
67 } 
68 
69 void JosePhuToDel(pLink pJose,int num,int step,int k) 
70 { 
71     int i,j; 
72     cout＜＜"出列序号是: "; 
73     for(i=1;i＜k;i++)                    //从第一个开始找 
74         pJose=pJose-＞pNext;                //找出报数的那个 
75     for(i=0;i＜num;i++) 
76     { 
77         for(j=1;j＜step;j++) 
78             pJose=pJose-＞pNext;            //找到出列的那个人 
79         cout＜＜pJose-＞num＜＜" ";            //打印出来后 
80         pJose=DelLink(pJose);            //该序号出列 
81     } 
82     cout＜＜endl; 
83 } 
84 [/code]


Remark :
  num表示全部人的数目 step表示数到那个数字,也就是m,k表示从k个人开始数数
[align=right][color=#000066][此贴子已经被作者于2008-8-29 18:09:11编辑过][/color][/align]

 先粘到Word，在粘到VC++新建的C++ Sourse File下即可：
#include <iostream.h> 
 #include <windows.h>
 typedef struct Josephu 
 { 
     int num;
     Josephu *pNext; 
 }Jose,*pLink;
 
 pLink CreateRing(int n);        //建立循环链表 
 pLink DelLink(pLink pDel);        //删除节点 
 void JosePhuToDel(pLink pJose,int num,int step,int k);        //解决JosePhu问题 
 void main() 
 { 
     int num,step,k; 
     pLink pJose; 
     cout<<"请输入全部人数: "; 
     cin>>num; 
     if(num<0) 
         num=-num;            //确保为正数 
     cout<<"请输入报数人序号: "; 
     cin>>k; 
     if(k<0) 
         k=-k;     
     cout<<"请输入序号为几出列: "; 
     cin>>step; 
     if(step<0) 
         step=-step; 
 
     pJose=CreateRing(num); 
     JosePhuToDel(pJose,num,step,k); 
 } 
 
 pLink CreateRing(int n) 
 { 
     pLink pHead=NULL; 
     pLink pTail=NULL; 
     for(int i=0;i<n;i++) 
     { 
         if(0==i)            //创建第一个节点 
         { 
             pTail=new Jose; 
             pHead=pTail; 
         } 
         else 
         { 
             pTail->pNext=new Jose;         
             pTail=pTail->pNext; 
         } 
         pTail->num=i+1;            //初始化 
         pTail->pNext=NULL; 
     } 
     pTail->pNext=pHead;            //最后围成循环链表 
     return pHead;     
 } 
 
 pLink DelLink(pLink pDel) 
 { 
     pLink sTemp; 
     sTemp=pDel; 
     while(pDel->pNext!=sTemp) 
     { 
     pDel=pDel->pNext;            //找到节点 
     } 
     pDel->pNext=sTemp->pNext; 
     delete sTemp;        //删除 
     return pDel->pNext;            //返回下一个 
 } 
 
 void JosePhuToDel(pLink pJose,int num,int step,int k) 
 { 
     int i,j; 
     cout<<"出列序号是: "; 
     for(i=1;i<k;i++)                    //从第一个开始找 
         pJose=pJose->pNext;                //找出报数的那个 
     for(i=0;i<num;i++) 
     { 
         for(j=1;j<step;j++) 
             pJose=pJose->pNext;            //找到出列的那个人 
         cout<<pJose->num<<" ";            //打印出来后 
         pJose=DelLink(pJose);            //该序号出列 
     } 
     cout<<endl; 
 }