约瑟夫环问题.md

约瑟夫环问题

@[toc]

一、C语言实现

Slist.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLDataType;
typedef struct SLNode
{
	SLDataType value;
	struct SLNode *next;
}SLNode;
typedef struct
{
	SLNode *first;
}SList;

//初始化
void SListInit(SList *list);

//创建节点
SLNode *SListBuyNode(SLDataType value);

//头插
void SListPushFront(SList *list, SLDataType value);

//尾插
void SListPushBack(SList *list, SLDataType value);

//打印
void SListPrint(const SList *list);

//在pos后面插入value
void SListInsertAfter(SLNode *pos, SLDataType value);

//去找到链表中遇到的第一个 value，如果没找到，返回NULL
SLNode * SListFind(const SList *list, SLDataType value);

//在pos前面插入value
void SListInsertBefore(SLNode *list, SLNode *pos, SLDataType value);

//头删
void SListPopFront(SList *list);

//尾删
void SListPopBack(SList *list);

//销毁
void SlistDestory(SList *list);

//删除 pos 后面的 value
void SListEraseAfter(SLNode *pos);

Slist.c

#include"Slist.h"

//初始化
void SListInit(SList *list)
{
	assert(list != NULL);
	list->first = NULL;
}

//创建节点
SLNode *SListBuyNode(SLDataType value)
{
	SLNode *node = (SLNode*)malloc(sizeof(SLNode));
	assert(node != NULL);
	node->value = value;
	node->next = NULL;
	return node;
}

//头插
void SListPushFront(SList *list, SLDataType value)
{
	assert(list != NULL);
	SLNode *node = SListBuyNode(value);
	assert(node != NULL);
	node->next = list->first;
	list->first = node;
}

//尾插
void SListPushBack(SList *list, SLDataType value)
{
	assert(list != NULL);

	if (list->first == NULL)
	{
		SListPushFront(list, value);
		return;
	}
	SLNode *cur = list->first;
	while (cur->next)
	{
		cur = cur->next;
	}
	SLNode *node = SListBuyNode(value);
	cur->next = node;
	node->next = NULL;
}

//打印
void SListPrint(const SList *list)
{
	assert(list != NULL);
	SLNode *cur = list->first;
	for (cur = list->first;cur;cur = cur->next)
	{
		printf("%d->", cur->value);
	}
	printf("NULL\n");
}

//在pos后面插入value
void SListInsertAfter(SLNode *pos, SLDataType value)
{
	assert(pos != NULL);
	SLNode *node = SListBuyNode(value);
	node->next = pos->next;
	pos->next = node;
}

//去找到链表中遇到的第一个 value，如果没找到，返回NULL
SLNode * SListFind(const SList *list, SLDataType value)
{
	assert(list != NULL);
	SLNode *cur;
	for (cur = list->first;cur;cur = cur->next)
	{
		if (cur->value == value)
		{
			return cur;
		}
	}
	return NULL;
}

//在pos前面插入value
void SListInsertBefore(SList *list, SLNode *pos, SLDataType value)
{
	assert(pos != NULL);
	assert(list != NULL);
	SLNode *node = SListBuyNode(value);
	SLNode *cur = list->first;
	while (cur->next != pos)
	{
		cur = cur->next;
	}

	cur->next = node;
	node->next = pos;
}

//头删
void SListPopFront(SList *list)
{
	assert(list != NULL);
	assert(list->first != NULL);
	SLNode *old_first = list->first;
	list->first = list->first->next;
	free(old_first);
}

//尾删
void SListPopBack(SList *list)
{
	assert(list != NULL);
	SLNode *cur = list->first;
	while (cur->next->next != NULL)
	{
		cur = cur->next;
	}
	free(cur->next);
	cur->next = NULL;
}

//销毁
void SlistDestory(SList *list)
{
	assert(list != NULL);
	SLNode *cur = list->first;
	SLNode *right;
	while (cur != NULL)
	{
		right = cur->next;
		free(cur);
		cur = right;
	}
	list->first = NULL;
}

//删除 pos 后面的 value
void SListEraseAfter(SLNode *pos)
{
	SLNode *next = pos->next;
	pos->next = next->next;
	free(next);
}

main()

int main()
{
	SLNode *last;
	SList *head;
	SLNode *cur;
	SListInit(&head);
	int m = 10;
	int n = 3;
	SListPushFront(&head, m);
	last = head;
	for (int i = m - 1;i >= 1;i--)
	{
		SListPushFront(&head, i);
	}
	SListPrint(&head);
	last->next = head;
	cur = last;
	for (;m > 1;m--)
	{
		for (int i = 1;i < n;i++)
		{
			cur = cur->next;
			printf("%d报%d\n", cur->value, i);
			
		}
		printf("%d号出圈\n", cur->next ->value);
		SListEraseAfter(cur);
	}
	printf("%d号胜利", cur->value);
	return 0;
}

二、C++实现

class Solution {
public:
    vector<int> Joseph_circle(vector<int>& people, int k) {
        vector<int> ret;
        if(people.empty())
        {
            return ret;
        }

        list<int> analog_loop(people.begin(),people.end());         
        auto current = analog_loop.begin();
        while(analog_loop.size() > 1)
        {
            // 将current移动到k的位置,注意current指针只需要移动k - 1次
            for(int i = 1; i < k; ++i)
            { 
                current++;

                // 到达链尾部
                if(current == analog_loop.end())  
                    // 重新指向链表开头,用list模拟出环形链表
                    current = analog_loop.begin();
            }

            //保存k的下一个节点
            auto cur_next = ++current;
            // 到达链尾部 
            if(cur_next == analog_loop.end())
                // 重新指向链表开头,用list模拟出环形链表
                cur_next = analog_loop.begin();
            
            //回到带删除节点
            --current;
            ret.push_back(*current);
            //删除第k个节点
            analog_loop.erase(current);
            current = cur_next;
        }
        ret.push_back(*current);
        return ret;
    }
};

三、牛客例题

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        list<int> Joseph_circle;
        for(int i = 1;i <= n;i++)
        {
            Joseph_circle.push_back(i);
        }
        
        auto cur = Joseph_circle.begin();
        while(Joseph_circle.size() > 1)
        {
            for(int i = 1;i < m;i++)
            {
                cur++;
                if(cur == Joseph_circle.end())
                {
                    cur = Joseph_circle.begin();
                }
            }
            
            auto next_Joseph_circle = ++cur;
            if(next_Joseph_circle == Joseph_circle.end())
            {
                next_Joseph_circle = Joseph_circle.begin();
            }
            
            --cur;
            Joseph_circle.erase(cur);
            cur = next_Joseph_circle;
        }
        cout<<*cur<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        int last = 0;
        for(int i = 2;i <= n;i++)
        {
            last = (last + m) % i;
        }
        cout<<last + 1<<endl;
    }
    return 0;
}