可乐复制问题

问题描述

  自动售货机里有N瓶复制可乐.复制可乐非常神奇，喝了它的人会复制出一个自己来！
  现在有Alice,Bob,Cathy,Dave四个人在排队买复制可乐。买完的人会马上喝掉，然后他和他的副本会重新去队伍的最后面排队买可乐。
  问：最后一个买到复制可乐的人叫什么名字？

输入描述

输入仅有一行，包含一个正整数N；

#输出描述
输出喝到最后一罐复制可乐的人的名字

示例

输入

8

输出

Bob

问题分析

  我们以1,2,3,4分别代表四个名字，那么他们的排列分别是：

序列	序列长度	单个数字重复次数
1 2 3 4	4	1
1 1 2 2 3 3 4 4	8	2
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4	16	3

我们可以看出，归纳总结可以知道，第i轮之后，第i轮的序列长度为\(4*2^{i-1}\)第i轮的每个数字重复频率为\(2^{i-1}\)
思路是，我们首先要确定输入的数字N在第i轮的范围内，然后再根据在这一轮每个数字的重复频率来确定最后N输入那个数字，也就是最后哪个人处于最后

代码

#include<iostream>
#include<cmath>
int main()
{
	using namespace std;

	long n;
	cin >> n;
	if (n <= 4)
	{
		if (1 == n)
			cout << "Alice" << endl;
		else if (2 == n)
			cout << "Bob" << endl;
		else if (3 == n)
			cout << "Cathy" << endl;
		else if (4 == n)
			cout << "Dave" << endl;
		return 0;
	}
	long num=0;
	long i = 1;
	for (; i < n; i++)
	{
		if (n > (num + 4 * pow(2, i - 1)))
			num += 4 * pow(2, i - 1);
		else
			break;
	}

	if (n-num<=pow(2,i-1))
		cout << "Alice" << endl;
	else if (n - num<=2*pow(2, i - 1))
		cout << "Bob" << endl;
	else if (n - num<=3*pow(2, i - 1))
		cout << "Cathy" << endl;
	else if(n-num<=4*pow(2,i-1))
		cout << "Dave" << endl;

	return 0;
}

总结

本来这个题还有一种最笨的解法，就是直接建立一个长度为N的数组，然后把数字一个一个填进去，然后判断最后是第几个人，但是这种方法，当N很大的时候，会占用很多内存，所以放弃了。