嗨,我遇到了這個難題,它是名爲Cryptarithms的着名的基於字和數字的難題的子集。假設有一個表達式作爲解決加密算法的有效方法
發EÑd + M O對 - [R E = M O對ÑE Y
現在最有趣的部分存在這樣,每個字母是表示從0-9的唯一數字。我想寫一個廣義的求解器,但是我最終爲它寫了一個強力的解決方案。任何接受者,我該如何解決它?
我認爲它可以使用謂詞邏輯或集合論來解決。我對找到基於C#或Python的解決方案特別感興趣。任何人。?
嗨,我遇到了這個難題,它是名爲Cryptarithms的着名的基於字和數字的難題的子集。假設有一個表達式作爲解決加密算法的有效方法
發EÑd + M O對 - [R E = M O對ÑE Y
現在最有趣的部分存在這樣,每個字母是表示從0-9的唯一數字。我想寫一個廣義的求解器,但是我最終爲它寫了一個強力的解決方案。任何接受者,我該如何解決它?
我認爲它可以使用謂詞邏輯或集合論來解決。我對找到基於C#或Python的解決方案特別感興趣。任何人。?
this可能會有所幫助
編輯:您發佈的維基鏈路上的回答也很有用!
這是一個小問題,蠻力解決方案不是一個壞方法。假設每個字母必須代表一個獨特的數字(即我們不允許解S = 9,M = 1,* = 0),我們可以看到要嘗試的組合數是!,其中 n是密碼中唯一字母的數量。要評估的理論最大組合數量爲 10! = 3 628 800,這對於電腦來說確實很小。
如果我們讓幾個字母來代表相同的號碼,組合嘗試的數量將 10^N爲界,又在那裏ñ是獨特的字母數。假設只有大寫英文字母,我們的理論最大組合數爲 10^26,所以對於理論上最壞的情況,我們可能需要一些啓發式。儘管如此,大多數實際的密碼體積都少於26個獨特的字母,所以正常情況下可能會受到小於10的限制,這對於計算機來說也是相當合理的。
蠻力可能是一個特定的情況下,怎麼樣,它必須適用於任何限制內指定的輸入必須工作? – 2009-04-15 13:35:17
這就是我的回答。對於任何一般性的輸入,我們都可以找到一個蠻力搜索最糟糕的情況。如果我們想要一個嚴格的解決方案,它是10 !,如果我們允許重複它是10^26。 – Christoffer 2009-04-15 20:57:54
好吧,試着寫它的功能列表:
SEND
MORE
----+
MONEY
如果我記得我的低年級的數學,這應該是:
Y = (D+E) mod 10
E = ((N+R) + (D+E)/10) mod 10
...
這裏是一個有效的蠻力方法週期通過所有可能的遞歸方式,但也注意到特定問題的結構來解決問題。
每個方法的前幾個參數表示每個分支的試用值,參數v1,v2等是尚未分配的值,可以按任意 的順序傳遞。該方法是有效的,因爲它最多有8x7x5可能的試用解決方案,而不是10!/ 2可能的解決方案蠻力
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void MESDYNR(int m, int s, int e, int d, int y, int n, int r, int v1, int v2, int v3)
{
// Solve for O in hundreds position
// "SEND" + "M?RE" = "M?NEY"
int carry = (10 * n + d + 10 * r + e)/100;
int o = (10 + n - (e + carry))%10;
if ((v1 == o) || (v2 == o) || (v3 == o))
{
// check O is valid in thousands position
if (o == ((10 + (100 * e + 10 * n + d + 100 * o + 10 * r + e)/1000 + m + s) % 10))
{
// "SEND" + "MORE" = "MONEY"
int send = 1000 * s + 100 * e + 10 * n + d;
int more = 1000 * m + 100 * o + 10 * r + e;
int money = 10000 * m + 1000 * o + 100 * n + 10 * e + y;
// Chck this solution
if ((send + more) == money)
{
Console.WriteLine(send + " + " + more + " = " + money);
}
}
}
}
static void MSEDYN(int m, int s, int e, int d, int y, int n, int v1, int v2, int v3, int v4)
{
// Solve for R
// "SEND" + "M*?E" = "M*NEY"
int carry = (d + e)/10;
int r = (10 + e - (n + carry)) % 10;
if (v1 == r) MESDYNR(m, s, e, d, y, n, r, v2, v3, v4);
else if (v2 == r) MESDYNR(m, s, e, d, y, n, r, v1, v3, v4);
else if (v3 == r) MESDYNR(m, s, e, d, y, n, r, v1, v2, v4);
else if (v4 == r) MESDYNR(m, s, e, d, y, n, r, v1, v2, v3);
}
static void MSEDY(int m, int s, int e, int d, int y, int v1, int v2, int v3, int v4, int v5)
{
// Pick any value for N
MSEDYN(m, s, e, d, y, v1, v2, v3, v4, v5);
MSEDYN(m, s, e, d, y, v2, v1, v3, v4, v5);
MSEDYN(m, s, e, d, y, v3, v1, v2, v4, v5);
MSEDYN(m, s, e, d, y, v4, v1, v2, v3, v5);
MSEDYN(m, s, e, d, y, v5, v1, v2, v3, v4);
}
static void MSED(int m, int s, int e, int d, int v1, int v2, int v3, int v4, int v5, int v6)
{
// Solve for Y
// "SE*D" + "M**E" = "M**E?"
int y = (e + d) % 10;
if (v1 == y) MSEDY(m, s, e, d, y, v2, v3, v4, v5, v6);
else if (v2 == y) MSEDY(m, s, e, d, y, v1, v3, v4, v5, v6);
else if (v3 == y) MSEDY(m, s, e, d, y, v1, v2, v4, v5, v6);
else if (v4 == y) MSEDY(m, s, e, d, y, v1, v2, v3, v5, v6);
else if (v5 == y) MSEDY(m, s, e, d, y, v1, v2, v3, v4, v6);
else if (v6 == y) MSEDY(m, s, e, d, y, v1, v2, v3, v4, v5);
}
static void MSE(int m, int s, int e, int v1, int v2, int v3, int v4, int v5, int v6, int v7)
{
// "SE**" + "M**E" = "M**E*"
// Pick any value for D
MSED(m, s, e, v1, v2, v3, v4, v5, v6, v7);
MSED(m, s, e, v2, v1, v3, v4, v5, v6, v7);
MSED(m, s, e, v3, v1, v2, v4, v5, v6, v7);
MSED(m, s, e, v4, v1, v2, v3, v5, v6, v7);
MSED(m, s, e, v5, v1, v2, v3, v4, v6, v7);
MSED(m, s, e, v6, v1, v2, v3, v4, v5, v7);
MSED(m, s, e, v7, v1, v2, v3, v4, v5, v6);
}
static void MS(int m, int s, int v1, int v2, int v3, int v4, int v5, int v6, int v7, int v8)
{
// "S***" + "M***" = "M****"
// Pick any value for E
MSE(m, s, v1, v2, v3, v4, v5, v6, v7, v8);
MSE(m, s, v2, v1, v3, v4, v5, v6, v7, v8);
MSE(m, s, v3, v1, v2, v4, v5, v6, v7, v8);
MSE(m, s, v4, v1, v2, v3, v5, v6, v7, v8);
MSE(m, s, v5, v1, v2, v3, v4, v6, v7, v8);
MSE(m, s, v6, v1, v2, v3, v4, v5, v7, v8);
MSE(m, s, v7, v1, v2, v3, v4, v5, v6, v8);
MSE(m, s, v8, v1, v2, v3, v4, v5, v6, v7);
}
static void Main(string[] args)
{
// M must be 1
// S must be 8 or 9
DateTime Start = DateTime.Now;
MS(1, 8, 2, 3, 4, 5, 6, 7, 9, 0);
MS(1, 9, 2, 3, 4, 5, 6, 7, 8, 0);
Console.WriteLine((DateTime.Now-Start).Milliseconds);
return;
}
}
}
+1:從今年的PyCon最好的談判之一恕我直言 – miles82 2009-04-15 11:22:16