<約瑟夫問題>
1.問題簡述
約瑟夫問題也叫做約瑟夫環，是一個數學應用問題，
已知有n個人（分別編號為1，2，3…n）圍坐成一圈，從第一個人開始報數，報到數m的人出圈；再從下一個人開始重新報數，報到m的人出圈；直至剩下最后一個人的時候游戲結束，輸出剩下的人的原始編號，
2.問題思考
我們要解決的問題：
- 報到m的人出圈，如何表示出圈？
- 解決了表示出圈，那如何出圈呢？是采用其他標號前移保證陣列的連續，還是采用設定狀態標志的方法呢？
- 陣列是線性的，怎么將其連成一個圈？
3.兩種可選擇的實作方式
方式一：
方法： 首先找到每輪報數中應該出圈人（報到m的人）的位置，出圈一人后，依次將后面的標號前移，以此回圈，直至剩下最后一人，
注意： 每個人原始編號的記錄、出圈人在陣列中的位置的尋找、移動后面的人…
具體代碼如下：
#include <stdio.h>
#define N 100
int main()
{
int n,m=3,s=1;//n:總人數，m:報數值，s報數人的起始編號
scanf("%d",&n);
int a[N] = {0};//陣列初始化
int i,j;
for(i = 0; i < n; i++)//陣列遍歷
{
a[i] = i+1; //i是陣列的位置量，a[i]是每個人的原始編號（從1開始）
}
i=s-1; //陣列的起點（0）
while (n > 1)
{
i = (i+m-1) % n; //出圈的人在陣列中的位置
for(j = i+1; j < n; j++)
{
a[j-1] = a[j];
}
n--; //出局1人后，總人數-1
if(i == n) //終點后，開始起點（圍成一個圈）
{
i = 0;
}
}
printf("%d\n", a[i]);//輸出留下的人的原始編號
return 0;
}方式二：
方法： 設定一個報數的量count，每有一人出圈后將count置為0，將每次出圈的人不參與之后的報數，然后出圈人的下一個人從1開始繼續報數；
注意： 因為每出圈一個人后總人數要-1，為防止原始資料n被破壞，用了一個x來代替n進行變化，輸出原始編號的時候，只要找到陣列中誰不是0就好了~
ps：方法一也可以采用count報數的方法來找出圈人的位置噢~
具體代碼如下：
#include <stdio.h>
#define N 50
int main()
{
int a[N], m, n, x, i, count = 0;
printf("Please input n m:\n");
scanf("%d %d", &n, &m); //輸入總人數n和出局要報的數m
x = n; //把n賦給x，防止使用時n被修改
for (i = 1; i <= n; i++) //陣列遍歷，此時在陣列中的位置就是人原來的編號
{
a[i] = i;
}
while(x>1)
{
for (i = 1; i <= n; i++)
{
if (a[i] != 0) //判斷是否出圈，已經出局的就不用報數了
{
count++; //報數
}
if (count == m)
{
a[i] = 0; //出圈的人置為0，而后不參與報數
count = 0;
x--; //出圈一個，總人數減1
}
}
} //回圈結束后，出圈的人都已經被置為0，留下唯一一個人
for (i = 1; i <= n; i++)
if(a[i]!=0)
printf("%d ",i); //輸出留下的人的原始編號
return 0;
}TIP:約瑟夫問題還可以采用 遞回 和 鏈表 的方式解決，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252040.html
標籤：其他
上一篇：入門三個月不到的小白寫的掃雷