C++ 中约瑟夫环替换计数器m(数组解决)

C++ 中约瑟夫环替换计数器m(数组解决)

题目描述：

输入一个由随机数组成的数列（数列中每个数均是大于0的整数，长度已知），和初始计数值m。从数列首位置开始计数，计数到m后，将数列该位置数值替换计数值m，并将数列该位置数值出列，然后从下一位置从新开始计数，直到数列所有数值出列为止。如果计数到达数列尾段，则返回数列首位置继续计数。请编程实现上述计数过程，同时输出数值出列的顺序

比如：

输入的随机数列为：3,1,2,4，初始计数值m=7，从数列首位置开始计数（数值3所在位置）
第一轮计数出列数字为2，计数值更新m=2，出列后数列为3,1,4，从数值4所在位置从新开始计数
第二轮计数出列数字为3，计数值更新m=3，出列后数列为1,4，从数值1所在位置开始计数
第三轮计数出列数字为1，计数值更新m=1，出列后数列为4，从数值4所在位置开始计数

最后一轮计数出列数字为4，计数过程完成。

输出数值出列顺序为：2,3,1,4。

要求实现函数：

void array_iterate(int len, int input_array[], int m, int output_array[])

【输入】 int len：输入数列的长度；
               int intput_array[]：输入的初始数列
               int m：初始计数值

【输出】 int output_array[]：输出的数值出列顺序

【返回】 无

示例:

输入：int input_array[] = {3,1,2,4}，int len = 4， m=7
输出：output_array[] = {2,3,1,4}

解题思路：

每次出列一个数值，需要对m、input_array、output_array、输出位置outPos、起始位置startPos进行更新；

对于输出位置outPos的计算是关键！通过分析可知，outPos=(startPos+m-1)%num

#include <stdio.h> 

void print_array(int len, int array[])
{
  for(int i=0; i<len; i++)
    printf("%d ", array[i]);
  printf("\n");
}  

void array_iterate(int len, int input_array[], int m, int output_array[])
{
  int startPos=0;
  int outPos;
  int nIter=len-1;
  int num=len;
  for(; nIter>=0; nIter--)
  {
    outPos=(m+startPos-1)%num;//难点，计算输出的位置
    m=input_array[outPos];
    startPos=outPos;
    printf("outPos is %d, m变为 %d\n", outPos, m);
    output_array[len-nIter-1]=m;
    for(int i=outPos; i<num-1; i++)
      input_array[i]=input_array[i+1];
    num--;
    print_array(num, input_array); //输出每次删除后的数列
  }
}
void main()
{
  int input_array[]={3,1,2,4};
  int output_array[4]={0};
  array_iterate(4, input_array, 7, output_array);
  printf("出列顺序为\n");
  print_array(4, output_array); //最后输出output_array
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • C++ 中循环链表和约瑟夫环

    循环链表和约瑟夫环 循环链表的实现 单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个环,成为单循环链表,简称循环链表.当它是空表,向后结点就只想了自己,这也是它与单链表的主要差异,判断node->next是否等于head. 代码实现分为四部分: 初始化 插入 删除 定位寻找 代码实现: void ListInit(Node *pNode){ int item; Node *temp,*target; cout<<"输入0完成初始化"&

  • C++ 约瑟夫环的实例代码

    C++ 约瑟夫环的实例代码 约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围.从编号为k的人开始报数,数到m的那个人出列:他的下一个人又从1开始报数,数到m的那个人又出列:依此规律重复下去,直到圆桌周围的人全部出列. 分析:有n个人,要想所有的人都退出去,只有每个人喊到m,才可以退完,所以可以算出,n*m为所有人总共报数的总次数. 代码: /* * 约瑟夫出圈 */ #include <stdio.h> int main() { char peo[

  • C++循环链表之约瑟夫环的实现方法

    本文实例形式展示了C++实现循环链表中约瑟夫环的方法,分享给大家供大家参考之用.具体方法如下: 主要功能代码如下: #include <iostream> using namespace std; typedef struct student { int data; struct student* next; }node,*LinkList; //约瑟夫环 void printfList(LinkList head){ LinkList p=head; if (head!=NULL) { do

  • C++ 中约瑟夫环替换计数器m(数组解决)

    C++ 中约瑟夫环替换计数器m(数组解决) 题目描述: 输入一个由随机数组成的数列(数列中每个数均是大于0的整数,长度已知),和初始计数值m.从数列首位置开始计数,计数到m后,将数列该位置数值替换计数值m,并将数列该位置数值出列,然后从下一位置从新开始计数,直到数列所有数值出列为止.如果计数到达数列尾段,则返回数列首位置继续计数.请编程实现上述计数过程,同时输出数值出列的顺序 比如: 输入的随机数列为:3,1,2,4,初始计数值m=7,从数列首位置开始计数(数值3所在位置) 第一轮计数出列数字为

  • Java简单实现约瑟夫环算法示例

    Java简单实现约瑟夫环算法示例

    本文实例讲述了Java简单实现约瑟夫环算法.分享给大家供大家参考,具体如下: 1.算法背景: 罗马人攻占了乔塔帕特,41人藏在一个山洞中躲过了这场浩劫.这41个人中,包括历史学家josephus和他的一个朋友.剩余的39个人为了表示不向罗马人屈服,决定集体自杀.大家决定了一个自杀方案,所有这41人围城一个圆圈,由第一个人开始顺时针报数,没报数为3的人就立刻自杀,然后由下一个人重新开始报数 仍然是每报数为3的人就立刻自杀,......,知道所有人都自杀死亡为止. 约瑟夫和他的朋友并不想自杀,于是约

  • PHP基于递归实现的约瑟夫环算法示例

    本文实例讲述了PHP基于递归实现的约瑟夫环算法.分享给大家供大家参考,具体如下: 约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓.于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀.然后下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏. <?php $nu

  • PHP使用栈解决约瑟夫环问题算法示例

    本文实例讲述了PHP使用栈解决约瑟夫环问题算法.分享给大家供大家参考,具体如下: 约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓.于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀.然后下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏. <?php cla

  • javascript循环链表之约瑟夫环的实现方法

    前言 传说在公元1 世纪的犹太战争中,犹太历史学家弗拉维奥·约瑟夫斯和他的40 个同胞被罗马士兵包围.犹太士兵决定宁可自杀也不做俘虏,于是商量出了一个自杀方案.他们围成一个圈,从一个人开始,数到第三个人时将第三个人杀死,然后再数,直到杀光所有人.约瑟夫和另外一个人决定不参加这个疯狂的游戏,他们快速地计算出了两个位置,站在那里得以幸存.写一段程序将n 个人围成一圈,并且第m个人会被杀掉,计算一圈人中哪两个人最后会存活.使用循环链表解决该问题. 看到这个问题首先想到的是要用到循环链表,还有就是要计算

  • C语言约瑟夫环的实现

    C语言约瑟夫环的实现 一.典故: 据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是商量了一个自杀方式: 41个人排成一个圆圈,由第1个人 开始报数,每数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要 他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死

  • 详解基于C++实现约瑟夫环问题的三种解法

    详解基于C++实现约瑟夫环问题的三种解法

    目录 一.前言 二.循环链表模拟 三.有序集合模拟 四.递归公式解决 五.结语 一.前言 什么是约瑟夫环问题? 约瑟夫环问题在不同平台被"优化"描述的不一样,例如在牛客剑指offer叫孩子们的游戏,还有叫杀人游戏,点名--最直接的感觉还是力扣上剑指offer62的描述:圆圈中最后剩下的数字. 问题描述: 0,1,···,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数).求出这个圆圈里剩下的最后一个数字. 例如,0.1.2.3.4这

  • JavaScript三种方法解决约瑟夫环问题的方法

    目录 概述 问题描述 循环链表 有序数组 数学递归 总结 概述 约瑟夫环问题又称约瑟夫杀人问题或丢手绢问题,是一道经典的算法问题.问题描述也有很多变式,但大体的解题思路是相同的.本篇将以循环链表.有序数组.数学递归三种方式来解决约瑟夫环问题. 问题描述 先来看一下什么是约瑟夫环问题? 在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀

  • C语言数据结构中约瑟夫环问题探究

    目录 问题描述 基本要求 测试数据 实现思路1 实现思路2 结果 数据结构开讲啦!!! 本专栏包括: 抽象数据类型 线性表及其应用 栈和队列及其应用 串及其应用 数组和广义表 树.图及其应用 存储管理.查找和排序 将从简单的抽象数据类型出发,深入浅出地讲解复数 到第二讲线性表及其应用中会讲解,运动会分数统计,约瑟夫环,集合的并.交和差运算,一元稀疏多项式计算器 到最后一步一步学会利用数据结构和算法知识独立完成校园导航咨询的程序. 希望我们在学习的过程中一起见证彼此的成长. 问题描述 约瑟夫环问题

随机推荐