C++: Đếm trẻ nhận bóng sau mỗi lần ném

Bài toán: n trẻ đứng tròn, số 1..n theo chiều kim đồng hồ. Trẻ 1 ném cho 2, 2 ném cho 4 (bỏ qua 1), 4 ném cho 7 (bỏ qua 2),... Bước nhảy tăng 1 mỗi lần. Tìm dãy trẻ nhận bóng.

Thuật toán

Vị trí hiện tại p (0-index). Lần i (bắt đầu 1): p = (p + i) % n. Nếu p == 0 thì p = n. In p cho i = 1..n-1.

Code C++

#include <bits/stdc++.h>
using namespace std;

void solve(int n) {
    int p = 1; // 1-indexed
    for (int i = 1; i < n; i++) {
        p += i;
        p %= n;
        if (p == 0) p = n;
        cout << p << (i == n-1 ? "" : ", ");
    }
}

int main() {
    solve(10); // Output: 2, 4, 7, 1, 6, 2, 9, 7, 6
    return 0;
}

Kết quả

2, 4, 7, 1, 6, 2, 9, 7, 6