约瑟夫环系列问题

「爱情、让人受尽委屈。」 2022-05-10 10:40 114阅读 0赞

数据结构循环链表的应用

\*铁锤妹妹手中有A—K的黑桃牌13张，每次不看牌，数数：1翻过来刚好为A；1、2翻过来刚好为2；  
1、2、3翻过来刚好为3（不翻的牌放在手中这迭牌的最下面，翻开的牌翻开放在一侧）；……；  
1、……、13刚好为K。最后放在一旁的牌的顺序为1、2、3、4、5、……、J、Q、K。问：  
原先铁锤妹妹手中的牌的循序是怎样的？  
 \* 答案：1 8 2 5 10 3 12 11 9 4 7 6 13

#include <iostream>
    using namespace std;
    #define N 13
     
    typedef struct Node
    {
        int data;
        Node *next;
    }Node,*LinkList;
     
    void Init(LinkList &L, int n)        //初始化 
    {
        L = new Node;
        L->next = L;
        LinkList p;
        for(int j = 0; j < n; ++j)
        {
            p = new Node;
            p->data = 0;          
            p->next = L->next;    
            L->next = p;          
        }
    }
    
    
    void Get(LinkList &L, int n)
    {
        LinkList p = L->next;
        p->data = 1; 
        int num;                     
        for( num = 2; num <= n; ++num)  
        {
            int i = 0;
            while(i < num)    
            {
                p = p->next;
                if(p->data == 0) ++i;      //跳过已存在的牌的地方 
            }
            p->data = num;
        }
    }
     
    void Print(LinkList &L)
    {
        LinkList p = L->next;
        cout << "Print: ";
        while(p != L)
        {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }
     
    int main()
    {
        LinkList L;
        Init(L, N);
        Get(L, N);
        Print(L);
    }

一群小孩编号为1，2，…，n(n>0)围成一圈，有一个刚出锅的山芋在他们之间传递。假设刚开始由1号拿  
着山芋，然后依次计数把山芋交给下一个小孩，当数到某个特定的k时，拿着山芋的小孩退出游戏，然后从  
下一个小孩重新开始计数，如此不断，最后剩下的那个孩子就是幸运者。要求设计一个程序模拟次过程，  
并给出不同的n，k组合下那个幸运者是谁？  
1、输入的形式和输入值的范围：演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示  
信息”之后，由用户在键盘上输入相应的数据，每个人的序号由程序自动分配。以int型输入，范围在  
\-2147483648～2147483648；  
2、输出的形式：int型；  
3、程序所能达到的功能：构造链表；输入数据；执行报数；储存出列人的序号，删除出列人的信息以及把  
指向出列人的指针移到出列人的下一个人，然后重新开始执行报数；直到最后一个人报数完毕，程序结束。  
4、测试数据：n=9，9个人的序号分别为：1,2,3,4,5,6,7,8,9。然后b=1，从第一个开始报数。k=5，则  
确定输出的序列为：5,1,7,4,3,6,9,2,8。

# include <iostream>
    # include <string.h> 
    # include <cstring>
    # include <cstdlib>
    # include <cstdio>
     
    using namespace std;  
      
    typedef struct _Node  
    {  
        int data;  
        struct _Node*next;  
    } node_t;  
      
    typedef struct _Linklist  
    {  
        node_t*phead;  
        node_t*ptail;  
        int len;  
    }Linklist;  
    static node_t*GetNode(int i )//新建并初始化节点  
    {  
        node_t*pNode;  
        pNode=new node_t;  
        if(!pNode)  
        {  
            cout <<"内存分配失败" <<endl;  
            exit(-1);  
        }  
        pNode->data=i;  
        pNode->next=NULL;  
        return pNode;  
        delete pNode;  
    }  
    void init_list(Linklist*plist)//用第一个节点初始化循环单链表  
    {  
        node_t*p;  
        p=GetNode(1);   
        plist->phead=p;  
        plist->ptail=p;  
        p->next=plist->phead;  
        plist->len=1;  
    }  
      
    //把其余数据添加到循环单链表中  
    static void Create_List(Linklist*plist,int n)  
    {  
        int i=0;  
        node_t*pNew;  
        for(i=2;i<=n;i++)  
        {  
            pNew=GetNode(i);  
            plist->ptail->next=pNew;  
            plist->ptail=pNew;  
            pNew->next=plist->phead;  
            plist->len++;  
        }  
    }  
    //输出链表内容  
    
    void joseph(Linklist* plist,int m,int k)  
    {    
        node_t *pPre=plist->ptail;  
        node_t *pCur=plist->phead;  
        int i,j;  
    cout << "出队列的顺序依次为： "<< endl;  
        while(plist->len != 1)  
        {  
            i=0;  
            j=0;  
            while(j<k-1)  
            {  
                pPre=pPre->next;  
                j++;  
            }  
            while(i< m -1)  
            {  
                pPre=pPre->next;  
                i++;  
            }  
            pCur=pPre->next;  
            int temp=pCur->data;  
            cout <<"第 " << temp << "  个人 "<< endl ;  
            pPre->next=pCur->next;  
            free(pCur);  
            plist->len--;  
        }  
        cout <<"第 " << pPre->data << " 个人" << endl; ;  
        cout << "幸运者是:" << pPre->data<< endl;  
    }  
    int main(int argc, char * argv[])  
    {  
        int n=0;  
        cout <<"小孩个数 : "<<endl;  
        cin >> n;  
        int m=0;  
        cout << "每数到几时，此人出列？"<<endl;  
        int k;  
        cin >> k;  
        cout << "从第几个小孩开始数？" << endl;  
        cin >>m;  
        Linklist pList;  
        init_list(&pList);  
        Create_List(&pList,n);    
        joseph(&pList,m,k);  
        return 0;  
    }

/\*  
铁锤妹妹想到一个杀人游戏游戏规则如下：铁锤妹妹抓了n个人对这n个人进行编号，分别从1到n，  
排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，活到最后的一个人是胜利者。  
请输出每次被杀的人的编号注意最后一个活着的人不用输出  
输入  
多组测试数据，输入n和m值。1<n,m<200，EOF结束  
输出  
输出每次被杀的人的编号 注意 最后一个人不用输出  
\*/  
/\*//数组方法

#include<stdio.h>
    int main()
    {
        int n,m;
        while(scanf("%d %d",&n,&m)&&n!=0&&m!=0)
        {
            int i=0,j=0,a[205]= {0},t=0;
            while(1)
            {
                j++;
                if(a[j%n]==0)
                    i++;
                if(i==m)
                {
                    i=0;
                    a[j%n]=1;
                    t++;
                    if(j%n==0)
                        printf("%d\n",n);
                    else
                        printf("%d\n",j%n);
                }
                if(t==n)
                    break;
            }
        }
        return 0;
    }

\*/

循环链表

# include <iostream>
    # include <string.h> 
    # include <cstring>
    # include <cstdlib>
    # include <cstdio>
     
    using namespace std;  
      
    typedef struct _Node  
    {  
        int data;  
        struct _Node*next;  
    } node_t;  
      
    typedef struct _Linklist  
    {  
        node_t*phead;  
        node_t*ptail;  
        int len;  
    }Linklist;  
    static node_t*GetNode(int i )//新建并初始化节点  
    {  
        node_t*pNode;  
        pNode=new node_t;  
        if(!pNode)  
        {  
            cout <<"内存分配失败" <<endl;  
            exit(-1);  
        }  
        pNode->data=i;  
        pNode->next=NULL;  
        return pNode;  
        delete pNode;  
    }  
    void init_list(Linklist*plist)//用第一个节点初始化循环单链表  
    {  
        node_t*p;  
        p=GetNode(1);   
        plist->phead=p;  
        plist->ptail=p;  
        p->next=plist->phead;  
        plist->len=1;  
    }  
      
    //把其余数据添加到循环单链表中  
    static void Create_List(Linklist*plist,int n)  
    {  
        int i=0;  
        node_t*pNew;  
        for(i=2;i<=n;i++)  
        {  
            pNew=GetNode(i);  
            plist->ptail->next=pNew;  
            plist->ptail=pNew;  
            pNew->next=plist->phead;  
            plist->len++;  
        }  
    }  
    //输出链表内容  
    
    void joseph(Linklist* plist,int m,int k)  
    {    
        node_t *pPre=plist->ptail;  
        node_t *pCur=plist->phead;  
        int i,j;   
        while(plist->len != 1)  
        {  
            i=0;  
            j=0;  
            while(j<k-1)  
            {  
                pPre=pPre->next;  
                j++;  
            }  
            while(i< m -1)  
            {  
                pPre=pPre->next;  
                i++;  
            }  
            pCur=pPre->next;  
            int temp=pCur->data;  
            cout  << temp << endl ;  
            pPre->next=pCur->next;  
            free(pCur);  
            plist->len--;  
        }     
    }  
    int main(int argc, char * argv[])  
    {  
        int n,k,m=1;    
        cin >> n;   
        cin >> k;    
        Linklist pList;  
        init_list(&pList);  
        Create_List(&pList,n);    
        joseph(&pList,m,k);  
        return 0;  
    }