主页 / 问题 / 1597470
Accepted
weldoy
Asked:2024-10-22 18:09:10 +0000 UTC2024-10-22 18:09:10 +0000 UTC

解释问题的解决方案。统一国家考试 23 [已关闭]

  • 772

TP4 执行者转换屏幕上的数字。

表演者有两支队伍，并分配了编号：

  1. 添加 1
  2. 乘以 2

也就是说，第一个命令将屏幕上的数字加 1，第二个命令将其乘以 2。

TP4 执行器的程序是一系列命令。

有多少个程序将原来的数字2转换为数字35，但计算路径中包含数字15而不包含数字31？

计算轨迹是所有程序命令执行的结果序列。例如，对于初始编号为 7 的程序 212，轨迹将由数字 14、15、30 组成。

def f(x, y):
    if x > y or x == 31:
        return 0
    elif x == y:
        return 1
    else:
        return f(x + 1, y) + f(x * 2, y)

print(f(2, 15) * f(15, 35))
python

1 个回答

  1. Best Answer

    在这个任务中，我们必须使用某些条件遍历树（作为数据结构）。该任务有更正式的解释（示例），但我将尝试使用清晰、简化的示例进行解释 - 只需减少限制数量。

    我们以条件为例：将 1 转换为 6，其中强制包含 3，不包含 4。

    预期结果是“存在多少个程序”。以最简单的方式，这是成功地将原始数字转换为最终数字的“加 1”和“乘以 2”操作的有效组合的数量。

    我们如何计算组合？让我们创建一个递归函数，它将以两种方式继续进行更改x- 加法和乘法：

    def f(x, y):
    if x > y:
        # если `x` превысил `y`, значит комбинация вычислений оказалась неверна
        # не считаем комбинацию в результат (+0)
        return 0
    elif x == y:
        # если `x` равен `y`, значит ветка древа подходит под условия
        # считаем комбинацию в результат (+1)
        return 1
    else:
        # иначе можно продолжать создавать комбинации из 2х способов
        return f(x + 1, y) + f(x * 2, y)

    这里我们可以确保满足“计算轨迹包含数字”的条件——为此，我们计算在计算过程中首先必然导致我们得出数字3的组合的数量。

    简单来说，就是带参数调用指定的函数(1, 3)：

    1 узел:                        (1, 3)

2 узел:          (2, 3)           |          (2, 3)

3 узел: (3, 3) -> 1 | (4, 3) -> 0 | (3, 3) -> 1 | (4, 3) -> 0

Всего подходящих комбинаций: 2

    也就是说，总共有 2 种组合将成功地将我们从第一名带到第三名：

    +1, +1和*2, +1。

    最后，他们按照自己的分支给予return 1，不适合的则相反return 0。所有这些值都被加到函数的最终结果 - 2中。

    接下来，我们可以使用相同的函数来统计从 3 到最终数字 6 的组合数量，然后将获得的第一个数字与第二个数字相乘（乘法规则）。这将产生一个必须经过数字 3 的组合的数字：

    1 узел:                                 (3, 6)

2 узел:                   (4, 6) -> 0      |        (6, 6) -> 1

3 узел:           (5, 6)     |    (8, 6) -> 0

4 узел: (6, 6) -> 1 | (10, 6) -> 0 

Всего подходящих комбинаций: 2

    但是，我们需要从后续路径中排除通过数字 4 进行的计算，为此，我们将添加该函数，以便x = 4该函数也返回 0，即，它不认为该树枝有效：

    def f(x, y):
    if x > y or x == 4:
        return 0
    elif x == y:
        return 1
    else:
        return f(x + 1, y) + f(x * 2, y)

    同时，如果您使用(1, 3)计算第一部分中的参数调用新函数，那么什么都不会改变，因为因为数量限制为3，x = 4这同时也是一个条件x > y——之前是有限制的。

    (3, 6)但通过计算第二部分的参数，这可以消除不适当的组合：

    1 узел:          (3, 6)

2 узел: (4, 6) -> 0 | (6, 6) -> 1

Всего подходящих комбинаций: 1

    也就是说，从 3 号到 6 号，如果不进入 4 号，只有 1 个组合可以成功：*2

    如上所述，根据乘法规则，我们将接收到的 2 个数字（2 和 1）相乘以获得所有组合（这就是调用 as 时发生的情况f(1, 3) * f(3, 6)）。

    结果，我们得到了答案2——这就是“加1”和“乘2”动作的组合有多少种，可以将1转化为6，而在计算过程中必然得到3，但不会得到4。

    这些组合看起来像：

    1 траектория: 112
(1 + 1 = 2 --> 2 + 1 = 3 --> 3 * 2 = 6)

2 траектория: 212
(1 * 2 = 2 --> 2 + 1 = 3 --> 3 * 2 = 6)

    如果我们从原始问题中获取条件，树会更大，并且更难以将其保留在脑海中/绘制它。但原理是一样的。

    为了更好地理解，您可以替换问题条件。例如，有效的程序操作为“add 1”和“add 2”。然后我们只需要在函数中替换f(x + 1, y) + f(x * 2, y)为f(x + 1, y) + f(x + 2, y)。结果，递归函数将计算新动作的组合树。

    • 4

相关问题