【刷题小结】华为2016研发工程师编程题-删数

我原来是没有打算把做过的题写成博客的，因为大部分还是基础题，而且我往往都是暴力求解，不太优雅。但是做了这道数独题对我还是很有启发的，虽然我仍然用的是暴力求解。做过的很多题有些有着很精巧的解法，但是往往随着时间过去也不太记得了。本地的很多cpp文件总是不能同步带走，而且很多做题的网站查看代码也不是很方便，所以就记录一下权当纪念了。

题目描述

有一个数组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]进行计算。

输出

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

示例

输入

8

输出

6

解题

思路

这道题就是我说的有一些精巧的题，固然是可以用暴力来把删数的过程模拟出来，但是还有更好的递归的方法，虽然我一开始想到的是暴力或者递归的方法，但是最后我还是把递归写成了循环，大概是受到算法作业影响……
  假设现在有一串连续的$n$个数$f(n)$：$0,1,2,...,n-2,n-1$，然后我们删掉了其中第$m$个数，那下一次要进行操作的串为$m,m+1,...,n-1,0,1,...,m-2$，我们将它映射到一个新长度为$n-1$的串$f(n-1)$：$0,1,...,n-3,n-2$，表示如下：

原始新的m0m+11......0n-m1n-m+1......m-2n-2

通过上表我们可以看到两者有如下映射关系：
$$原始=(新的+m)/n$$
  则$f(n)$最后剩下的数等于$(f(n-1)+m)/n$。那么我们就得到了一个递推的公式，而且当$n=1$时，$f(n)=0$。

代码

    #include<iostream>
    using namespace std;
    
    int main()
    {
    	int N;
    
    	while (cin >> N) {
    		int num = 0;
    		for (int i = 1; i < N; i++) {
    			num = (num + 3) % (i + 1);
    		}
    		cout << num << endl;
    	}
    
    	return 0;
    }