资源描述：
《九位不同数字乘法等式的优化算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、学术探讨∙算法研究九位不同数字乘法等式的优化算法陈勇(遵义职业技术学院，贵州遵义563000)[摘要]对“九位不同数字构成乘法等式”的问题进行研究分析，深入探讨其解决方案，根据NP问题穷举算法设计的常规思路，设计了一种更加优化的穷举算法，实验证明该算法是正确高效的。[关键词]NP问题；穷举算法；优化算法；高效中图分类号：TP302文献标识码：A文章编号：1008-6609(2016)07-0046-03式中最小的因子组合，而其积3335也不满足数字互不相同的1引言规则，这也说明最小乘积至少大于3000，由于1或者2用于因文
2、献[1]使用数字{1，2，3，4，5，6，7，8，9}组成形如X×Y=Z子，那么最小乘积至少为3456。因此，进一步缩小乘积的范的乘法等式，在该等式中使用且仅使用九个数字中的每个数围是3456～9876。字一次，列举出了所有符合条件的等式。“九位不同数字构成3算法设计乘法等式”的问题显然是NP[2]问题，采取常用数学分析算法（1）在3456至9876中按序取1数，如果已取完则执行求解非常困难，此类问题常采用穷举算法求解[3]。实现的具（9）；体方法很多，用递归与非递归回溯算法实现比较耗时，本文（2）所取数的4位数字用预处理
3、判断是否相异，否则执行提出了一种基于预处理[4]的更加优化的穷举算法，其算法大（1）；大减少了程序运行的时间。（3）所取数是否被2～9中某一数整除，否则执行（6）；2问题分析（4）商为4位数且9个数字相异，否则执行（6）；根据文献[1]可知，9个数字分别为任意的且互不相同的（5）输出一个解；a1，a2，a3，…，a9，所谓符合条件的等式其实是在排列（6）所取数是否被12～98中某一数整除，否则执行（1）；a1a2a3a4a5a6a7a8a9中找到可使等式成立的乘号、等号的位置，（7）商为3位数且9个数字相异，否则执行（1）
4、；即确定两个因子的数字位数。满足等式有两种情形（排除乘（8）输出一个解，执行（1）；法交换律的等价等式）：（9）结束。(a03210321×10)×(a2×10+a3×10+a4×10+a5×10)=(a6×10+a7×10+4算法实现a108×10+a9×10)(1)(a10210324.1算法预处理1×10+a2×10)+(a3×10+a4×10+a5×10)=(a6×10+a7×10+a10用预处理判断乘积中4个数字是否重复，即在穷举乘积8×10+a9×10)(2)穷举数字{1,2,3,…,9}的所有排列非常耗时，通
5、过分析的排列时，用预处理过滤掉乘积中有相同数字的乘积，减少发现只要穷举乘积的排列就可大大减少计算时间，即乘积范搜索空间。围为1234～9876。进一步研究缩小乘积范围，在(1)式中最intjudge1(intx)小的乘积是1×2345＝2345，但1位数字因子不可能是1，那么{最小的1位因子只可能大于等于2，因此构造另一个最小的inta,b,c,d;乘积是2×1345＝2690，根据数字互不相同的规则容易得出，a=x/1000;满足等式的最小乘积至少大于3000；同理可知，23×145是(2)b=x%1000/100;——
6、————————————作者简介：陈勇，男，贵州遵义人，讲师，研究方向：媒体制作与网站建设。-46-学术探讨∙算法研究c=x%100/10;if(a==a3
7、
8、a==b3
9、
10、a==c3
11、
12、a==d3
13、
14、a==a2
15、
16、a==b2)d=x%10;return0;if(d==0
17、
18、b==0
19、
20、c==0)elseif(b==a3
21、
22、b==b3
23、
24、b==c3
25、
26、b==d3
27、
28、b==a2
29、
30、b==b2)return0;return0;if(a==b
31、
32、a==c
33、
34、a==d)elseif(c==a3
35、
36、c==b3
37、
38、c==c3
39、
40、c==
41、d3
42、
43、c==a2
44、
45、c==b2)return0;return0;elseif(b==c
46、
47、b==d
48、
49、c==d)elseif(d==a3
50、
51、d==b3
52、
53、d==c3
54、
55、d==d3
56、
57、d==a2
58、
59、d==b2)return0;return0;elseelseif(a2==a3
60、
61、a2==b3
62、
63、a2==c3
64、
65、a2==d3)return1;return0;}elseif(b2==a3
66、
67、b2==b3
68、
69、b2==c3
70、
71、b2==d3)4.2判断乘积等式是否符合条件return0;intjudge2(intx,inty,int
72、z)elseif(a3==b3
73、
74、a3==c3
75、
76、a3==d3){return0;inta,b,c,d;elseif(b3==c3
77、
78、b3==d3
79、
80、c3==d3)inta2,b2;return0;inta3,b3,c3,d3;elsea=x/1000;return1;b=x%1000/100;}c=x
