约瑟夫问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。

        人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，执行下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。

        问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

        历史:

        这个问题是以弗拉维奥·约瑟夫命名的，它是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个.

// VS2017 C++ 编译通过， Designed by DGS-SK, Nov. 23, 2024
#include <stdio.h>
#include <string.h>
#include "pch.h"
#include <iostream>
using namespace std;

int Joseph(int n, int m)
{
	if (n <= 0 || m <= 0) return -1;
	int *arr = new int[n];
	if (n == 1)
	{
		return 0;
	}
	if (m == 1)
	{
		return n-1;
	}

	for (int i = 0; i < n; i++)
	{
		arr[i] = i;
	}

	int scnt = n;  // survial count
	int k = m % scnt;
	int startindex = 0;
	int killindex = 0;
	while (true)
	{
		if (scnt == 1) return arr[0];
		k = m % scnt;
		if (startindex + k > scnt)
		{
			killindex = (startindex + k) % scnt - 1;
		}
		else
		{
			killindex = (startindex + k - 1);
		}

		if (killindex == scnt - 1)
		{
			startindex = 0;
			scnt--;
		}
		else
		{
			for (int i = killindex; i < (scnt - 1); i++)
			{
				arr[killindex] = arr[killindex + 1];
			}
			scnt--;
			startindex = killindex;
		}
	}




}

int main(void)
{
	int n, m;
	int survival;
start:
	printf("Please input Joseph problem's N and M: ");
	scanf_s("%d, %d", &n, &m);
	if (n <= 0 || m <= 0)
		goto exit1;
	survival = Joseph(n, m);
	printf("N = %d, M = %d\n", n, m);
	printf("The survival people is No. %d \n\n", survival);

	goto start;

exit1:
	printf("The End");
	return 0;
}