代码之家 › 专栏 › 技术社区 › Zeks

需要从《竞争编程手册》中解释格伦迪的数字吗

algorithm

Zeks · 技术社区 · 2 年前

我试图理解书中的例子 https://cses.fi/book/book.pdf 第239页。该示例描述如下:

我不明白的是,比如说,右下角的数字3意味着什么,我们可以向上移动4步,向左移动3步,3步怎么样?和上面的4一样,它与我能想到的任何一组动作都不对应。一般来说,这本书在逻辑上做了很多飞跃,他们认为这是显而易见的,但通常我可以在一段时间后推断出它们的意思,在这里我只是迷路了。

1 回复 | 直到 2 年前

Peter de Rivaz 2 年前

计算这些数字的规则是递归的。

考虑所有可以达到的值,然后选择无法达到的最小(非负)整数。

例如,左上角的值为0,因为不可能移动。

例如,右下角的值是3,因为可达到的值是0,4,1,0,2,1,4,所以3是不在此列表中的最小整数。

这解释了如何计算这些数字,但要理解它们,最好从理解数字游戏开始 Nim .在尼姆的游戏中,一堆的斯普拉格·格伦迪数等于一堆的大小。

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前