密码算术
4.85/5 (11投票s)
创建和解决密码算术的科学与艺术。
问题定义
密码算术是一种数学谜题，其中数字被字母或其他符号替换。(参见下图。)如果同一个字母出现多次，则每次都必须为其分配相同的数字。任何两个不同的字母都不能分配相同的数字。因此，问题是找出与唯一字母相对应的唯一数字。密码算术是创建和解决密码算术的科学与艺术。J. A. Hunter 创造了“字母算术”一词，用来指字母组成有意义的词语或短语的密码算术。
S E N D
+ M O R E
-----------------
M O N E Y
世界上最著名的字母算术谜题是 SEND+MORE = MONEY。
解释和概述
这个概念最初由 H.E. Dudeney 提出，并首次发表在 1924 年 7 月的《Strand Magazine》上，与一个绑匪勒索赎金的故事有关。
密码算术是约束满足问题的一个很好的例子。密码算术问题与其说是提供描述，不如说由一些约束条件来定义。定义密码算术问题的约束条件如下：
- 每个字母或符号在整个问题中只代表一个唯一的数字。
- 当数字替换字母或符号时，生成的算术运算必须正确。
这两个约束条件会导致问题中的一些其他限制。考虑到数字的基数为 10。那么问题中最多只能有 10 个唯一的符号或字母。否则，就不可能为问题中的每个唯一字母或符号分配唯一的数字。
为了在语义上有所意义，数字不能以零开头。因此，每个数字开头的字母不应对应于零。
程序逻辑
错误检查
在应用任何算法之前，我们需要验证用户输入的输入是正确的。
- 不同字母的总数应小于或等于 10。
- 答案的长度不应小于任何操作数的长度。
- 答案的长度只能比任何一个操作数多一个。
这里有两种算法可以用来解决问题。它们是约束规范和进化算法。
约束规范
约束是特定于问题的。这里有一些例子。SEND + MORE = MONEY 这个谜题，解决后看起来会是这样
S E N D
9 5 6 7
+ M O R E
1 0 8 5
---------
M O N E Y
1 0 6 5 2
在加法或减法中搜索“0”和“9”
寻找零或九的一个好提示是查找包含两个或三个相同字母的列。看看这些加法
* * * A * * * B
+ * * * A + * * * A
------- -------
* * * A * * * B
列 A+A=A 和 B+A=B 表明 A=零。在数学中，这被称为“零的加法恒等性质”；它表示你加上“0”不会改变任何东西，因此它保持不变。现在，看看密码算术主体中的相同加法
* A * * * B * *
+ * A * * + * A * *
------- -------
* A * * * B * *
在这些情况下，我们可能有 A=零或 A=9。这取决于是否从前一列收到了“进位 1”。换句话说，“9”在每次获得“1”的进位时都像零一样。
在加法中搜索“1”
看看左边的数字。如果它们是单个的，它们可能是“1”。以世界上最著名的密码算术为例
S E N D
+ M O R E
---------
M O N E Y
“M”只能等于 1，因为它是 S+M=O (+10) 列的“进位 1”。换句话说，每次“n”个数字相加得到“n+1”位数的总和时，总和的左边那个数字必须是“1”。
盲目搜索最终可以在有限的时间内找到解（如果存在）。考虑到数字的基数为 10，问题空间中可能有 10n 个解需要检查；其中 n 是问题中唯一字母或符号的数量。基于规则的搜索技术可以在最短的时间内提供解决方案。
当约束条件应用于问题时，如果有的话，需要搜索的解空间会减小。
进化算法
进化算法 (EA) 是指模仿自然原理的自适应行为的算法的通用术语。
虽然进化算法的定义有所不同，但 EA 更常见的特性是维护问题潜在解的集合。
这些解被称为当前一代的种群。每个潜在解称为一个染色体。
将操作应用于当前种群，以生成一个新一代，该新一代有望包含问题更好解的染色体。这个过程一直持续到达到某个阈值或停止标准。
新一代是通过对当前一代中选定的染色体应用算子来产生的。通常，当前一代中应用算子的染色体是根据它们的质量来选择的。这样，后代染色体就更有可能继承其父母的优良特性。一些启发式方法或适应度函数用于选择一代中的父代染色体。
因此，一个长度为 10 的、由这些字母和额外的“不关心”符号组成的字段是一个不错的选择。如果数字的基数是 n，那么我们将使用一个长度为 n 的数组。字符串中字母的位置表示它们的取值。
S E N D M O R Y _ _
0 1 2 3 4 5 6 7 8 9
上面用“_”（下划线）表示“不关心”符号，字母下方的数字表示它们在字符串中的位置以及在解中的相应值。
现在我们可以生成两个随机数，然后像下面图片所示的那样交换这些字母的位置。
Y N R M _ O E D _ S
0 1 2 3 4 5 6 7 8 9
Y N R M _ O D E _ S
0 1 2 3 4 5 6 7 8 9
适应度函数通常表示染色体正确的程度。可以轻松地构建一个评估函数，该函数将计算问题中数学结果的误差。
S E N D
9 7 1 6
+ M O R E
3 5 2 7
-------------
M O N E Y
3 5 1 7 0
ERROR = ABS (35170-(9716+3527)) = 21927
误差最小的染色体是一代中最适合的染色体。为了确保后一代不比当前一代差，可以将当前一代中最适合的染色体添加到下一代。但是，这会引入一个“死锁”，因为这些最适合的染色体即使存在解也无法导向解。或者一个叫做“局部最小值”的问题。因此，可以给随机染色体一个机会来贡献下一代。这个修改将避免死锁。
算法
- 步骤 1：扫描输入字符串。
- 步骤 2：检查输入是否正确。
- 步骤 3：将字母或符号放入
ARRAY[10]。 - 步骤 4：应用算术规则并尝试缩小解空间。
- 步骤 5：如果不同字母的数量小于 10，则用不关心符号填充
ARRAY的其余索引。这个ARRAY[10]现在是我们当前的一代。 - 步骤 6：多次生成两个随机数 m、n，并交换当前一代任何一个染色体索引 m 和 n 的内容，并将这个新染色体复制到下一代。
- 步骤 7：评估下一代每个染色体的适应度，并选择最佳染色体。现在这些最佳染色体成为我们当前的一代。同时将一个随机染色体也包含到当前一代中。如果当前一代中没有误差为 0 的染色体，则转到步骤 6。如果找到一个误差为 0 的染色体，则报告解并退出。
根据特定问题的难度，可以设置一些参数，如每代染色体的数量、为繁殖选择的染色体数量以及为避免局部最小值而选择的随机染色体数量，以在最小的搜索范围内获得解决方案。
代码
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace CryptArithmetic
{
public partial class Form1 : Form
{
char[] s1 = new char[10];
char[] s2 = new char[10];
char[] s3 = new char[10];
int[] assinged = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
char[] c = new char[11];
int[] val = new int[11];
int topc = 0;
public Form1()
{
InitializeComponent();
}
private void btn_ok_Click(object sender, EventArgs e)
{
label4.Text = "";
s1 = textBox1.Text.ToCharArray();
s2 = textBox2.Text.ToCharArray();
s3 = textBox3.Text.ToCharArray();
int flag=0;
for(int i=0;i<s1.Length;i++)
{
for(int j=0;j<=topc;j++)
{
if(s1[i]!=c[j])
flag=1;
else
{
flag =0;
break;
}
}
if(flag==1)
c[topc++] =s1[i];
}
for(int i=0;i<s2.Length;i++)
{
for(int j=0;j<=topc;j++)
{
if(s2[i]!=c[j])
flag=1;
else
{
flag =0;
break;
}
}
if(flag==1)
c[topc++] =s2[i];
}
for(int i=0;i<s3.Length;i++)
{
for(int j=0;j<=topc;j++)
{
if(s3[i]!=c[j])
flag=1;
else
{
flag =0;
break;
}
}
if(flag==1)
c[topc++] =s3[i];
}
if (solve(0, assinged)==1)
{
for(int i=0;i<c.Length;i++)
label4.Text += "\n"+ c[i]+"--->"+val[i].ToString() + "\n";
}
else
label4.Text = "Sorry";
}
//-------------------end of getdata-----------------
int solve(int ind,int []temp1)
{
int [] temp2 = new int[10];
int flag=0;
for(int i=0;i<10;i++)
{
if(temp1[i]==0)
{
for(int j=0;j<10;j++)
temp2[j]=temp1[j];
temp2[i]=1;
val[ind]=i;
if(ind==(topc-1))
{
if(verify()==1)
{
flag=1;
goto exit;
}
}
else
{
if(solve(ind+1,temp2)==1)
{
flag=1;
goto exit;
}
}
}
}
exit :
if(flag!=0)
return 1;
else
return 0;
}
int verify()
{
long n1=0,n2=0,n3=0;
long power=1;
char ch;
int i=s1.Length-1;
int in1;
while(i>=0)
{
ch=s1[i];
in1=0;
while(in1!=topc)
{
if(c[in1]==ch)
break;
else
in1++;
}
n1+=power*val[in1];
power *=10;
i--;
}
power=1;
i=s2.Length-1;
while(i>=0)
{
ch=s2[i];
in1=0;
while(in1!=topc)
{
if(c[in1]==ch)
break;
else
in1++;
}
n2+=power*val[in1];
power *=10;
i--;
}
power=1;
i=s3.Length-1;
while(i>=0)
{
ch=s3[i];
in1=0;
while(in1!=topc)
{
if(c[in1]==ch)
break;
else
in1++;
}
n3+=power*val[in1];
power *=10;
i--;
}
if(n1+n2==n3)
return 1;
else
return 0;
}
private void Form1_Load(object sender, EventArgs e)
{
}
private void textBox1_TextChanged(object sender, EventArgs e)
{
}
}
}
局限性
这个程序仍然有机会可以提高效率，并在最短的时间内获得输出。它最多找到 10 个不同的解（如果存在），不多于 10 个。这仅限于加法，不解决减法或乘法问题。这也仅限于解决有两个操作数的方程，而不能用于解决方程中超过两个操作数的问题。
示例输入/输出
参考文献
- 人工智能 (Artificial Intelligence) 作者：Kelvin Knight 和 Rich。