证明特定矩阵存在

2024-04-01

我在编程论坛 Ohjelmointiputka 中发现了这个问题:

  • https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu and
  • https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu2 https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu2

有人说计算机可以找到解决方案,但我找不到证明。

证明存在一个包含 117 个元素且包含数字的矩阵,使得人们可以读取数字 1、2、...、100 的平方。

这里的 read 意味着你固定起始位置和方向(8 种可能性),然后朝那个方向走,连接数字。例如,如果您可以连续找到数字 1,0,0,0,0,4,则您找到了整数 100004,其中包含 1、2、10、100 和 20 的平方数,因为您可以从该序列中读出 1、4、100、10000 和 400(反转)。

但是要找到的数字太多了(准确地说,是 100 个平方数,如果删除另一个总共 312 位的平方数中包含的数字,则为 81 个),而矩阵中的整数又太少了,因此您必须将所有这些数都放入平方数如此密集,以至于找到这样的矩阵很困难,至少对我来说是这样。

我发现如果存在这样一个矩阵mxn,我们可以不失一般性地假设m1x117, 3x39 or 9x13。但是什么样的算法可以找到矩阵呢?

我已经成功地编写了一个程序来检查要添加的数字是否可以放在黑板上。但如何实现搜索算法呢?

# -*- coding: utf-8 -*-

# Returns -1 if can not put and value how good a solution is if can be put. Bigger value of x is better.
def can_put_on_grid(grid, number, start_x, start_y, direction):
#   Check that the new number lies inside the grid.
    x = 0
    if start_x < 0 or start_x > len(grid[0]) - 1 or start_y < 0 or start_y > len(grid) - 1:
        return -1
    end = end_coordinates(number, start_x, start_y, direction)
    if end[0] < 0 or end[0] > len(grid[0]) - 1 or end[1] < 0 or end[1] > len(grid) - 1:
        return -1
#   Test if new number does not intersect any previous number.
    A = [-1,-1,-1,0,0,1,1,1]
    B = [-1,0,1,-1,1,-1,0,1]
    for i in range(0,len(number)):
        if grid[start_x + A[direction] * i][start_y + B[direction] * i] not in ("X", number[i]):
            return -1
        else:
            if grid[start_x + A[direction] * i][start_y + B[direction] * i] == number[i]:
                x += 1
    return x

def end_coordinates(number, start_x, start_y, direction):
    end_x = None
    end_y = None
    l = len(number)
    if direction in (1, 4, 7):
        end_x = start_x - l + 1
    if direction in (3, 6, 5):
        end_x = start_x + l - 1
    if direction in (2, 0):
        end_x = start_x
    if direction in (1, 2, 3):
        end_y = start_y - l + 1
    if direction in (7, 0, 5):
        end_y = start_y + l - 1
    if direction in (4, 6):
        end_y = start_y
    return (end_x, end_y)

if __name__ == "__main__":
    A = [['X' for x in range(13)] for y in range(9)]
    numbers = [str(i*i) for i in range(1, 101)]
    directions = [0, 1, 2, 3, 4, 5, 6, 7]
    for i in directions:
        C = can_put_on_grid(A, "10000", 3, 5, i)
        if C > -1:
            print("One can put the number to the grid!")
    exit(0)

我还发现认为暴力搜索或最佳优先搜索太慢。我认为可能有一个使用模拟退火、遗传算法或装箱算法的解决方案。我还想知道是否可以应用马尔可夫链以某种方式找到网格。不幸的是,以我目前的技能来说,这些似乎太难实现了。


有一个程序可以解决这个问题https://github.com/minkkilaukku/square-packing/blob/master/sqPackMB.py https://github.com/minkkilaukku/square-packing/blob/master/sqPackMB.py。只需将第 20 行和第 21 行中的 M=9、N=13 更改即可。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

证明特定矩阵存在 的相关文章

  • 在现实生活中,您会使用 heapq Python 模块做什么?

    读完吉多的书后使用 Python 对 2MB RAM 中的一百万个 32 位整数进行排序 http neopythonic blogspot com 2008 10 sorting million 32 bit integers in 2m
  • 最小对的总和

    Given 2N点 in a 2D plane 你必须将它们分组为N pairs使得所有对的点之间的距离的总和是最小可能值 所需的输出只是总和 换句话说 如果a1 a2 an分别是第一对 第二对 和第 n 对点之间的距离 则 a1 a2 a
  • 在 O(log n) 中查找排序矩阵(行 n 列)中的数字 [重复]

    这个问题在这里已经有答案了 假设我有一个矩阵 MxN 其行和列已排序 每行中的所有元素均按升序排列 每列中的所有元素均按升序排列 所有元素均为整数 无法做出其他假设 Example 1 5 8 20 2 9 19 21 12 15 25 3
  • 对二进制二维矩阵进行排序?

    我在这里寻找一些指示 因为我不太知道从哪里开始研究这个 我有一个二维矩阵 每个单元格中有 0 或 1 例如 1 2 3 4 A 0 1 1 0 B 1 1 1 0 C 0 1 0 0 D 1 1 0 0 我想对其进行排序 使其尽可能 上三角
  • 以小于 O(n^2) 的复杂度计算两个数组中的互质对数量

    我在挑战中遇到了这个问题 有两个数组 A 和 B 的大小均为 N 我们需要返回对的计数 A i B j 其中gcd A i B j 1 and A i B j 我只能想到暴力方法 它超出了少数测试用例的时间限制 for int i 0 i
  • DPLL算法定义

    我在理解 DPLL 算法时遇到一些问题 我想知道是否有人可以向我解释它 因为我认为我的理解是不正确的 我理解的方式是 我采用一些文字集 如果每个子句都为真 则模型为真 但如果某些子句为假 则模型为假 我通过查找单元子句递归地检查模型 如果有
  • 算法 - 如何有效删除列表中的重复元素?

    有一个list L 它包含以下元素任意类型each 如何有效删除此类列表中的所有重复元素 必须保留订单 只需要一个算法 因此不允许导入任何外部库 相关问题 在Python中 从列表中删除重复项以使所有元素都是唯一的最快算法是什么在维持秩序的
  • 为什么我的 Project Euler Problem 12 算法这么慢?

    我已经在 Scala 中为 PE P12 创建了解决方案 但速度非常非常慢 有人可以告诉我为什么吗 如何优化这个 calculateDevisors 简单的方法和calculateNumberOfDivisors 除数函数具有相同的速度 i
  • 用于基本要素匹配的最坏情况 NlogN 算法

    查找两个相同大小数组的元素之间的唯一映射 https stackoverflow com questions 4411940 find the unique mapping between elements of two same size
  • 识别鼠标移动的算法

    我想知道是否有任何研究 算法可以指定鼠标在识别 等字符时的偏差量使用鼠标绘制 某种光学字符识别 但可能是一个更简单的版本 是否有某种算法可以让我说用户绘制的问号确实是一个问号 而不是其他具有一定准确性的东西 就像 Windows 平板电脑软
  • 运行时间为 O(n) 且就地排序的排序算法

    有没有运行时间为O n 并且还分类到位 在某些情况下 最好的情况是 O n 但这可能是因为项目集合已经排序 你正在看 O nlogn 一些较好的平均值 话虽如此 排序算法的 Wiki 还是相当不错的 有一个表格比较了流行的算法 说明了它们的
  • 如何检查无向图是否有奇数环

    我试图找到一个 O V E 时间算法来检查是否已连接 无向图有或没有奇数环 我正在考虑对图进行广度优先搜索 并尝试将顶点标记为黑色和白色 以便没有两个标记为相同颜色的顶点相邻 是否有任何已知的更简洁的算法可以在线性时间内解决这个问题 你的方
  • 当平方和为N时,如何找到四个变量的所有可能值?

    A 2 B 2 C 2 D 2 N给定一个整数N 打印出整数值的所有可能组合ABCD求解方程 我猜我们可以比暴力做得更好 天真的暴力会是这样的 n 3200724 lim sqrt n 1 for a 0 a lt lim a for b
  • 在 3d 网格中转发(绘制)线

    我需要类似 Bresenham 算法的东西 但是 对于 3d 网格空间来说不完全是这样 我需要 3d 单元网格 边缘尺寸 1 0 从 S 点开始 前进到 K 点 接触 该线接触的所有单元格 即使只有边缘 点被触摸我需要触摸所有 8 个单元
  • 从原点开始在离散 2D 网格上迭代向外螺旋的算法

    例如 这是预期螺旋的形状 以及迭代的每个步骤 y 16 15 14 13 12 17 4 3 2 11 18 5 0 1 10 x 19 6 7 8 9 20 21 22 23 24 其中线条是 x 轴和 y 轴 以下是算法每次迭代 返回
  • 简单的排名算法

    我需要创建一个民意调查 按照项目的好坏顺序创建一个排名列表 我打算向每个用户展示两个项目 让他们选择一个他们认为更好的项目 然后多次重复这个过程 它有点类似于您在社交网络电影 我应该如何根据收到的答案对项目进行排名 看着那 这ELO国际象棋
  • 定点数学比浮点运算快吗?

    多年前 即 20 世纪 90 年代初期 我构建了图形软件包 该软件包基于定点算术和预先计算的 cos sin 表格以及使用牛顿近似方法进行 sqrt 和对数近似的缩放方程来优化计算 这些先进技术似乎已经成为图形和内置数学处理器的一部分 大约
  • 在任意时间范围内找到最佳日/月/年间隔的算法?

    如果您有时间表 请说 March 19 2009 July 15 2011 是否有一种算法可以将该时间范围分解为 March 19 2009 March 31 2009 complete days April 1 2009 December
  • “包含字符串”的快速索引

    在我的应用程序中 我有多达数百万个短字符串 大部分短于 32 个字符 我想实现一个带有附加列表的搜索框 该列表仅包含包含在搜索框中输入的整个字符串的元素 如何预先建立索引来快速找到此类字符串 所有排序的 STL 容器都会检查整个字符串 对于
  • 如何在 C# 中以编程方式创建柔和的颜色?

    根据所需的颜色数量均匀分布地生成它们 如果指定的计数为 8 则看起来像这样 List

随机推荐

  • 将 SAFEARRAY 从 C++ 返回到 C#

    我有一个 C 方法 可以创建 填充并返回 SAFEARRAY SAFEARRAY TestClass GetResult long size return GetSafeArrayList size How should I export
  • Lua中运算符~=是什么意思?

    什么是 Lua中的运算符是什么意思 例如 在以下代码中 if x params then the is not equals 这在其他语言中是等价的
  • 尝试在Flash AS3.0中使用BindingUtils

    我无法使此代码在包含 Flex SDK 4 0 的 AS3 0 Flash 中工作 import mx binding utils Bindable var myValue int 0 var cw ChangeWatcher Bindin
  • 如何手动向已在 mechanize 中设置了 cookie 的会话添加更多 cookie?

    我有一个 python 脚本 它抓取页面并接收 cookie 我想将另一个 cookie 附加到发送到服务器的现有 cookie 中 这样 在下一个请求中 我将获得原始页面中的 cookie 以及我手动设置的 cookie 无论如何要这样做
  • 更改 axios 的默认基本 url

    我已经像这样配置了我的 axios const axiosConfig baseURL http 127 0 0 1 8000 api timeout 30000 Vue prototype axios axios create axios
  • Android 滚动时如何在 RecyclerView 中加载更多数据

    我想为一个网站开发android应用程序 我阅读了以下网站的帖子json并显示其在RecyclerView每 10 个帖子以及当用户滚动时RecyclerView显示更多 10 条帖子并结束 我是业余爱好者 我写了下面的代码 但我不知道滚动
  • 如何在 blob 中计算情感分析

    我使用以下方法计算 200 个短句子的情绪 我没有使用训练数据集 for sentence in textblob sentences print sentence sentiment 分析返回两个值 极性和主观性 根据我在网上读到的内容
  • Google 文本转语音 API 音调调整

    如何在此代码中将音调调整为 1 20 from google cloud import texttospeech def text to wav voice name text language code join voice name s
  • 单击带有最新更新的 EditText 时应用程序崩溃(gradle 4.4 - android studio 3.1)

    我最近将我的 android studio 更新到版本 3 1 并将我的 gradle 更新到版本 4 4 从那时起 我一直面临着应用程序在点击某个按钮时进入 ANR 的问题EditText这应该会弹出一个软输入键盘 单击EditText我
  • Ajax 调用不会更新我的行

    我想用字符的 id 更新我的数据库 但是当我将它们放入插槽中时 它不会更新我想要更新的行 我的问题是 你能为我指明如何正确编码或修复我的错误的正确方向吗 function updateTeam var team slot if input
  • 在.Net 中使用 Scala 有什么好处?

    Scala 是一种特殊的编程语言 因为它同时针对 JVM 和 CLR 但有什么好处呢 是否值得将其视为 F 语言的可行替代方案 NET 上的 Scala 是 Miguel Garcia 领导的一项持续努力 最新状态是我们几乎能够在 NET
  • While 循环重置 Bash 脚本中的数字变量[重复]

    这个问题在这里已经有答案了 我正在尝试编写一个简单的 bash 脚本来在一组文件夹中的每个文件中执行某些操作 我还喜欢计算脚本读取了多少个文件 但是当脚本通过循环时 数值变量会被重置 我正在使用的代码是这样的 bin bash let AU
  • 有没有办法获取给定的classes.dex 文件中的类名?

    我正在构建一个家庭自动化应用程序 我正在尝试添加一个插件系统 作为测试 我将测试类 Button 的子类 导出为 APK 文件 并将其放入我的应用程序的文件目录中 我能够创建此类的新实例并将其放入我的视图中使用DexClassLoader
  • 绘制直方图的峰值

    我试图弄清楚如何使用绘制简单直方图的峰值scipy signal find peaks但发现的峰值似乎还很遥远 ages np array 10 5 22 13 50 45 67 30 21 34 60 67 89 45 45 65 his
  • HTTP 是否使用 UDP?

    这可能是一个愚蠢的问题 HTTP 是否使用过用户数据报协议 例如 如果使用 HTTP 传输 MP3 或视频 它内部是否使用 UDP 进行传输 From RFC 2616 http www ietf org rfc rfc2616 txt 通
  • 可以使用数据流将 pubsub 消息重复数据删除回 pubsub 吗?

    我有一个将数据写入 Google Cloud pubsub 的应用程序 根据 pubsub 的文档 由于重试机制而导致的重复偶尔可能会发生 还有消息乱序的问题 这在 pubsub 中也得不到保证 另外 根据文档 可以使用 Google Cl
  • 表设计+SQL问题

    我有一个餐桌食品吧 是使用以下 DDL 创建的 我使用的是mySQL 5 1 x CREATE TABLE foodbar id INT NOT NULL AUTO INCREMENT user id INT NOT NULL weight
  • 动态创建 Laravel Request 对象

    我正在一个控制器中处理数据 并希望将其进一步传递到另一个控制器中以避免重复代码 有没有办法设置另一个控制器中需要的 Request 对象store 方法 我追踪了 Request 继承并找到了 Symfony 的 Request 对象 它有
  • Java事件和事件监听器[关闭]

    很难说出这里问的是什么 这个问题是含糊的 模糊的 不完整的 过于宽泛的或修辞性的 无法以目前的形式得到合理的回答 如需帮助澄清此问题以便重新打开 访问帮助中心 help reopen questions 我在 Google 上搜索以了解如何
  • 证明特定矩阵存在

    我在编程论坛 Ohjelmointiputka 中发现了这个问题 https www ohjelmointiputka net postit tehtava php tunnus ahdruu https www ohjelmointipu