陳勇

(遵義職業(yè)技術(shù)學(xué)院，貴州 遵義 563000)

九位不同數(shù)字乘法等式的優(yōu)化算法

陳勇

(遵義職業(yè)技術(shù)學(xué)院，貴州 遵義 563000)

對(duì)“九位不同數(shù)字構(gòu)成乘法等式”的問題進(jìn)行研究分析，深入探討其解決方案，根據(jù)NP問題窮舉算法設(shè)計(jì)的常規(guī)思路，設(shè)計(jì)了一種更加優(yōu)化的窮舉算法，實(shí)驗(yàn)證明該算法是正確高效的。

NP問題；窮舉算法；優(yōu)化算法；高效

1 引言

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

2 問題分析

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

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

3 算法設(shè)計(jì)

（1）在3456至9876中按序取1數(shù)，如果已取完則執(zhí)行（9）；

（2）所取數(shù)的4位數(shù)字用預(yù)處理判斷是否相異，否則執(zhí)行（1）；

（3）所取數(shù)是否被2～9中某一數(shù)整除，否則執(zhí)行（6）；

（4）商為4位數(shù)且9個(gè)數(shù)字相異，否則執(zhí)行（6）；

（5）輸出一個(gè)解；

（6）所取數(shù)是否被12～98中某一數(shù)整除，否則執(zhí)行（1）；

（7）商為3位數(shù)且9個(gè)數(shù)字相異，否則執(zhí)行（1）；

（8）輸出一個(gè)解，執(zhí)行（1）；

（9）結(jié)束。

4 算法實(shí)現(xiàn)

4.1 算法預(yù)處理

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

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 實(shí)驗(yàn)測(cè)試及結(jié)論

經(jīng)過計(jì)算共得到如下9組解（與文獻(xiàn)[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；

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

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

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

[3]Levitin Anany,潘彥[譯].算法設(shè)計(jì)與分析基礎(chǔ)[M].北京:清華大學(xué)出版社,2004.

[4]姜華林.數(shù)獨(dú)問題高效算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)光盤軟件與應(yīng)用,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

陳勇，男，貴州遵義人，講師，研究方向：媒體制作與網(wǎng)站建設(shè)。