证明特定矩阵存在

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(使用前将#替换为@)

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

  • 如何使用 Julia 查找矩阵中的连通分量

    假设我有以下矩阵 此处用 Julia 语言定义 mat 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 将一组值为 1 的相邻元素视为一个 分量 如何识别该矩阵有 2 个分量以及每个分量由哪些顶点组成 对于矩
  • 将数字公平分配到两组的算法

    给定一组 n 个数字 1 每组的总数最多相差 1 A 中所有数字的总和尽可能接近 B 中所有数字的总和 即分布应该是公平的 有人可以建议一种有效的算法来解决上述问题吗 谢谢 由于数字很小 因此它不是 NP 完全的 为了解决这个问题 你可以使
  • 对相当大的整数的大集合的操作的快速实现

    描述 我实现了以下类 LabSetInt64 参见下面的代码 这里的目标是尽可能快地操作大量大整数 最多 10M 的值 我的主要要求集中在 至关重要 尽快获取集合的大小 基数 重要 能够非常快速地迭代一组集合 所以 从下面的实现开始 我还有
  • 分词统计方法

    我想解决分词问题 从没有空格的长字符串中解析单词 例如我们想要从中提取单词somelongword to some long word 我们可以通过字典的动态方法来实现这一点 但我们遇到的另一个问题是解析歧义 IE orcore gt or
  • 对二进制二维矩阵进行排序?

    我在这里寻找一些指示 因为我不太知道从哪里开始研究这个 我有一个二维矩阵 每个单元格中有 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 我想对其进行排序 使其尽可能 上三角
  • 从二维排序数组中查找第 k 个最大元素

    我有一个二维数组 行和列已排序 如何从二维数组中找到第 k 大元素 如果你有一个n n矩阵 那么可以在平均时间内完成此操作O n log n log n 您所做的是将矩阵分解为一系列排序数组 然后立即对所有数组进行二分搜索 例如假设n 4并
  • 如何计算python 2D散点占用面积

    我使用 matplotlib 绘制了这两个 2000 个点的序列 从图片上看 前2000点占用的面积比后2000点要小 但如果我想定量计算2000个点的第一序列和第二序列占用了多少面积 该怎么办 我真的很感谢任何帮助 建议或意见 非常感谢
  • 计算 Adamic-Adar 的快速算法

    我正在研究图形分析 我想计算一个 N N 相似度矩阵 其中包含每两个顶点之间的 Adamic Adar 相似度 为了概述 Adamic Adar 让我从以下介绍开始 给定邻接矩阵A无向图的G CN是两个顶点的所有公共邻居的集合x y 两个顶
  • 算法 - 如何有效删除列表中的重复元素?

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

    我一直在研究基数排序实现 到目前为止粘贴在下面的代码 代码是用 Java 编写的 但在 C C 中应该也能正常工作 正如您从实现中看到的 我首先执行最高有效位 即整数的第 31 位 这似乎更快 因为一旦子组完成 就不再需要迭代 例如 打个比
  • 优化 HTML 属性压缩顺序

    我在某处读到 按一定顺序组织 HTML 属性可以提高 HTML 文档的压缩率 我想我是从 Google 或 Yahoo 推荐的更快网站上读到这篇文章的 如果我没记错的话 建议是将最常见的属性放在第一位 例如id等 然后将其余的按字母顺序排列
  • 找到质数?

    为了判断 N 是否是质数 我们只需要查找所有小于或等于 sqrt N 的数字 这是为什么 我正在编写 C 代码 因此试图理解其背后的原因 如果 N 是一个正整数 且能被两个正整数 1 和 N 整除 则 N 是素数 由于数字的约数不能大于该数
  • 将整数列表划分为总和相等的 K 个子列表

    类似的问题还有1 https stackoverflow com questions 27322804 partition of a set into k disjoint subsets with equal sum and 2 http
  • Python 中的空填字游戏求解器

    我得到了一个包含填字游戏蓝图的矩阵 当然 它是空的 我们的目标是填补整个难题 这是 Checkio 的一项任务 我已经为此奋斗了相当长一段时间 根据我对复杂性的理解 这个问题没有完美的算法 不过 必须有最好的方法来做到这一点 对吧 我尝试了
  • 用于计算三角函数、对数或类似函数的算法。仅限加减法

    我正在修复 Ascota 170 古董机械可编程计算机 它已经开始工作了 现在我正在寻找一种算法来展示其功能 例如计算三角或对数表 或类似的东西 不幸的是 从数学运算来看 计算机只能进行整数的加减法 从 1E12到1E12的55个寄存器 甚
  • 运行时间为 O(n) 且就地排序的排序算法

    有没有运行时间为O n 并且还分类到位 在某些情况下 最好的情况是 O n 但这可能是因为项目集合已经排序 你正在看 O nlogn 一些较好的平均值 话虽如此 排序算法的 Wiki 还是相当不错的 有一个表格比较了流行的算法 说明了它们的
  • 处理流星中的长服务器端计算

    我正在使用 jimp https www npmjs com package jimp https www npmjs com package jimp 在meteor JS中生成图像服务器端 换句话说 我正在使用递归算法 计算 图像的像素
  • 如何在 JavaScript 中构建树模式匹配算法?

    好吧 这是一个有点复杂的问题 但是 tl dr 基本上是如何使用 模式树 解析 实际树 如何检查特定的树实例是否与特定的模式树匹配 首先 我们有我们的结构模式树 模式树通常可以包含以下类型的节点 sequence节点 匹配一系列项目 零个或
  • 线段树java实现[关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 你知道 二进制 的良好实现吗线段树 http en wikipedia org wiki Segmen
  • 分而治之算法找到两个有序元素之间的最大差异

    给定一个整数数组 arr 找出任意两个元素之间的差异 使得较大的元素出现在 arr 中较小的数字之后 Max Difference Max arr x arr y x gt y 例子 如果数组是 2 3 10 6 4 8 1 7 那么返回值

随机推荐

  • 将 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