约瑟夫问题（c/c++解决）

淩亂°似流年 2023-05-28 06:52 10阅读 0赞

**问题描述：**  
设有n个人围坐在圆桌周围，现从某个位置m(1≤m≤n)上的人开始报数，报数到k的人就站出来。下一个人，即原来的第k+1个位置上的人，又从1开始报数，再报数到k的人站出来。依次重复下去，直到全部的人都站出来为止。试设计一个程序求出这n个人的出列顺序。

#include<iostream>
    using namespace std;
    typedef struct Lnode
    {
        
    	int data;
    	struct Lnode *next;
    }Lnode, *Linklist;  //循环链表结点类型定义
    					//创建循环链表
    Linklist Initlist(Linklist L, int n)
    {
        
    	Linklist q;
    	q = L;
    	L->data = 1;
    	for (int i = 2; i <= n; i++)
    	{
        
    		Linklist p;
    		p = (Lnode*)malloc(sizeof(Lnode));
    		p->data = i;
    		p->next = NULL;
    		q->next = p;
    		q = p;
    	}
    	while (q->next == NULL)
    	{
        
    		q->next = L;
    	}
    	return L;
    }
    //删除报数为k的结点
    Linklist Deletelist(Linklist L, int m, int k, int n, int w)
    {
        
    	Linklist p, q;
    	p = q = L;
    	if (m == 1)
    	{
        
    		if (n == w);
    		else
    		{
        
    			for (int i = 0; i < k-m; i++)
    			{
        
    				p = p->next;
    			}
    		}
    	}
    	else
    	{
        
    		for (int i = m; i < m + k - 1; i++)
    		{
        
    			p = p->next;
    		}
    	}
    	q = p->next;
    	p->next = q->next;
    	q->next = NULL;
    	free(q);
    	L = p;
    	return L;
    }
    //获取报数为k的序号
    int Getnumlist(Linklist L, int m, int k, int n,int w)
    {
        
    	Linklist p;
    	p = L;
    	if (m == 1)
    	{
        
    		if (n == w)	
    			for (int i = 0; i < k - m; i++)
    			{
        
                    p = p->next;
    			}
    				
    		else
    			for (int i = 0; i < k - m + 1; i++)
    			{
        
    				p = p->next;
    			}
    	}
    	else
    	{
        
    		for (int i = m; i < m + k; i++)
    		{
        
    			p = p->next;
    		}
    	}
    	return p->data;
    }
    int main()
    {
        
    	int n,m,k;
    	cout << "有__个人围坐在圆桌周围,请输入:";
    	cin >> n;
    	cout << "从某个位置__上的人开始报数,请输入:";
    	cin >> m;
    	cout << "报数到__的人就站出来,请输入:";
    	cin >> k;
    	int num, *a, i = 0,w;
    	w = n;
    	Linklist L;
    	L = (Lnode*)malloc(sizeof(Lnode));
    	L = Initlist(L, n);
    	a = (int*)malloc(sizeof(int)*n);
    	while (n != 0)
    	{
        
    		num = Getnumlist(L, m, k,n,w);
    		a[i++] = num;
    		L = Deletelist(L, m, k,n,w);
    		n--;
    	}
    	cout << "这" << w << "人的出列顺序为：";
    	for (int i = 0; i < w; i++)
    	{
        
    		cout << a[i] << " ";
    	}
    	cout << endl;
    	return 0;
    }