【妙解】约瑟夫问题

题目描述

戳我
普通的约瑟夫问题。。
一般的解法就是开一个visit数组，记录是否出队，然后用一个p指针一遍一遍扫，扫到第m个人就踢出去，visit设为true，然后接着搞，，，知道搞到全部出队为止。代码也很好写

#include<cstdio>
bool visit[210];
int main() {
    int n, m, p = 0;
    scanf("%d%d", &n, &m);
    for (int k = 1; k <= n; k++) {
        for (int i = n; i < m; i++) {
            if (++p > n) p = 1;
            if (visit[p]) i--;
        }
        printf("%d ", p);
        visit[p] = true;
    }
    return 0;
}

标题说了妙解，我就来讲讲另外一种做法，就是设立一个next数组，每个元素的next都是这个元素的后继（也就是下一个报数的人），每次报数就将p=next[p]$p=next[p]$,记住，只能先报到m-1为止，然后让p的后继出队，方式就是next[p]=next[next[p]]$next[p]=next[next[p]]$，这有点难理解，画个图就明白了。

这样看就明白了，就相当于跳过了next[p]，如果原本数了m个，由于没有记录前驱节点，相当于把指针丢掉了的。。。

#include<cstdio>
int next[210];
int main() {
    int n, m, p = 0;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) next[i] = i + 1; next[n] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++)
            p = next[p];
        printf("%d ", next[p]);
        next[p] = next[next[p]];
    }
    return 0;
}

这个是数组模拟链表的写法。再来个惊世骇俗的(链表，还原它的本相)。。

#include<cstdio>
struct link {
    int value;
    link* next;
};
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    link *p = new link;
    link *temp = p;
    temp->next = new link;
    temp = temp->next;
    temp->value = 1;
    link *rhs = temp;
    for (int i = 1; i < n; i++) {
        temp->next = new link;
        temp = temp->next;
        temp->value = i + 1;
    }
    temp->next = rhs;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++)
            p = p->next;
        printf("%d ", p->next->value);
        p->next = p->next->next;
    }
    return 0;
}

还原了本相，但是写起来有点烦，还是让推荐数组模拟链表吧。