洛谷P1162题：模拟算法解决约瑟夫环报数

一、题目解读

洛谷P1162题要求模拟一个报数游戏：有N个人围成一圈，从1开始依次报数，当报到包含数字7或7的倍数时，方向反转（即顺时针变为逆时针，或反之）。题目需要求解第X次报数的人编号。关键在于处理方向反转逻辑和循环报数的边界条件，确保每次报数后正确移动到下一个位置。

二、解题思路

采用循环模拟报数过程，结合判断数字是否包含7或是7的倍数。核心逻辑分为两部分：

1. 数字检查：通过自定义函数containsSeven()，对当前报数num进行双重判断——若num是7的倍数直接反转方向；若num本身不包含7，则分解各位数字检查是否有7（如17、27等）。

2. 方向反转与位置移动：利用方向变量direction（1为正方向，-1为反方向），每次检测到7相关数字时反转方向。移动当前人current时，需考虑边界条件（超过N或小于1时循环到另一端）。

三、解题步骤

1. 输入人数N和总报数次数X。

2. 初始化当前人current=1，方向direction=1（正向）。

3. 循环遍历1到X：

○ 检查当前数字num是否触发方向反转，调用containsSeven()判断。

○ 根据方向移动current：正向时加方向值，反向时减方向值。

○ 处理边界：若移动后current超出范围，利用取模运算循环到另一端（如current > N时重置为1）。

4. 输出最终位置current。

四、代码与注释

#include <iostream>  
using namespace std;  

// 检查数字是否包含7或是7的倍数  
bool containsSeven(int num) {  
    if (num % 7 == 0) return true; // 是7的倍数直接返回  
    while (num > 0) {  
        if (num % 10 == 7) return true; // 分解数字检查各位是否有7  
        num /= 10;  
    }  
    return false;  
}  

int main() {  
    int X;  
    cin >> X;  
    const int N = 1337; // 题目给定的N值  
    int current = 1; // 当前报数的人  
    int direction = 1; // 方向标记  

    for (int num = 1; num <= X; ++num) {  
       
        // 输出当前数字和对应的人(调试用)
        // cout << num << " " << current << endl;

        // 反转方向条件  
        if (containsSeven(num)) {  
            direction *= -1;  
        }  

        // 移动到下一个人（处理边界）  
        if (num < X) { // 最后一个数字无需移动  
            current += direction;  
            if (current > N) current = 1; // 超过N时循环到1  
            if (current < 1) current = N; // 小于1时循环到N  
        }  
    }  

    cout << current << endl;  
    return 0;  
}

五、总结

本解法通过分离数字检查与方向移动逻辑，实现了高效的报数模拟。关键在于：

● 使用位分解检查数字是否包含7，避免复杂计算。

● 利用方向变量简化移动逻辑，结合边界判断确保循环正确性。

● 时间复杂度为O(X)，适用于题目数据范围。

该思路可扩展至其他约瑟夫环报数问题，具有一定通用性。