有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡是报到3的人退出圈子,问最后留下来的是原来的第几位(指针方法处理)。

标签: c++  指针  数据结构

1、前言
一开始我感觉这道题应该蛮简单的,不就是到第三个人那不报数嘛,然后问最后一个留下的人原来排在第几号。经过博主仔细阅读之后,发现,事情并非如此简单。因为,他说了,每到第三个人那就退出,也就是说,在原来元素顺序的基础上,要从第3,6,9,12等三的倍数之后的序号退出该排序(此时博主还没系统学过数据结构,只是稍微了解了一点数据结构的知识,所以咱只用现有的C/C++语言的知识来借题就可)。
2、解体思路
上面已经说了,首先咱得从每到第三号位的时候,退出这个圈子;
其次,退出去之后,后面的元素得依次向前移一位。因为,前面的3已经退出了,而问题又问的是这个位置上的数原来排在第几号,所以我们得把后面的元素都依次向前移。
最后,光是向前移还不行,还必须在移的时候用一个数组来记录所移元素的初始位置。
3、
好,说了那么多,接下来就直接看代码

#include <iostream>
using namespace std;

int main()
{
    void sort(int*, int);
    cout << "请输入N个人" << endl;
    int number;
    int n = 0;//用n来记录退出的次数
    cin >> number;//输入的人数
    cout << "请输入每个人的数字代号"<<endl;
    int* p =new int[number];//申请一个可以存入输入的人数的动态数组
    for (int i = 0;i < number;i++) {
        cin >> *(p+i);//输入人的代号
    }    
    int* mark = new int [number];//用来标记该元素改变前的位置
    for(int i=0;i<number;i++)
    {
        mark[i] = i;
    }
    for (int i = 0;i < number;i++)
    {
        if ((i + 1) % 3 == 0) {//如果到第三个人就退出
            p[i - n] = -1;//用-1来提示退出圈子
            sort(p + i - n, number - i);//调用sort函数来退出第三个人,函数值从第i个人开始,余下number-1-i个人
            sort(mark + i - n, number - i);
            n = n + 1;//记录改变次数
        }
    }
    for (int i = 0;i < number;i++) {//输出改变之后的排序
        if (p[i] == -1) break;//输出到-1时直接退出循环
        cout << p[i] << " ";//输出数组
    }
    cout << endl;
    for (int i = 0;i < number;i++) {//输出现有排序的元素的原有位置
        if (p[i] == -1)break;
        cout << " " << p[i] << "原有的位置是:" << mark[i] << endl;
    }
    delete[]p;//清空指针数组
    delete[]mark;
    return 0;
}

void sort(int* p,  int n) {//用p来接受数组p+i的首地址;这里的n是用来接收该次退出的第三位元素之后的元素总数
    int *t=new int[n-1];//申请一个存n-1个人的动态数组,该数组用来记录所接受的数组的第p+i+1位之后的元素
    int z;//申请一个用来将数组的第p+i位与最后一位数转换的变量
    if (n != 1) {//使用这个控制条件的原因是因为当n=1时,调用函数的数组访问的是最后一个有效元素(不等于1的元素)
        for (int i = 0;i < n - 1;i++) { *(t + i) = *(p + i + 1); } //将数组的p+i+1之后的地址存的值都传给数组t
        if (*p == -1) {//将所接受的数组的地址的值与数组末尾的地址的值交换,将-1放在数组的末尾
            z = *p;
            *p = *(p + n - 1);
            *(p + n - 1) = z;
        }
        for (int i = 0;i < n - 1 ;i++) { *(p + i) = *(t + i); }//将t存入的值再传回给数组p+i之后的值,到第n-1个结束
    }
    delete[]t;//清空指针
}

在这里插入图片描述
好啦,整个代码已经写完了,这也是靠现有知识花了两天时间才做出来了这道题(中途遇到了蛮多bug的,看来是真的没天赋了哈哈哈),不过,通过自己一手做出来的时候,那感觉还不错。

版权声明:本文为YweiK原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/YweiK/article/details/106468498