敢死队问题

news/2024/11/23 5:27:46/

1.1.1分析论证:有M个敢死队员要炸掉敌人的一碉堡,谁都不想去,排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务,则要再派一个战士上去。现给每个战士编一个号,大家围坐成一圈,随便从某一个战士开始计数,当数到5时,对应的战士就去执行任务,且此战士不再参加下一轮计数。如果此战士没完成任务,再从下一个战士开始数数,被数到第5时,此战士接着去执行任务。以此类推,直到任务完成为止。
1.1.2目的意义:(1)排长是不愿意去的,假设排长为1号,我需要设计一程序,求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。
(2)同时我需要采用两种不同的数据结构实现。
1.1.3达到目标:(1)设置好一个循环单链表。(2)选出合适m的倍数,列出,并删除节点。人数减一。(3)用free(p)用完之后就销毁,避免内存空间浪费
1.2、 数据结构和算法说明

1.2.1总体设计与分析和设计:利用逆向思维:
题目中要求排长为1号,问从哪号开始计数可以使得排长最后一个活下来
我们是不是可以这样认为,不妨设从1号开始计数,看看最后幸存的是几号,
再倒推回来就是应该从哪号数数,最后让排长幸存。

1.2.2采用的数据结构:循环单链表和另一种动态规划 。
1.2.3算法思想:
我是以循环单链表的方法来求解这道题的。最后给出一种更好的改进的方法(动态规划)。我先在纸上推导出满足的公式s = (s + k) % i,这是编号从0开始的,现题目要求编号从一开始,所以结果需加一。因此创建了aplus函数来求出其幸存号码。后最后在main函数实现,然后就可求出最终符合条件幸存号码。
在这里插入图片描述

1.2.4遇到的问题:遍历循环单链表时,头尾指针的next设置错了,导致不能构成一个圆圈去遍历它。还有一点是利用动态规划算法中
在动态规划算法中,
1.2.5解决方法:设置好头指针的next指向空,同时把data的值赋给i,把尾指针tail赋给p。p赋值回尾指针tail。
1.3、全部源程序清单
代码清单及主要注释:
源文件下的main.cpp如下:

第一种方法:
#include <iostream>  
#include<stdio.h>
#include<malloc.h>
using namespace std;
//const int mod = 1000;
struct node
{int data;node *next;
};
int main()
{int n, m;//定义头结点,尾结点 ,还有p,q指针 node *head, *p, *tail, *q;//动态申请一片内存空间,用来存放一个结点,同样可以用C++语言中的new来实现 head = new node;//head = (struct node*)malloc(sizeof(struct node));head->next = NULL;//尾指针指向头指针,形成循环链表 tail = head;cout << "该题目是约瑟夫问题的变种,我们可以用求解约瑟夫问题的思路来求解敢死队问题\n" << endl;cout << "从1号开始数数:\n" << endl;cout << "请输入n,n代表总人数:" << endl;cin >> n;cout << "请输入m,m代表每数到第m个就去执行任务:" << endl;cin >> m;//m的意思是每数到m就出列去执行任务 for (int i = 1; i <= n; i++){  //开始遍历整个圆圈(循环单链表)//p = (struct node*)malloc(sizeof(struct node));p = new node;//构建循环链表 p->next = NULL;p->data = i;tail->next = p;tail = p;}tail->next = head->next;//  ans我设置为从1号开始报数 int ans = 1;q = head;p = head->next;//只考虑n>1的情况 ,因为n如果小于等于1就不用选了 while (n != 1){// 如果报的数不是m的倍数,就没事,继续数 if (ans%m != 0){p = p->next;q = q->next;}else{  //找到m的倍数,就出列,删除结点 q->next = p->next;//用完之后就销毁,避免内存空间浪费 free(p);p = q->next;//人数减一个 n--;}//一个人报完数就接着下一个人 ans++;}cout << "幸存的是:" << endl;cout << p->data << "号" << endl;cout << "因此应在从1号开始数数的基础上倒退" << endl;cout << p->data - 1 << "位" << endl;cout << "开始数数,可保证 排长最后一个留下" << endl;cout << "任意键关闭";cin.get();cin.get();
}
第二种方法:
#include <iostream>
using namespace std;int aplus(int n, int k) {  //创建aplus函数来统计,n为统计总人数,k代表每数到第j个就去执行任务//非递归版本int s = 0;//初值赋值0for (int i = 2; i <= n; i++)s = (s + k) % i; //取余求出最终结果s值,s为幸存号数。return s + 1;//编号从0开始,如果编号从1开始时,结果得加1;
}
int main() {int m,i,gg;//gg代表幸存号数cout << "请输入m,m代表总人数\n";cin >> m;for (i = 1; i <= m; i++)if (m == i){gg = aplus(i, 5);cout << i << ' ' << gg << endl;	//调用aplus(),5代表每数到第5个就去执行任务}cout << "幸存的是:" << endl;cout << gg << "号" << endl;cout << "因此应在从1号开始数数的基础上倒退" << endl;cout << gg - 1 << "位" << endl;cout << "开始数数,可保证 排长最后一个留下" << endl;cout << "按任意键结束";cin.get();cin.get();}

1.4、程序运行、测试与分析
1.4.1运行结果:
在这里插入图片描述


http://www.ppmy.cn/news/588459.html

相关文章

华为铁三角:浅聊铁三角模式的角色边界

今年早些时候&#xff0c;石头做过一期铁三角案例梳理&#xff0c;看看哪些标杆企业在用「铁三角」&#xff0c;以及「铁三角」是哪些角色构成。 当时的重点放在标杆企业名单梳理&#xff0c;以及铁三角角色构成这两件事情上&#xff0c;对这些案例的行业属性、客户属性、销售…

华为铁三角:铁三角模式诞生背景与思考

横看成岭侧成峰&#xff0c;不同的人看不同时期的华为铁三角&#xff0c;其答案是不一样的&#xff0c;在这众多的不同里面&#xff0c;如果要找一个相同点&#xff0c;也是可以找到的&#xff0c;就是华为铁三角的起点。 学习华为铁三角销售模式&#xff0c;为什么要溯源&…

2.数据的类型、数据的输入输出

2.数据的类型、数据的输入输出 2.1 数据类型-常量-变量(整型-浮点-字符)2.1.1 数据类型2.1.2 常量2.1.3 变量2.1.4 整型类型2.1.5 浮点型数据2.1.6 字符型数据字符型常量字符型变量 2.1.7 字符串型常量 2.2 混合运算-printf讲解 2.1 数据类型-常量-变量(整型-浮点-字符) 2.1.1…

ABeam中国2023社招 | ABeam旗下艾宾信息技术开发(大连)诚邀您的加入

招聘岗位介绍 SAP SD Senior Consultant (English Speaker) Job Requirements 5年以上SD项目实施或支持经验 优秀的沟通技巧&#xff0c;快速的反应和积极的态度 能够在压力下工作或面对挑战 具备ABAP调试和编程能力 有MM交叉模块知识优先 英语口语流利&#xff0c;良…

交叉熵、Focal Loss以及其Pytorch实现

交叉熵、Focal Loss以及其Pytorch实现 本文参考链接&#xff1a;https://towardsdatascience.com/focal-loss-a-better-alternative-for-cross-entropy-1d073d92d075 文章目录 交叉熵、Focal Loss以及其Pytorch实现一、交叉熵二、Focal loss三、Pytorch1.[交叉熵](https://pyto…

Arthas使用方法

一、概述 1、简介 Arthas 是一款基于 Java 开发的开源应用程序诊断工具&#xff0c;可以帮助开发者实时监控和分析 Java 应用程序运行情况&#xff0c;并进行调试和优化。 Arthas 提供了丰富的命令行工具和可视化界面&#xff0c;包括线程堆栈、类加载器、内存使用情况、方法…

Redis列表类型(list)模拟队列操作

文章目录 Redis列表类型模拟队列操作1. 使用用lpush和rpop模拟队列的操作1.1 lpush介绍1.2 rpop介绍1.3 llen介绍1.4 lrange介绍1.5 del命令介绍 2. 使用用rpush和lpop模拟队列的操作2.1 rpush介绍2.2 lpop介绍 Redis列表类型模拟队列操作 Redis的列表类型&#xff08;list&…

socket详解

目录 socket&#xff1a; 套接字的工作原理&#xff1a; 套接字类型&#xff1a; 套接字可以分为两种类型&#xff1a;流套接字&#xff08;Socket Stream&#xff09;和数据报套接字&#xff08;Socket Datagram&#xff09;。 创建套接字&#xff1a; 绑定套接字到地址和…