在代码出现第13天应用Cramer的规则-Python教程-PHP中文网

在代码出现第13天应用Cramer的规则

碧海醫心

发布： 2025-01-28 14:54:10

原创

1128人浏览过

第13天的编程挑战相对简单，尤其对数学基础扎实的朋友来说。起初我尝试蛮力法，但很快意识到随着难度增加，这种方法效率低下。在尝试解决这个问题时，我已经落后几天了。在参考了朋友的建议后，我研究了克莱默法则，最终找到了解决方案。

在代码出现第13天应用Cramer的规则

这是一个代码难题，涉及到一个非传统的爪机控制。我们有两个按钮，分别标记为a和b，它们控制爪机的移动方向，并且每个按钮的按下成本不同。

只要运用正确的数学方法，这个难题并不难。我们从解析输入数据开始：

<code class="python">cost_a = 3
cost_b = 1

type point = tuple[int, int]
type vector = tuple[int, int]

def extract_vector(input: str) -> vector:
    return tuple(int(item.strip().lstrip("x").lstrip("y")) for item in input.split(","))

def extract_point(input: str) -> point:
    return tuple(int(item.strip().lstrip("x=").lstrip("y=")) for item in input.split(","))

def parse(input: str, cost_a: int = cost_a, cost_b: int = cost_b) -> tuple[tuple[dict[vector, int], point], ...]:
    result = ()
    button, goal = {}, ()

    for line in input.strip().splitlines():
        if line.startswith("button a:"):
            button[extract_vector(line.partition(":")[-1])] = cost_a
        elif line.startswith("button b:"):
            button[extract_vector(line.partition(":")[-1])] = cost_b
        elif line.startswith("prize:"):
            goal = extract_point(line.partition(":")[-1])
        else:
            result += ((button, goal),)
            button, goal = {}, ()

    return result + ((button, goal),)</code>

登录后复制

我最近开始在我的代码中添加类型提示。虽然这不会提高运行时性能，但它极大地提高了代码的可读性，尤其是在使用支持良好类型提示的编辑器时。反复输入诸如tuple[int, int]之类的复杂类型很繁琐。幸运的是，Python 3.12引入了类型别名的功能，例如：

<code class="python">type point = tuple[int, int]
type vector = tuple[int, int]</code>

登录后复制

这显著提高了解析函数的可读性。解析函数返回一个元组，每个内部元组包含一个按钮成本映射和目标点。

克莱默法则非常适合解决二元一次方程组，这正是我们需要的。我们有两个方程，分别代表爪机在x和y方向上的移动：

在代码出现第13天应用Cramer的规则

其中：

a_1, a_2: 按下按钮a引起的x和y方向移动
b_1, b_2: 按下按钮b引起的x和y方向移动
c_1, c_2: 奖品的目标x和y坐标
x: 按下按钮a的次数
y: 按下按钮b的次数

示例输入中，按钮a按了80次，按钮b按了40次。我们可以用这些数据验证线性方程。计算得到的x和y坐标验证了我们的方程。

现在我们已经验证了问题可以用线性方程表示，我们可以将其改写成适合应用克莱默法则的形式，从而求解按下每个按钮的次数。这需要将方程表示成矩阵形式，Ax = b：

在代码出现第13天应用Cramer的规则

其中：

A是系数矩阵
x是包含按下每个按钮次数(x和y)的列矩阵
b是包含目标x和y坐标的列矩阵

为了应用克莱默法则，我们首先需要计算矩阵A的行列式，记为d：

AppMall应用商店

AI应用商店，提供即时交付、按需付费的人工智能应用服务

查看详情

在代码出现第13天应用Cramer的规则

然后，我们计算行列式d_x和d_y。为了计算d_x，我们将常数矩阵b替换矩阵A的第一列。同样，为了计算d_y，我们将常数矩阵b替换矩阵A的第二列：

在代码出现第13天应用Cramer的规则

现在我们可以用克莱默法则计算按下按钮a (x) 和b (y) 的次数：

在代码出现第13天应用Cramer的规则

在实现中，我们需要一个函数来计算2x2矩阵的行列式。我们将矩阵表示为字典，键是(行，列)索引(从(0,0)开始)，值是对应的矩阵元素：

<code class="python">def determinant(matrix: dict[point, int]) -> int:
    return matrix[(0, 0)] * matrix[(1, 1)] - matrix[(0, 1)] * matrix[(1, 0)]</code>

登录后复制

接下来，我们实现使用克莱默法则解决难题的核心逻辑。find函数接收按钮移动和目标坐标作为输入，并返回每个按钮需要按下的次数：

<code class="python">def find(buttons: dict[vector, int], goal: point) -> dict[tuple[int, int], int]:
    button_a, button_b = tuple(buttons.keys())
    result = {button_a: 0, button_b: 0}

    d = determinant(
        {
            (0, 0): button_a[0],
            (1, 0): button_a[1],
            (0, 1): button_b[0],
            (1, 1): button_b[1],
        }
    )
    dx = determinant(
        {
            (0, 0): goal[0],
            (1, 0): goal[1],
            (0, 1): button_b[0],
            (1, 1): button_b[1],
        }
    )
    dy = determinant(
        {
            (0, 0): button_a[0],
            (1, 0): button_a[1],
            (0, 1): goal[0],
            (1, 1): goal[1],
        }
    )

    if dx % d == 0 and dy % d == 0:
        result = {button_a: dx // d, button_b: dy // d}

    return result</code>

登录后复制

最后，我们组装第一部分的解决方案，它计算在所有爪机配置中获胜的总成本(点数)。它解析输入，使用find函数确定每个配置的按钮按下次数，并对按钮成本和按下次数的乘积求和：

<code class="python">def part1(input: str) -> int:
    return sum(
        buttons[button] * count
        for buttons, goal in parse(input)
        for button, count in find(buttons, goal).items()
    )</code>

登录后复制

第二部分将10¹³添加到所需的x和y坐标。由于我们使用的是克莱默法则，只需简单地修改传递给find函数的目标坐标即可：

<code class="python">def part2(input: str) -> int:
    return sum(
        buttons[button] * count
        for buttons, goal in parse(input)
        for button, count in find(
            buttons,
            tuple(item + 10000000000000 for item in goal)
        ).items()
    )</code>

登录后复制

这个难题比后来的代码挑战简单，但编写这篇文章却花费了更多时间。我必须仔细检查公式以确保准确性，并经常参考我的笔记以避免错误。我花在写这篇文章上的时间肯定比解决难题本身更多。

这就是本周的编程挑战。如果您正在寻找软件工程师加入您的团队，请随时联系！感谢您的阅读，我们下周再见！

以上就是在代码出现第13天应用Cramer的规则的详细内容，更多请关注php中文网其它相关文章！