华为2016研发工程师编程题 删数

一、题目重现

　　题目: 有一个数组a[N]顺序存放0~N-1，要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。以8个数(N=7)为例:｛0，1，2，3，4，5，6，7｝，0->1->2(删除)->3->4->5(删除)->6->7->0(删除),如此循环直到最后一个数被删除。

　　输入描述: 每组数据为一行一个整数n(小于等于1000)，为数组成员数,如果大于1000，则对a[999]进行计算。

　　输出描述: 一行输出最后一个被删掉的数的原始下标位置。

　　输入例子1: 8

　　输出例子1: 6

二、解题思路

发现这是著名的约瑟环问题

第一种解法，比较符合人的思考方式，构造链表来模拟人删数字的方式，隔两个删掉一个，如果遇到结尾，则指针指到开始部分继续执行，直到列表中没有元素，这时候跳出循环，输出指针指向的数字；

 这种解法很容易想到，不过要模拟整个游戏过程，时间空间复杂度比较高。

#include <iostream>
#include <list>
using namespace std;

int main()
{
    int input;
    while (cin >> input) {
        list<int> que;
        for (int i = 0; i < input; ++i) {
            que.push_back(i);
        }

        list<int>::iterator iter = que.begin();
        while (que.size() > 1) {
            for (int i = 0; i < 2; ++i) {
                ++iter;
                if (iter == que.end()) iter = que.begin();
            }

            list<int>::iterator deleteIter = iter;
            ++iter;
            if (iter == que.end()) iter = que.begin();
            que.erase(deleteIter);
        }
        cout << *iter << endl;
    }
    return 0;
}

　　

第二种解法，找到其中的数学规律；

当有连续的n个数时，删掉第m个的数，发现[m],[m+1],...这剩下的n-1个数还可以看成是连续数，只要把>n的数，对n取余即可；

将[m], [m+1], ...对应0, 1, ..., n-1。这时从连续的n-1个数，删掉第m个数；

假设n个数最终剩下的数是f(n,m)，这个数一定能在n-1个数中找到，且有一定对应关系。

可推之，f(n,m) = [ f(n-1, m) + m ] % n ; 且当n=1时，f(1,m)=0；

#include <iostream>
using namespace std;

int main()
{
    int n;
    while (cin >> n) {
        int f = 0;
        for (int i = 1; i < n; ++i) {
            f = (f + 3) % (i + 1);
        }
        cout << f << endl;
    }
        
    return 0;
}

此题也运用了动态规划问题的思想，将一个问题拆子问题，求解子问题，即可推断出大问题的解。

推荐阅读：什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 阮行止的回答 - 知乎 https://www.zhihu.com/question/23995189/answer/613096905

以上两种解法均测试通过所有用例；