问题98 - 项目Euler

问题如下：通过分别用1,2,9和6替换单词CARE中的每个字母，我们形成一个平方数：1296 = 36 ^（2）。值得注意的是，通过使用相同的数字替换，anagram，RACE，也形成一个平方数：9216 = 96 ^（2）。我们将CARE（和RACE）称为方形字谜词对，并进一步指定不允许前导零，不同字母也不能与另一个字母具有相同的数字值。使用words.txt（右击和'保存链接/目标为...'），一个包含近两千个常用英文单词的16K文本文件，找到所有方形字谜词对（一个回文词不被认为是一个自己的字谜）。这样一对中任何一个成员形成的最大平方数是多少？注意：形成的所有字谜必须包含在给定的文本文件中。我不明白CARE到1296的映射？这是如何运作的？或者是所有排列映射都要尝试，即所有字母都是1-9？

已邀请:

4 个回复

誓猎贰

简而言之：是的，所有的排列都需要尝试。

久坡

允许所有数字到字母的分配。所以C = 1，A = 2，R = 3，E = 4将是一个可能的分配...除了1234不是正方形，所以这是不好的。也许另一个例子可以帮助说清楚？如果我们指定A = 6，E = 5，T = 2，则TEA = 256 = 16 2，EAT = 625 = 25。所以（TEA = 256，EAT = 625）是一个方形的字谜词对。（仅仅因为允许所有数字到字母的分配，并不意味着实际尝试所有这些分配是解决问题的最佳方法。可能还有其他一些更聪明的方法。）

期差骇蓟

如果你测试所有替换字母的数字，而不是你正在寻找具有属性的方形对：长度相同与输入字符串中的出现次数相同的数字。找到所有这些正方形对象的速度更快。有68个正方形，长度为4,216个正方形，长度为5，...按上面的属性过滤所有相同长度的正方形将生成“小”对，这是您正在寻找的解决方案。这些数据是“静态的”，不依赖于输入字符串。它可以计算一次并用于所有输入字符串。

眠缝

嗯。怎么说这个。将Euler项目放在一起的人承诺，对于每个问题都有一分钟的解决方案，而且我认为只有一个问题可能会使这个承诺失败，但事实并非如此。是的，你可以对数字进行置换，并尝试对所有正方形进行所有排列，但这将是一个非常大的搜索空间，完全不可能是（TM）正确的东西。通常，当您看到问题的“查看”将导致搜索时间过长时，您需要搜索其他内容。比如，假设有人要求你确定将两个素数乘以1到1亿的结果是多少。您可以将每个数字的因子计算在1到1之间，但是将两个素数的所有组合相乘并乘以它们可能会更快。既然你正在研究组合，你可以从两个开始，直到你的结果太大，然后用三个相同，等等。相比之下，这应该快得多 - 而且你不必将所有数字相乘out，你可以记录所有素数的日志然后只需添加它们并找到每个素数的限制，给你一个你可以添加的数字列表。有许多创新的解决方案，但您想到的第一个 - 特别是您在Project Euler描述问题时所考虑的那个，可能是错误的。那么，你怎么能解决这个问题呢？可能有太多的排列要看，但也许你可以通过映射找出一些东西并比较映射？（尽量避免全部放弃。）

要回复问题请先登录或注册

问题98 - 项目Euler

4 个回复

发起人

anagram

问题状态

问题98 - 项目Euler

与内容相关的链接

4 个回复

发起人

anagram

问题状态