华为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;
    }