您必须猜出6个数字。数字应小于50且大于0。数字在游戏中仅出现一次。因此，您不能在一个游戏中多次猜测相同的数字。如果您猜对了6个正确的数字，那么您就赢了这场比赛。
我想知道拥有6个正确的数字需要进行多少次尝试，并编写了此示例。它可以工作，但不幸的是，该示例非常慢并且需要大量时间，因为它不太可能正确包含6个数字。如何提高速度？
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
int play(int attempt[])
{
// generate draw
int draw[6];
draw[0] = rand() % 49 + 1;
for(int i = 1; i < 6; i++)
{
int random_number;
generate:
random_number = rand() % 49 + 1;
for(int j = 0; j < i; j++)
{
if(random_number == draw[j])
{
goto generate;
}
}
draw[i] = random_number;
}
// compare draw with attempt
int compared = 0;
for(int i = 0; i < 6; i++)
{
if(attempt[i] == draw[i])
{
compared++;
}
}
if(compared == 6)
{
return 1;
}
else
{
return 0;
}
}
int main()
{
srand (time(NULL));
int attempt[] = {1, 2, 3, 4, 5, 6};
long long int counter = 1;
while(!play(attempt))
{
counter++;
}
printf("You only needed %lld attempts to get 6 right numbers!\n", counter);
}
顺便说一句：大约5分钟后，程序完成了，我只需要尝试1,487,592,156次！
#1 楼
错误当然不可能赢6/49了。任何一张票证所有六个数字正确的概率为
$$ \ dfrac {1} {\ binom {49} {6}} = \ dfrac {6！\，（49-6） ！} {49！} = \ dfrac {1} {13983816} $$
但是您的代码需要1.5×109抽奖才能赢，这是预期的1.4×107抽奖的100倍。为什么？因为您的比较循环…
// compare draw with attempt
int compared = 0;
for(int i = 0; i < 6; i++)
{
if(attempt[i] == draw[i])
{
compared++;
}
}
………要求所选数字必须具有相同的顺序！因此，与真实6/49游戏相比，在模拟中获胜的可能性要小720倍。
性能和风格
您的
// generate draw循环有一个特例： // generate draw
int draw[6];
draw[0] = rand() % 49 + 1;
for(int i = 1; i < 6; i++)
{
…
您可以轻松消除特殊情况：
// generate draw
int draw[6];
for(int i = 0; i < 6; i++)
{
…
您还可以使用
goto处理两次绘制相同数字的情况。结构良好的代码不应具有goto。作为生成随机数和检查冲突的替代方法，请考虑进行部分改组。建议的解决方案
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
const int *lotto_draw(int r)
{
static int balls[] = {
1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, 12, 13, 14,
15, 16, 17, 18, 19, 20, 21,
22, 23, 24, 25, 26, 27, 28,
29, 30, 31, 32, 33, 34, 35,
36, 37, 38, 39, 40, 41, 42,
43, 44, 45, 46, 47, 48, 49
};
const static int n = sizeof(balls) / sizeof(balls[0]);
// Partial Fisher-Yates shuffle on the last r elements
for (int i = n - 1; i >= n - r; i--)
{
int j = rand() % (i + 1);
int swap = balls[j];
balls[j] = balls[i];
balls[i] = swap;
}
return balls + n - r;
}
int play(int attempt[], int r)
{
const int *draw = lotto_draw(r);
// compare draw with attempt
int correct = 0;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < r; j++)
{
if (attempt[i] == draw[j])
{
correct++;
}
}
}
return (correct == r);
}
int main()
{
srand(time(NULL));
int attempt[] = {1, 2, 3, 4, 5, 6};
int r = sizeof(attempt) / sizeof(attempt[0]);
long long int counter;
for (counter = 1; !play(attempt, r); counter++);
printf("You only needed %lld attempts to get %d right numbers!\n",
counter, r);
}
评论
\ $ \ begingroup \ $
这就是我对规则的理解。我不玩彩票，所以我想就是那样。我会改正的。
\ $ \ endgroup \ $
– exter刺
17年8月16日在21:42
\ $ \ begingroup \ $
@DexterThorn彩票抽取的号码会自动从小到大排序。实际上，许多彩票表格仅在网格中显示每个可能的选项，而您只圈选所需的选项。
\ $ \ endgroup \ $
– Nzall
17年8月17日在8:22
\ $ \ begingroup \ $
@Nzall如果是这样，那不应该影响哪些数字有效吗？例如，如果第一个数字已经是3，则其余数字将不少于3。
\ $ \ endgroup \ $
–桅杆
17年8月17日在9:25
\ $ \ begingroup \ $
@桅杆不行，他们首先抽出所有球，然后对其进行排序。如果您得到42-37-22-32-39-3，则它们总是被视为3-22-32-37-39-42。目标只是猜测所有6个数字，但顺序不对物。在这种情况下，如果抽出42，则将该球从池中取出，并从其余48个球中选择下一个球。我建议下次他们在您观看的当地电视台播放彩票抽奖时，看看会发生什么。
\ $ \ endgroup \ $
– Nzall
17年8月17日在11:53
#2 楼
没有赤裸裸的循环。每次您不得不像
// generate draw这样添加注释时，这意味着您需要将注释的代码分解为generate_draw()函数。返回条件，而不是标志。
if(compared == 6)
{
return 1;
}
else
{
return 0;
}
是很长的话
return compared == 6;
所有这些，该程序的结果具有误导性。并不是说您只需要尝试那么多次。就是这次运行的程序进行了多次尝试。
中奖的概率为\ $ \ dfrac {1} {\ binom {49} {6}} \ $；一个非常小的数字，并且预期的尝试次数为\ $ \ binom {49} {6} \ $。这是一个很大的数目。更糟糕的是，不能保证特定的运行会导致命中。换句话说，有机会无限期地等待（并且有机会在第一次尝试中获胜）。
评论
\ $ \ begingroup \ $
谢谢您的回答！程序的输出当然没有绝对值，只是很有趣地看到它可能需要多少次尝试。我的第二次尝试现在运行了一个半小时（尚未完成）。我首先尝试在一个单独的函数中生成一个数组，然后将其返回给调用函数，但是后来我注意到我需要有关指针的知识，并且需要一些东西来做到这一点。为了简单起见，我只是在相同的函数中生成了数组。但是，当我了解到有关指针的更多信息后，我将尝试按您所说的将函数中的代码分开。
\ $ \ endgroup \ $
– exter刺
17年8月16日在21:34
\ $ \ begingroup \ $
@Deduplicator老实说，我看不出\ $ frac {1} {2} \ $因素可能会如何出现，但是我可能错了。
\ $ \ endgroup \ $
–vnp
17年8月16日在22:44
#3 楼
即使rand()返回均匀分布的数字，也请注意(rand() % 49) + 1不会均匀分布。您的RNG偏向于较小的数字（通常小于RAND_MAX % 49 + 1）。评论
\ $ \ begingroup \ $
由于rand（）在大多数实现中都很烂，所以我不会尝试消除这种偏差（例如通过拒绝），而是切换到实现高质量prng和支持从区间生成数字的高级API的替代库。 0至n-1。
\ $ \ endgroup \ $
– CodesInChaos
17年8月17日在9:20
\ $ \ begingroup \ $
我在这里分析了这种技术引入的偏差：ericlippert.com/2013/12/16/…
\ $ \ endgroup \ $
–埃里克·利珀特
17年8月17日在14:34
#4 楼
正如200_success的答案中指出的那样，比较猜测数字和绘制数字的方式是错误的。但是，不必将每个猜测的数字与每个绘制的数字进行比较，而是可以使用49个元素的表格来加快比较速度。如果一组猜中的数字包含数字i，则索引i处的条目将设置为1。否则，它将被设置为0。因此，您只需进行一次数组查找即可确定一组猜中的数字是否包含数字。这是一个基于200_success答案中的部分Fisher-Yates随机播放的示例。请注意，如果无法匹配任何绘制的数字，我们可以提早终止。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int play(const char attempt_map[49])
{
static int balls[] = {
1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, 12, 13, 14,
15, 16, 17, 18, 19, 20, 21,
22, 23, 24, 25, 26, 27, 28,
29, 30, 31, 32, 33, 34, 35,
36, 37, 38, 39, 40, 41, 42,
43, 44, 45, 46, 47, 48, 49
};
const static int n = sizeof(balls) / sizeof(balls[0]);
// Partial Fisher-Yates shuffle on the last r elements
for (int i = n - 1; i >= n - 6; i--)
{
int j = rand() % (i + 1);
int swap = balls[j];
if (attempt_map[swap-1] == 0)
{
return 0;
}
balls[j] = balls[i];
balls[i] = swap;
}
return 1;
}
int main()
{
srand (time(NULL));
int attempt[] = {1, 2, 3, 4, 5, 6};
char attempt_map[49] = {0};
long long int counter = 1;
// Precompute map.
for (int i = 0; i < 6; i++)
{
attempt_map[attempt[i]-1] = 1;
}
while(!play(attempt_map))
{
counter++;
}
printf("You only needed %lld attempts to get 6 right numbers!\n", counter);
}
代替49元素的char数组，您还可以使用位图额外的加速。
评论
\ $ \ begingroup \ $
您可以使用标准容器并使用std :: iota对其进行初始化，而不是在代码中写出49个数字。这样可以更轻松地更改平局的球数。
\ $ \ endgroup \ $
– Toby Speight
17年8月17日在13:59
\ $ \ begingroup \ $
std :: itoa闻起来像C ++。我的代码是用干净的C语言编写的，因此我在这里不能使用它。
\ $ \ endgroup \ $
– exter刺
17年8月17日在15:03
评论
实际上，由于增加了Superzahl，德国6澳元49彩票的规则略有不同，因此赢得“ 6个正确猜测”类别的机会略有不同（≈1/ 15.5M，而非≈1/ 14.0M） 。@ mkrieger1因为OP不会生成Superzahl，所以他实际上测试了“ 6个正确的猜测（没有Superzahl）或6个与Superzahl正确的猜测”，然后我们又回到了约1 / 14M。我不认为他会介意Superzahl将他“偶然地”提升为更高阶层的人...