约瑟夫问题

队列实现

#include <stdio.h>
#include <queue>
using namespace std;
//队列实现 
queue<int> q;
int n, m, cnt, out, a[101]; //a[i]=0表示在圈里 
int main()
{
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++){
		q.push(i);
	}
	while(!q.empty()){
		cnt++;
		if(cnt==m){
			cnt=0;
			printf("%d ", q.front());
			q.pop();
		}
		else{
			q.push(q.front());
			q.pop();
		}
	}
	return 0;
}

#include <bits/stdc++.h>//万能头文件   
//动态链表 
//动态链表需要临时分配链表节点,使用完毕后释放链表节点。
//动态链表的优点是能及时释放空间,不使用多余内存﹔缺点是需要管理空间,容易出错。
//动态链表是“教科书式”的标准做法。
/*
定义链表节点 
data  节点的值
next  单向链表指针 
*/ 
struct node{
	int data;
	node *next;
}; 
 
int main(){
 int n,m;
 scanf("%d%d",&n,&m);
 node *head,*p,*now,*r;//定义变量
 //分配第1个节点，数据设置为1 
 head = new node;head->data=1;head->next=NULL;
 now = head; //设置当前指针为头指针
 for(int i=2;i<=n;i++){
 	p=new node;p->data=i;p->next=NULL;//p是新节点
	now ->next=p;//把申请的新节点连到前面的链表上 
	now = p;//尾指针后移一个 
 } 
 now->next=head;//尾指针指向头，循环链表建立完成
 now = head;r=head;//从第1个开始数
 while((n--)>1) {
 	for(int i=1;i<m;i++)
 	{
 		r=now;//数到m，停下 
 		now=now->next;//记录上一个位置，用于下面跳过第m个节点 
	 }
	 printf("%d ",now->data);//输出第m个节点,带空格
	 r->next=now->next;//跳过这个节点
	 delete now;//释放节点
	 now=r->next;//新的一轮 
 }
  printf("%d",now->data);//打印最后一个节点，后面不带空格
  delete now;//释放最后一个节点 
  return 0; 
 }

双向链表参考题解

#include <iostream>   
// 双向链表节点  
struct Node {  
    int data;  
    Node* prev;  
    Node* next;  
   
    Node(int d) : data(d), prev(nullptr), next(nullptr) {}  
};  
   
// 约瑟夫问题求解函数  
void josephus(int n, int m) {  
    if (n < 1 || m < 1) {  
        //std::cerr << "输入错误!" << std::endl;  
        return;  
    }  
   
    // 创建一个虚拟头节点来简化操作  
    Node* dummyHead = new Node(0);  
    Node* current = dummyHead;  
    Node* prev = dummyHead;  
   
    // 创建双向链表  
    for (int i = 1; i <= n; ++i) {  
        current->next = new Node(i);  
        current->next->prev = current;  
        current = current->next;  
    }  
    // 闭合链表  
    current->next = dummyHead->next;  
    dummyHead->next->prev = current;  
    current = dummyHead->next; // 跳过虚拟头节点  
   
    // 约瑟夫问题求解过程  
    while (current != current->next) { // 当链表中还有多于一个节点时  
        // 报数到m-1  
        for (int count = 1; count < m; ++count) {  
            prev = current;  
            current = current->next;  
        }  
        // 输出出圈人的编号  
        std::cout << current->data << " ";  
        // 移除当前节点  
        prev->next = current->next;  
        current->next->prev = prev;  
        // 释放当前节点内存  
        Node* toDelete = current;  
        current = current->next;  
        delete toDelete;  
    }  
    // 输出最后一个出圈人的编号  
    std::cout <<  current->data << std::endl;  
    // 释放最后一个节点内存  
    delete current;  
   
    // 不需要再保留虚拟头节点  
    delete dummyHead;  
}  
   
int main() {  
    int n, m;   
    std::cin >> n >> m;    
    josephus(n, m);   
    return 0;  
}

一维数组

/* 
 使用一维数组实现单向静态链表的解法
 这是最简单的实现方法。
*/ 
#include<bits/stdc++.h>
using namespace std;
int n,m,arr[110]; 
int main(){
	scanf("%d%d",&n,&m);
	int i=1;
	int cnt=0;
	int t=1;
	while(n>cnt){
	 	if(i>n) i=1;
	 	if(arr[i]==0)
	 	{
	 		if(t==m){
	 			arr[i]=1;
	 			cnt++;
	 			printf("%d ",i);
	 			t=0;
			 }
			 t++;
		 } 
		 i++; 
	} 
    return 0;
}

STL

/* 
在算法竞赛或工程项目中常常使用 C++STL list。
list 是双向链表,由标准模板库Standard Template Library,STL)
管理通过指针访问节点数据高效率地删除和插入。 
*/ 
#include <bits/stdc++.h> 
using namespace std;
int main()
{
	int n,m;
	list<int> node;
	scanf("%d%d",&n,&m);
	//nodes[i]的值就是下一个节点 
	for(int i=1;i<=n;++i) node.push_back(i);//建立链表
	list<int>::iterator it=node.begin();
	while(node.size()>1){//list的大小由STL自己管理 
		for(int i=1;i<m;++i){//数到m 
			it++;
			if(it==node.end()) //循环到末尾后再回头 
				it=node.begin();
		}
		printf("%d ",*it);
		list<int>::iterator next=++it;
		if(next==node.end()) next=node.begin();//循环链表
		node.erase(--it);//删除节点，node.size()自动减1
		it=next; 
	} 
 	printf("%d",*it);
	return 0;
}