题目:
一副从1到n的牌,每次从牌堆顶取一张放桌子上,再取一张放牌堆底,直到手里没有牌.最后桌子上的牌是从1到n有序,设计程序,输入n,输出牌堆的顺序数组
这里有介绍两种方式解题
1.第一种方式,通过逆向推倒, 从桌子上拿起排好序的牌.当手里没有牌时,从桌子上拿起第一张牌放到手里.当手里已经有牌之后,拿起桌子上的牌放到手里牌的最上面,将手里最底下的牌放到从上面数的第二张.
for (int i = 0; i < n; i ++) {
if (i == 0) {
array[n - 1 ] = n;
}else{
// 将新的牌插入到最上面
array[n - i - 1] = n - i;
// 记录最后一张牌的值
int last = array[n - 1];
// 新牌后面所有的牌向后移动一位
for (int j = n - 1; j > n - i ; j --) {
array[j] = array[j - 1];
}
// 将原来的最后一张牌放到新牌的后面
array[n - i] = last;
}
}
for (int i = 0; i < n; i ++) {
printf("%d\n",array[i]);
}
2.第二种方式,是先将1...n的牌顺序排列,然后按照题目中描述的步骤重新排列.将得到的牌面上的数字,替换成该数字的索引对应的牌面数字,最终得到的顺序就是题目要求的结果.
for (int i = 0; i < n; i ++) {
// 将堆顶的牌放到result顶
result[i] = source[i];
// 记录第二位的牌
int second = source[i + 1];
for (int j = i + 1; j < n - 1; j ++) {
source[j] = source[j + 1];
}
source[n - 1] = second;
}
for (int i = 0; i < n; i ++) {
printf("%d\n",result[i]);
}
printf("------替换后-----\n");
// 将牌面数字作为map的key,将索引作为value,将key顺序排列,
//得到的value的序列就是要求的结果
//这里直接用循环来查找了
for (int i = 1; i <= n; i ++) {
for (int j = 0; j < n; j ++) {
if (result[j] == i) {
printf("%d\n",j + 1);
break;
}
}
}
第一种逆向推到的方法略去不表,只看第二种正序推到后,再按索引替换,为什么得到的就是想要的结果呢?
假设n=6,按照题目描述的步骤排序后得到的顺序是135264
但是题目上说的是放到桌子上之后的顺序是123456,而现在牌面顺序是135264.现在假设牌的背面都写上的目前对应的索引.
| 背面 | 正面 |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 5 |
| 4 | 2 |
| 5 | 6 |
| 6 | 4 |
现在我们不管最初牌堆里的123456是怎么排成现在的156342的,只是把牌的正面重新排列成123456.然后把牌背面朝上,看到的背面的顺序就是我们要求的结果.
| 背面 | 正面 |
|---|---|
| 1 | 1 |
| 4 | 2 |
| 2 | 3 |
| 6 | 4 |
| 3 | 5 |
| 5 | 6 |
第二种方式的好处是,完全可逆,不用倒着推.换成更复杂的步骤,这样替换索引仍然是可行的.
此文题目和解题思路源自https://www.jianshu.com/p/fa3abe4e2531
