首页 > 其他分享 >约瑟夫生者死者游戏问题

约瑟夫生者死者游戏问题

时间:2024-11-08 12:19:32浏览次数:1  
标签:node head 游戏 victim next 链表 死者 约瑟夫 节点

C++使用单向循环链表解决
需要实现节点的插入和删除
——我为++做实事


1 、节点定义:

struct node
{
    int number; // 表示序号
    node *next;
};

2 、节点的插入:

为每个节点(人)发放生死序号:index
考虑链表为空和不为空的情况

void insert_Node(node *&head, int index)
{
    node *newNode = new node;
    // 如果链表为空
    if (head == nullptr)
    {
        newNode->number = index;
        newNode->next = newNode; // next指针指向自己
        head = newNode;          // 把自己设为头节点
    }
    else
    {
        newNode->number = index;
        newNode->next = head; // next指针指向头节点
        node *N = find_tail(head);
        N->next = newNode; // 尾节点的next指向自己
    }
}

3 、删除节点的操作:

当我们删除链表中的节点时,一般只需要修改附近节点的 next 指针即可,不过此题使用了 new 来分配空间,所以还需要 delete 掉节点,防止内存泄漏。如果用数组模拟链表就不用考虑真的“删除”节点这个问题。

3 .1 有以下几种情况:
如果是头节点
	是否有且只有头节点
	除了头节点还有其他节点
如果不是头节点
3.2 需要注意释放内存

delete node
代码:

void del_Node(node *&head, node *victim)
{
    if (victim == head) 			// 如果删除的是头节点
    {
        node *tail = find_tail(head);
        if (head == tail) 			// 链表只有一个节点
        {
            delete head;    		// 释放内存
            head = nullptr; 		// 设置为空
        }
        else						// 除了头节点还有其他节点
        {
            head = head->next; 		// 修改头节点
            tail->next = head; 		// 尾节点指向新的头节点
            delete victim;     		// 释放内存
        }
    }
    else							// 删的不是头节点
    {
        node *before_victim = head;
        while (before_victim->next != victim)
            before_victim = before_victim->next;
            
        before_victim->next = victim->next; // 删除 victim,修改前面节点的next指针
        delete victim;                      // 释放内存
    }
}

4. Main 函数

一定要初始化头节点为空,作为链表的一个标志
代码逻辑:
为 30 个人发号码牌
循环 15 次,每次丢出去一个人(好残忍)
每次从当前的人这里,往前走 8 步,找到 victim
删除 victim
指针移动到这个 victim 下一位,下次循环就从这人开始,继续走 8 步……
代码:

int main()
{
    node *head = nullptr;			// 一定要初始化头节点为空
    for (int i = 1; i <= 30; i++)
        insert_Node(head, i);

    int all_people = 30, half_people = all_people / 2;
    node *victim = head;
    while (half_people--)
    {
        for (int i = 0; i < 8; i++)
            victim = victim->next;

        cout << victim->number << " ";
        node *next_vic = victim->next;
        del_Node(head, victim);
        victim = next_vic;

        cout << endl;
        // print(head);
    }
    return 0;
}

最后是些无关紧要的辅助函数

1、find_tail 函数

// 返回链表最后一个节点的指针
node *find_tail(node *head)
{
    node *N = head;
    while (N->next != head) // find尾节点
    {
        N = N->next;
    }
    return N;
}

2、打印链表函数(debug 用可删)

// 打印当前剩下的所有人
void print(node *head)
{
    node *c = head;
    if (c == nullptr)
        return; // 空链表处理
    do
    {
        cout << c->number << " ";
        c = c->next;
    } while (c != head); // 打印直到头节点
    cout << endl;
}

小韩碎碎念 —有些 bug 值得注意:

1、对于链表的修改,包括插入和删除,传进函数一定要用 &,引用传递,否则只会在函数内部修改,不会对原始链表有任何影响。

2、关于 while 和 do-while 的一个 bug:
源代码:

void print(node * head)
{
    node *c = head;
    while(c->next != head)
    cout << c->number << " ";
}

问题:
print 函数的逻辑问题print 函数缺少打印链表最后一个节点的代码,因为它只循环到 c->next != head,而没有打印尾节点。因此,你会错过打印最后一个节点
改成 do-while 循环后的代码:

void print(node * head) 
{ 
	node *c = head; 
	if (c == nullptr) 
		return; // 空链表处理 
	do 
	{ 
		cout << c->number << " "; 
		c = c->next; 
	} while (c != head); // 打印直到头节点 
	cout << endl; 
}

标签:node,head,游戏,victim,next,链表,死者,约瑟夫,节点
From: https://www.cnblogs.com/yuxiyuxi/p/18534827

相关文章

  • 11月7日 NOIP模拟(难题math、矩阵游戏matrix、括号序列seq、道路road) - 模拟赛记录
    PrefaceT1试图找规律失败,正经推反而几分钟就出来了。以后应该少想这些歪门邪道(除非实在闲的蛋疼或者没有一点头绪,且必须要打完所有能打的子任务比如暴力或特殊性质;而且必须在用常规方法思考过后,才能够用一些稍微不那么常规的方法)至于T2、T3、T4,因为知道T1浪费了太多时间,都是......
  • 使用python中的pygame简单实现飞机大战游戏
    前言在这个教程中,我们将使用Python的Pygame库来开发一个简单的飞机大战游戏。Pygame是一个开源的Python库,用于编写视频游戏。它包括计算机图形和声音库,设计目的是为游戏开发者提供一个简单易用的接口。一、环境准备在开始编码之前,请确保已经安装了Python和Pyga......
  • 《地下城与勇士:同人单机版》游戏 —— 经典重现,单人冒险新体验
     引言《地下城与勇士》作为一款经典的多人在线角色扮演游戏(MMORPG),在全球范围内拥有庞大的粉丝群体。对于许多热爱这款游戏的玩家来说,能够体验到一个单人版的《地下城与勇士》无疑是一个令人兴奋的提议。现在,让我们来探索这个由粉丝打造的《地下城与勇士:同人单机版》,它将带给玩......
  • Springboot游戏网站322mj(程序+源码+数据库+调试部署+开发环境)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表用户,游戏信息,游戏分类,拍卖行,卖家,装备购买,游戏周边,周边购买,点卡充值,充值信息,处罚公示,处罚申诉,商品分类开题报告内容一、研究背景与意义随着信息技术......
  • 我的世界(Minecraft)_游戏地图的生成
    相关:HowMinecraftACTUALLYWorks......
  • 如何编程求解俄罗斯方块游戏问题
    相关:对于特定的游戏问题使用启发式算法可以取得比AI算法更好的表现UsingA.I.toDOMINATENERDSinTETRISMachineLearning:AILearnsToPlayTetriswithConvolutionalNeuralNetworkAIlearnstoplayTetrisusingMachineLearningandConvolutionalNeuralNetwor......
  • 【C语言】分支和循环详解(下)猜数字游戏
    与诸君共进步!!!!!文章目录1.随机数的生成2.猜数字小游戏的实现1.随机数的生成掌握了前⾯学习的这些知识,我们就可以写⼀些稍微有趣的代码了,⽐如:写⼀个猜数字游戏游戏要求:电脑⾃动⽣成1~100的随机数玩家猜数字,猜数字的过程中,根据猜测数据的⼤⼩给出⼤了或⼩了的......
  • [luoguP2713] 罗马游戏
    题意原题链接维护一个数据结构,要求支持合并集合或删除集合最小值并输出。sol双倍经验,同[luoguP3377]左偏树/可并堆代码#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintN=1000005;structNode{intl,r;int......
  • 上古卷轴msvcp120.dll文件丢失怎么办?上古卷轴游戏msvcp120.dll缺失问题的高效解决方案
    对于热爱《上古卷轴》系列游戏的玩家来说,遇到游戏因msvcp120.dll文件丢失而无法运行的情况无疑是一个令人沮丧的问题。这个动态链接库文件(DLL)是MicrosoftVisualC++RedistributablePackage中的一个关键组件,对于游戏的正常运行至关重要。一旦这个文件缺失,游戏可能无法加载必......
  • ssm052游戏攻略网站的设计与实现+vue(论文+源码)-kaic
      毕业设计(论文)题目:游戏攻略网站设计与实现      摘 要现代经济快节奏发展以及不断完善升级的信息化技术,让传统数据信息的管理升级为软件存储,归纳,集中处理数据信息的管理方式。本游戏攻略网站就是在这样的大环境下诞生,其可以帮助管理者在短时间内处理完......