扑克牌问题

2024-03-07 00:18

文章标签 问题扑克牌

本文主要是介绍扑克牌问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

手里有一副牌，取第一张牌放到桌子上，取第二张牌放到牌堆底部，取第三张牌放到桌子上，取第四张牌放到牌堆底部… 直到手里没有牌了。现在桌子上的牌是从 1 到 n 按顺序排列的，求牌在手里时的顺序是怎样的？

思路

比如一副牌在手里时的顺序是 [1 5 2 4 3]，经过上面的规则变换后在桌子上的顺序就是 [1 2 3 4 5]，变换过程是这样的：

	桌子	手里	操作
0:	[]	[1 5 2 4 3]	– 将 1 放到桌子上，将 5 放到堆底
1:	[1]	[2 4 3 5]	– 将 2 放到桌子上，将 4 放到堆底
2:	[1 2]	[3 5 4]	– 将 3 放到桌子上，将 5 放到堆底
3:	[1 2 3]	[4 5]	– 将 4 放到桌子上，将 5 放到堆底
4:	[1 2 3 4]	[5]	– 将 5 放到桌子上
5:	[1 2 3 4 5]	[]

解法：假设牌在手里时的顺序是 [a1 a2 a3 a4]，经过下面的变换过程变成了 [a1 a3 a5 a4 a2]：

	桌子	手里
0:	[]	[a1 a2 a3 a4 a5]
1:	[a1]	[a3 a4 a5 a2]
2:	[a1 a3]	[a5 a2 a4]
3:	[a1 a3 a5]	[a4 a2]
4:	[a1 a3 a5 a4]	[a2]
5:	[a1 a3 a5 a4 a2]	[]

最后在桌子上的牌是 [1 2 3 4 5]，那么就意味着 a1 = 1, a3 = 2, a5 = 3, a4 = 4, a5 = 2，原来在手里的顺序就是 [1 5 2 4 3]。也就是说只要按题目的规则变换数组，最后数组中的值就是原数组的下标，比如 a5 = 3 就说明 3 在 a5 的位置， a5 原来在索引为 5 的位置。

vector<int> getInitial(vector<int> a)
{deque<int> tempDeq;vector<int> tempVec;vector<int> resultVec;int count=0;for (int k = 0; k < a.size(); ++k) {tempDeq.push_back(a[k]);}while (!tempDeq.empty()){if (count%2==0){tempVec.push_back(tempDeq.back());tempDeq.pop_back();} else{tempDeq.push_front(tempDeq.back());tempDeq.pop_back();}count++;}resultVec=tempVec;for (int i = 0; i < resultVec.size(); ++i) {resultVec[tempVec[i]-1]=i+1;}return resultVec;
}