约瑟夫问题

一、数组解法

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

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int a[n+1], visit[n+1];
    int count = 0, curIdx = 0, num = 0;

    for (int i = 1; i <= n; i++) {
        a[i] = i;
        visit[i] = 1;
    }
    while (count < n - 1) {
        for (int i = 1; i <= n; i++) {
            if (visit[i]) {
                num++;
                if (num == m) {
                    printf("%d ", i);
                    count++;
                    visit[i] = 0;
                    num = 0;
                }
                if (count == n - 1) break;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (visit[i] == 1) {
            printf("\nThe last one is : %d\n", a[i]);
            break;
        }
    }

    return 0;
}

二、循环队列

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = 1;
        int n = sc.nextInt(), m = sc.nextInt();
        Deque<Integer> queue = new ArrayDeque<Integer>();

        for (int i = 1; i <= n; i++) queue.offer(i);

        while (!queue.isEmpty()) {
            if (cnt == m) {
                System.out.print(queue.poll() + " ");
                cnt = 1;
            } else {
                int temp = queue.poll();
                queue.offer(temp);
                cnt++;
            }
        }
        System.out.println();
    }
}

三、数学解法

#include <stdio.h>
int main() {
    int n, m, i, s = 0;
    printf ("N M = ");
    scanf("%d%d", &n, &m);
    for (i = 2; i <= n; i++) {
        s = (s + m) % i;
    }
    printf ("The winner is %d\n", s+1);
}