詳解約瑟夫環成績及其相干的C說話算法完成。本站提示廣大學習愛好者：（詳解約瑟夫環成績及其相干的C說話算法完成）文章只能為提供參考，不一定能成為您想要的結果。以下是詳解約瑟夫環成績及其相干的C說話算法完成正文
約瑟夫環成績
N小我圍成一圈次序編號，從1號開端按1、2、3......次序報數，報p者加入圈外，其他的人再從1、2、3開端報數，報p的人再加入圈外，以此類推。
請按加入次序輸入每一個加入人的原序號
算法思惟
用數學歸結法遞推。
不管是用鏈表完成照樣用數組完成都有一個配合點：要模仿全部游戲進程，不只法式寫起來比擬煩，並且時光龐雜度高達O(nm)，若nm異常年夜，沒法在短時光內盤算出成果。我們留意到原成績僅僅是請求出最初的成功者的序號，而不是要讀者模仿全部進程。是以假如要尋求效力，就要打破慣例，實行一點數學戰略。
為了評論辯論便利，先把成績略微轉變一下，其實不影響原意：
成績描寫：n小我（編號0~(n-1))，從0開端報數，報到(m-1)的加入，剩下的人持續從0開端報數。求成功者的編號。
我們曉得第一小我(編號必定是m%n-1) 出列以後，剩下的n-1小我構成了一個新的約瑟夫環（以編號為k=m%n的人開端）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2而且從k開端報0。
如今我們把他們的編號做一下轉換：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
變換後就完完整全成了(n-1)小我報數的子成績，假設我們曉得這個子成績的解：例如x是終究的成功者，那末依據下面這個表把這個x變歸去不恰好就是n小我情形的解嗎？！！變歸去的公式很簡略，信任年夜家都可以推出來：x'=(x+k)%n
若何曉得(n-1)小我報數的成績的解？對，只需曉得(n-2)小我的解就好了。(n-2)小我的解呢？固然是先求(n-3)的情形——這明顯就是一個倒推成績！好了，思緒出來了，上面寫遞推公式：
令f[i]表現i小我玩游戲報m加入最初成功者的編號，最初的成果天然是f[n]
遞推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
完成辦法
1、輪回鏈表
樹立一個有N個元素的輪回鏈表，然後從鏈表頭開端遍歷並計數，假如基數i == m，則踢出該元素，持續輪回，直到以後元素與下一個元素雷同時加入輪回
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct lnode
{
int pos;
struct lnode *next;
} lnode;
/**
* 構建輪回鏈表&&輪回遍歷
*/
void create_ring(lnode **root, int loc, int n)
{
lnode *pre, *current, *new;
current = *root;
pre = NULL;
while (current != NULL) {
pre = current;
current = current->next;
}
new = (lnode *)malloc(sizeof(lnode));
new->pos = loc;
new->next = current;
if (pre == NULL) {
*root = new;
} else {
pre->next = new;
}
// 輪回鏈表
if (loc == n) {
new->next = *root;
}
}
/**
* 約瑟夫環
*/
void kickoff_ring(lnode *head, int p)
{
int i;
lnode *pre, *pcur;
pre = pcur = head;
while (pcur->next != pcur) {
for (i = 1; i < p; i ++) {
pre = pcur;
pcur = pcur->next;
}
printf("%d ", pcur->pos);
pre->next = pcur->next;
free(pcur);
pcur = pre->next;
}
printf("%d\n", pcur->pos);
free(pcur);
}
void print_ring(lnode *head)
{
lnode *cur;
cur = head;
while (cur->next != head) {
printf("%d ", cur->pos);
cur = cur->next;
}
printf("%d\n", cur->pos);
}
int main()
{
int i, p, n;
lnode *head;
while (scanf("%d %d", &n, &p) != EOF) {
// 構建輪回鏈表
for (i = 1, head = NULL; i <= n; i ++)
create_ring(&head, i, n);
// 約瑟夫環
if (p != 1)
kickoff_ring(head, p);
else
print_ring(head);
}
return 0;
}
/**************************************************************
Problem: 1188
User: wangzhengyi
Language: C
Result: Accepted
Time:110 ms
Memory:912 kb
****************************************************************/
2、數組模仿
思惟跟輪回鏈表相似，少了構建輪回鏈表的進程
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i, index, p, n, remain, delete[3001], flag[3001] = {0};
while (scanf("%d %d", &n, &p) != EOF) {
remain = n;
index = 0;
while (remain >= 1) {
for (i = 0; i < n; i ++) {
if (flag[i] == 0) {
// 報數
index ++;
// 報p者加入圈外
if (index == p) {
// 加入圈外
flag[i] = 1;
// 從新報數
index = 0;
delete[remain - 1] = i + 1;
remain --;
}
}
}
}
// 輸入每一個加入人的序號
for (i = n - 1; i >= 0; i --) {
if (i == 0) {
printf("%d\n", delete[i]);
} else {
printf("%d ", delete[i]);
}
}
}
return 0;
}
3、數學推導
#include <stdio.h>
int main(void)
{
int i, n, m, last;
while (scanf("%d", &n) != EOF && n != 0) {
// 吸收報數
scanf("%d", &m);
// 約瑟夫環成績
for (i = 2, last = 0; i <= n; i ++) {
last = (last + m) % i;
}
printf("%d\n", last + 1);
}
return 0;
}
