九位不同數字乘法等式的優化算法

陳勇

(遵義職業技術學院，貴州 遵義 563000)

九位不同數字乘法等式的優化算法

陳勇

(遵義職業技術學院，貴州 遵義 563000)

對“九位不同數字構成乘法等式”的問題進行研究分析，深入探討其解決方案，根據NP問題窮舉算法設計的常規思路，設計了一種更加優化的窮舉算法，實驗證明該算法是正確高效的。

NP問題；窮舉算法；優化算法；高效

1 引言

文獻[1]使用數字{1，2，3，4，5，6，7，8，9}組成形如X×Y=Z的乘法等式，在該等式中使用且僅使用九個數字中的每個數字一次，列舉出了所有符合條件的等式?！熬盼徊煌瑪底謽嫵沙朔ǖ仁健钡膯栴}顯然是NP[2]問題，采取常用數學分析算法求解非常困難，此類問題常采用窮舉算法求解[3]。實現的具體方法很多，用遞歸與非遞歸回溯算法實現比較耗時，本文提出了一種基于預處理[4]的更加優化的窮舉算法，其算法大大減少了程序運行的時間。

2 問題分析

根據文獻[1]可知，9個數字分別為任意的且互不相同的a1，a2，a3，…，a9，所謂符合條件的等式其實是在排列a1a2a3a4a5a6a7a8a9中找到可使等式成立的乘號、等號的位置，即確定兩個因子的數字位數。滿足等式有兩種情形（排除乘法交換律的等價等式）：

窮舉數字{1,2,3,…,9}的所有排列非常耗時，通過分析發現只要窮舉乘積的排列就可大大減少計算時間，即乘積范圍為1234～9876。進一步研究縮小乘積范圍，在(1)式中最小的乘積是1×2345＝2345，但1位數字因子不可能是1，那么最小的1位因子只可能大于等于2，因此構造另一個最小的乘積是2×1345＝2690，根據數字互不相同的規則容易得出，滿足等式的最小乘積至少大于3000；同理可知，23×145是(2)式中最小的因子組合，而其積3335也不滿足數字互不相同的規則，這也說明最小乘積至少大于3000，由于1或者2用于因子，那么最小乘積至少為3456。因此，進一步縮小乘積的范圍是3456～9876。

3 算法設計

（1）在3456至9876中按序取1數，如果已取完則執行（9）；

（2）所取數的4位數字用預處理判斷是否相異，否則執行（1）；

（3）所取數是否被2～9中某一數整除，否則執行（6）；

（4）商為4位數且9個數字相異，否則執行（6）；

（5）輸出一個解；

（6）所取數是否被12～98中某一數整除，否則執行（1）；

（7）商為3位數且9個數字相異，否則執行（1）；

（8）輸出一個解，執行（1）；

（9）結束。

4 算法實現

4.1 算法預處理

用預處理判斷乘積中4個數字是否重復，即在窮舉乘積的排列時，用預處理過濾掉乘積中有相同數字的乘積，減少搜索空間。

int judge1(int x)

{

int a,b,c,d;

a=x/1000;

b=x%1000/100;

c=x%100/10;

d=x%10;

if(d==0||b==0||c==0) return 0;

if(a==b||a==c||a==d) return 0;

else if(b==c||b==d||c==d) return 0;

else return 1;

}

4.2 判斷乘積等式是否符合條件

int judge2(int x,int y,int z)

{

int a,b,c,d; int a2,b2;

int a3,b3,c3,d3; a=x/1000;

b=x%1000/100; c=x%100/10; d=x%10; if(y<10) {

a2=y;

a3=z/1000;

b3=z%1000/100; c3=z%100/10;

d3=z%10;

b2=0;

if(b3==0||c3==0||d3==0)

return 0;

}

else

{

a2=y/10; b2=y%10; a3=z/100;

b3=z%100/10;

c3=z%10;

d3=0;

if(b3==0||c3==0||b2==0) return 0;

}

if(a==a3||a==b3||a==c3||a==d3||a==a2||a==b2) return 0;

else if(b==a3||b==b3||b==c3||b==d3||b==a2||b==b2) return 0;

else if(c==a3||c==b3||c==c3||c==d3||c==a2||c==b2) return 0;

else if(d==a3||d==b3||d==c3||d==d3||d==a2||d==b2) return 0;

else if(a2==a3||a2==b3||a2==c3||a2==d3) return 0;

else if(b2==a3||b2==b3||b2==c3||b2==d3) return 0;

else if(a3==b3||a3==c3||a3==d3) return 0;

else if(b3==c3||b3==d3||c3==d3) return 0;

else return 1;

}

4.3 乘積等式搜索for(i=3456;i<9877;i++)

{

if(judge1(i)==0)

continue;

for(j=2;j<10;j++)

{ if(i%j==0)

{

k=i/j;

if(k/1000==0)

continue; if(judge2(i,j,k)==0)

continue; tnum++;

printf("%d*%d=%d ",j,i/j,i);

}

}

for(j=12;j<99;j++)

{

if(j/10==j%10) continue; if(i%j==0)

{

k=i/j;

if(k/100==0)

continue; if(judge2(i,j,k)==0)

continue; tnum++;

printf("%d*%d=%d ",j,i/j,i);

}

}

}

printf("共有%d種 ",tnum);

5 實驗測試及結論

經過計算共得到如下9組解（與文獻[1]的解相同）：

28*157=4396；18*297=5346；27*198=5346;

12*483=5796；42*138=5796；4*1738=6952;

39*186=7254；48*159=7632；4*1963=7852；

由文獻[3]可知該算法的時間復雜度為O(n)。在操作系統xp和CPU為AMD 4600+(2.4G)的環境下用C語言實現，五次測試其平均值為8ms，由此可見本算法是高效的；通過檢驗本算法所得答案也是正確的。

[1]白宇.九位不同數字乘法等式的遞歸與非遞歸回溯算法[J].山西大同大學學報(自然科學版),2009,25(4):12-14.

[2]Aho Alfred,Ullman Jeffrey,Hopcroft et al.The design and analysis of computer algorithms[M].北京:機械工業出版社,2007.

[3]Levitin Anany,潘彥[譯].算法設計與分析基礎[M].北京:清華大學出版社,2004.

[4]姜華林.數獨問題高效算法的研究與實現[J].計算機光盤軟件與應用,2013(12):82-83.

An Efficient Algorithm for the Equation of Multiplication of Nine Different Single Numbers

Chen Yong
(Zunyi Vocational and Technical College,Zunyi 563000,Guizhou)

Based on the study of the equation of multiplication of nine different single numbers and according to conventional design for NP problem by exhaustive algorithm,the author introduces an optimized algorithm to solve the famous puzzle.It is improved that the algorithm is correct and efficient.

NP problem;exhaustive algorithm;optimized algorithm;efficient

TP302

A

1008-6609(2016)07-0046-03

陳勇，男，貴州遵義人，講師，研究方向：媒體制作與網站建設。