初级算法 – 约瑟夫圆环 | 高性能架构探索

很著名的一个问题。

简单描述，n个人坐成一圈，然后按k的顺序将人剔除，直到剩下最后一个人。

我的思路就是将n个人标志为0，按k的顺序剔除的人改为标志1。代码如下：

#include <iostream>

int main()
{
    int total, n,i = 0,k=0,count = 0,count_ = 0;    
    std::cout << "输入总人数：";
    std::cin >> total;
    std::cout << "输入你想要循环的数：";
    std::cin >> n;
    int* nums = new int[total];
    memset(nums, 0, sizeof(int) * total);

    while(1)
    {
        for (i=0; i < total; i++)
        {
            if (!nums[i])
            {
                count_++;
            }
            if (count_ > 1)
            {
                count_ = 0;
                break;
            }
        }
        if (count_ == 1)
        {
            break;
        }
        while (count != n)
        {
            if (!nums[k])
            {
                count++;
            }
            ++k;
            if (k == total)
            {
                k = 0;
            }
        }
        k -= 1;
        if (k < 0)
        {
            nums[total-1] = 1;
            k = 0;
        }
        else
        {
            nums[k] = 1;
        }        
        count = 0;        
    }

    for (i=0; i < total; i++)
    {
        if (!nums[i])
        {
            std::cout << "最后剩下的人标号：" << i << std::endl;
        }
    }

    delete nums;
    return 0;
}

标号是从数组下标0开始的，而不是从下标1开始的。

代码可能看的不是很舒服，这也只是我暂时想到的。更多的方法可以自行百度。

注意：使用memset初始化int数组为1时，会出现问题。所以我初始化为0了。

原文链接: https://www.cnblogs.com/strive-sun/p/14426957.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/404688

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

初级算法 – 约瑟夫圆环

相关推荐