最近我接受了一次面试，得到了一个以下问题诀窍是在不使用队列、堆栈或数组的情况下解决此问题。我没能回答这个问题不用说，我没有得到那份工作你将如何解决这个问题。
给你一副牌，里面有N张牌。握住甲板时：
把最上面的卡片从甲板上拿下来放在桌子上
把下一张牌从上面拿下来放在牌堆的底部
在你手里。
继续第1步和第2步，直到所有卡片都在桌上这是一个
圆的。
从桌子上拿起甲板，重复步骤1-3，直到甲板
按原来的顺序。
编写一个程序来确定放置一个
回到原来的顺序这需要创建一个数据
表示卡片顺序的结构不要使用数组。
这个程序只能用C语言编写它应该需要一些
作为命令行参数并将结果写入
标准输出请确保程序正确编译和运行（否
伪代码）这不是个骗人的问题，应该是公平的
直截了当。
最佳答案
不使用任何数组，我看不到任何明显的方法来找出循环群user3386109 mentioned的长度。
另外，“这不是一个技巧[面试]问题”听起来好像面试官只是想让你用数组以外的东西来模拟C中的甲板操作。
想到的直接解决方案是使用单链或双链列表就我个人而言，当洗牌操作将牌移动到牌组的顶部和底部时，我会使用一个单链链表和一个牌组结构来保存牌组中第一张和最后一张牌的指针：
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
struct card {
struct card *next;
long face; /* Or index in the original order */
};
typedef struct deck {
struct card *top;
struct card *bottom;
} deck;
#define EMPTY_DECK { NULL, NULL }
我使用的甲板操纵功能是
static void add_top_card(deck *const d, struct card *const c)
{
if (d->top == NULL) {
c->next = NULL;
d->top = c;
d->bottom = c;
} else {
c->next = d->top;
d->top = c;
}
}
static void add_bottom_card(deck *const d, struct card *const c)
{
c->next = NULL;
if (d->top == NULL)
d->top = c;
else
d->bottom->next = c;
d->bottom = c;
}
static struct card *get_top_card(deck *const d)
{
struct card *const c = d->top;
if (c != NULL) {
d->top = c->next;
if (d->top == NULL)
d->bottom = NULL;
}
return c;
}
由于没有
get_bottom_card()功能，因此不需要使用双链接列表来描述卡片。洗牌操作本身非常简单：
static void shuffle_deck(deck *const d)
{
deck hand = *d;
deck table = EMPTY_DECK;
struct card *topmost;
while (1) {
topmost = get_top_card(&hand);
if (topmost == NULL)
break;
/* Move topmost card from hand deck to top of table deck. */
add_top_card(&table, topmost);
topmost = get_top_card(&hand);
if (topmost == NULL)
break;
/* Move topmost card from hand deck to bottom of hand deck. */
add_bottom_card(&hand, topmost);
}
/* Pick up the table deck. */
*d = table;
}
带有指向卡片列表两端指针的
deck结构类型的好处是避免在shuffle_deck()中进行线性搜索以查找手牌组中的最后一张卡片（用于快速附加到手牌组）。我做的一些快速测试表明，否则线性搜索将成为瓶颈，使运行时间增加大约一半。一些结果：
Cards Rounds
2 2
3 3
4 2
5 5
6 6
7 5
8 4
9 6
10 6
11 15
12 12
13 12
14 30
15 15
16 4
20 20
30 12
31 210
32 12
50 50
51 42
52 510 (one standard deck)
53 53
54 1680
55 120
56 1584
57 57
80 210
81 9690
82 55440
83 3465
84 1122
85 5040
99 780
100 120
101 3360
102 90
103 9690
104 1722 (two decks)
156 5040 (three decks)
208 4129650 (four decks)
然而，使用数组，可以很容易地找出循环长度，并使用这些来计算所需的轮数。
首先，我们创建一个图表或映射卡位置在整轮中的变化：
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>
size_t *mapping(const size_t cards)
{
size_t *deck, n;
if (cards < (size_t)1) {
errno = EINVAL;
return NULL;
}
deck = malloc(cards * sizeof *deck);
if (deck == NULL) {
errno = ENOMEM;
return NULL;
}
for (n = 0; n < cards; n++)
deck[n] = n;
n = cards;
while (n > 2) {
const size_t c0 = deck[0];
const size_t c1 = deck[1];
memmove(deck, deck + 2, (n - 2) * sizeof *deck);
deck[n-1] = c0;
deck[n-2] = c1;
n--;
}
if (n == 2) {
const size_t c = deck[0];
deck[0] = deck[1];
deck[1] = c;
}
return deck;
}
上面的函数返回一个索引数组，对应于每一整轮之后卡片的结束位置因为这些索引指示卡的位置，所以每一轮执行完全相同的操作。
这个函数没有经过优化，甚至效率很低；它使用
memmove()来保持面板的顶部位于数组的开头相反，可以将数组的初始部分视为循环缓冲区。如果您很难将功能与原始指令进行比较，则目的是始终取两张最上面的卡，并将第一张移动到结果牌组的顶部，将第二张移动到手牌组的底部如果只剩下两张牌，第一张牌首先进入结果牌组，第二张牌最后如果只剩下一张牌，它显然会进入结果牌组。在函数中，数组中的第一个
n条目是手牌组，最后一个cards-n条目是表牌组。为了找出循环的数量，我们只需要遍历上面图表或映射中的每个循环：
size_t *cycle_lengths(size_t *graph, const size_t nodes)
{
size_t *len, i;
if (graph == NULL || nodes < 1) {
errno = EINVAL;
return NULL;
}
len = malloc(nodes * sizeof *len);
if (len == NULL) {
errno = ENOMEM;
return NULL;
}
for (i = 0; i < nodes; i++) {
size_t c = i;
size_t n = 1;
while (graph[c] != i) {
c = graph[c];
n++;
}
len[i] = n;
}
return len;
}
这个功能也可以得到很大的增强。这个循环遍历每个周期，即该周期时间内的位置数，而不是只遍历每个周期一次，并将周期长度分配给周期中的所有参与者。
在接下来的步骤中，我们需要知道所有的素数，包括卡片的数量。（包括，因为我们可能只有一个循环，所以我们可能看到的最大长度是卡组中的卡数。）一个简单的选择是使用位图和Sieve of Eratosthenes：
#ifndef ULONG_BITS
#define ULONG_BITS (sizeof (unsigned long) * CHAR_BIT)
#endif
unsigned long *sieve(const size_t limit)
{
const size_t bytes = (limit / ULONG_BITS + 1) * sizeof (unsigned long);
unsigned long *prime;
size_t base;
prime = malloc(bytes);
if (prime == NULL) {
errno = ENOMEM;
return NULL;
}
memset(prime, ~0U, bytes);
/* 0 and 1 are not considered prime. */
prime[0] &= ~(3UL);
for (base = 2; base < limit; base++) {
size_t i = base + base;
while (i < limit) {
prime[i / ULONG_BITS] &= ~(1UL << (i % ULONG_BITS));
i += base;
}
}
return prime;
}
由于可能只有一个周期，覆盖所有卡，因此您需要为上述功能提供卡的数量+1。
让我们看看上面的工作原理让我们定义一些我们需要的数组变量：
size_t cards; /* Number of cards in the deck */
unsigned long *prime; /* Bitmap of primes */
size_t *graph; /* Card position mapping */
size_t *length; /* Position cycle lengths, for each position */
size_t *power;
最后一个“power”应该被分配并初始化为所有零我们将只使用条目[2]到[卡片]，包括在内。其目的是能够将结果计算为∏（p^power[p]），p=2..cards。
首先生成映射，然后计算循环长度：
graph = mapping(cards);
length = cycle_lengths(graph, cards);
要计算轮次数，我们需要对循环长度进行因子分解，并计算长度中每个因子的最大幂的乘积。（我不是数学家，所以如果有人能正确/更好地解释这一点，任何和所有的帮助都是值得赞赏的。）
也许实际的代码更好地描述了它：
size_t p, i;
prime = sieve(cards + 1);
for (p = 2; p <= cards; p++)
if (prime[p / ULONG_BITS] & (1UL << (p % ULONG_BITS))) {
/* p is prime. */
for (i = 0; i < cards; i++)
if (length[i] > 1) {
size_t n = 0;
/* Divide out prime p from this length */
while (length[i] % p == 0) {
length[i] /= p;
n++;
}
/* Update highest power of prime p */
if (power[p] < n)
power[p] = n;
}
}
结果是，在
size_t不够大的情况下使用浮点数学，double result = 1.0;
for (p = 2; p <= cards; p++) {
size_t n = power[p];
while (n-->0)
result *= (double)p;
}
我已经验证了这两个解决方案对于多达294张卡的卡组产生完全相同的结果（慢的非数组解决方案花费了太长时间，以至于295张卡让我等待）。
后一种方法即使对大型甲板也适用例如，在这台笔记本电脑上大约需要64毫秒才能发现，使用10000张卡片组，需要2^5*3^3*5^2*7^2*11*13*17*19*23*29*41*43*47*53*59*61=5153733273880656826400发子弹才能得到原始订单。
（使用双精度浮点数打印小数点为零的结果会产生稍小的结果，51537332738806565830656，因为精度有限。）
用了将近8秒的时间计算出一副10万张牌的回合数是2^7*3^3*5^3*7*11^2*13*17*19*23*31*41*43*61*73*83*101*113*137*139*269*271*277*367*379*541*547*557*569*1087*1091*1097*1103*1109*6.5*10^70。
请注意，出于可视化的目的，我使用了以下代码片段来描述卡在一轮中的位置变化：
printf("digraph {\n");
for (i = 0; i < cards; i++)
printf("\t\"%lu\" -> \"%lu\";\n", (unsigned long)i + 1UL, (unsigned long)graph[i] + 1UL);
printf("}\n");
只需将输出从Graphviz馈送到
dot即可绘制出一个漂亮的有向图。
关于c - 如何不使用队列，堆栈或数组来解决此问题？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29420602/