65.乘式還原(2)
有乘法算式如下：
○○○
× ○○
------------
○○○○
○○○○
------------
○○○○○
18個(gè)○的位置上全部是素?cái)?shù)(1、3、5或7)，請(qǐng)還原此算式。
*問題分析與算法設(shè)計(jì)
問題中雖然有18數(shù)位，但只要確定乘數(shù)和被乘數(shù)后經(jīng)過計(jì)算就可確定其它的數(shù)位。
乘數(shù)和被乘數(shù)共有5個(gè)數(shù)位，要求每個(gè)數(shù)都是質(zhì)數(shù)。完全可以采用窮舉的方法對(duì)乘數(shù)和被乘數(shù)進(jìn)行窮舉，經(jīng)過判斷后找出答案。但是這種方法給人的感覺是“太笨了”，因?yàn)榻M成的數(shù)字只是質(zhì)數(shù)(4個(gè))，完全沒有必要在那么大的范圍內(nèi)進(jìn)行窮舉，只需要試探每一位數(shù)字為質(zhì)數(shù)時(shí)的情況即可。
采用五重循環(huán)的方法實(shí)現(xiàn)對(duì)于5個(gè)數(shù)字的窮舉，前面的許多例題中都已見過。循環(huán)實(shí)現(xiàn)簡(jiǎn)單易行，但嵌套的層次太多，需要窮舉的變量的數(shù)量直接影響到循環(huán)嵌套的層數(shù)，這種簡(jiǎn)單的實(shí)現(xiàn)方法缺少技巧性。本例的程序中給出了另外一種同樣功能的算法，該算法的實(shí)現(xiàn)思想請(qǐng)閱讀程序。
程序中并沒有直接對(duì)質(zhì)數(shù)進(jìn)行窮舉，而是將每個(gè)質(zhì)數(shù)與1到4順序一一對(duì)應(yīng)，在窮舉時(shí)為處理簡(jiǎn)單僅對(duì)1到4進(jìn)行窮舉處理，待要判斷產(chǎn)生的乘積是否滿足條件時(shí)再利用一個(gè)數(shù)組完成向?qū)?yīng)質(zhì)數(shù)的轉(zhuǎn)換。請(qǐng)?bào)w會(huì)程序中的處理方法。程序中使用的算法實(shí)際上是回朔法。
*程序與程序注釋
#include
#define NUM 5 /*需要窮舉的變量數(shù)目*/
#define C_NUM 4 /*每個(gè)變量的值的變化范圍*/
int a[NUM+1]; /*為需要窮舉的變量開辟的數(shù)組*/
/*a[1]:被乘數(shù)的百位，a[2]：十位,aa[3]:個(gè)位 a[4]:被乘數(shù)的十位 a[5]:個(gè)位*/
int b[]={0,2,3,5,7}; /*存放質(zhì)數(shù)數(shù)字的數(shù)組，不使用第0號(hào)元素*/
int f(long sum);
void main()
{
int i,not_finish=1;
i=2; /*i:將要進(jìn)行處理的元素的指針下標(biāo)。設(shè)置初始值*/
a[1]=1; /*為第1號(hào)元素設(shè)置初始值*/
while(not_finish) /*not_finish:程序運(yùn)行沒結(jié)束標(biāo)記*/
{
while(not_finish&&i<=NUM)
/*處理包括第i個(gè)元素在內(nèi)的后續(xù)元素，找出當(dāng)前條件下的一種各個(gè)變量的一種可能的取值方法*/
if(a[i]>=C_NUM) /*當(dāng)要處理的元素取超過規(guī)定的C_NUM時(shí)*/
if(i==1&&a[1]==C_NUM)
not_finish=0; /*若1號(hào)元素已經(jīng)到C_NUM，則處理全部結(jié)束*/
else a[i--]=0; /*將要處理的元素置0，下標(biāo)-1(回退一個(gè)元素)*/
else a[i++]++; /*當(dāng)前元素值加1后下標(biāo)指針加1*/
if(not_finish)
{
long int sum1,sum2,sum3,sum4; /*定義臨時(shí)變量*/
sum1=b[a[1>*100+b[a[2>*10+b[a[3>; /*計(jì)算被乘數(shù)*/
/*利用數(shù)組的下標(biāo)與質(zhì)數(shù)的對(duì)應(yīng)關(guān)系完成序號(hào)1到4向質(zhì)數(shù)的轉(zhuǎn)換*/
sum2=sum1*b[a[5>; /*計(jì)算乘數(shù)個(gè)位與被乘數(shù)的部分積*/
sum3=sum1*b[a[4>; /*計(jì)算乘數(shù)十位與被乘數(shù)的部分積*/
if(sum2>=2222&&sum2<=7777&&f(sum2)&&sum3>=2222&&sum3<=7777&&f(sum3))
/*判斷兩部分積是否滿足題目條件*/
if((sum4=sum2+sum3*10)>=22222&&sum4<=77777&&f(sum4))
/*判斷乘式的積是否滿足題目條件*/
{
printf(" %d\n",sum1); /*若滿足題意，則打印結(jié)果*/
printf("* %d%d\n",b[a[4>,b[a[5>);
printf("........................\n");
printf(" %d\n",sum2);
printf(" %d\n",sum3);
printf("........................\n");
printf(" %d\n",sum4);
}
i=NUM; /*為窮舉下一個(gè)可能取值作準(zhǔn)備*/
}
}
}
int f(long sum) /*判斷sum的每一位數(shù)字是否是質(zhì)數(shù)，若不是返回0，若是返回1*/
{
int i,k,flag; /*flag=1:數(shù)字是質(zhì)數(shù)的標(biāo)記*/
while(sum>0)
{
i=sum; /*取個(gè)位的數(shù)字*/
for(flag=0,k=1;!flag&&k<=C_NUM;k++)
if(b[k]==i)
{
flag=1;break;
}
if(!flag) return 0;
else sum=sum/10;
}
return 1;
}
*運(yùn)行結(jié)果
7 7 5
× 3 3
----------
2 3 2 5
2 3 2 5
-----------
2 5 5 7 5
*思考題
以下乘式中，A、B、C代表一確定的數(shù)字，○代表任意數(shù)字，請(qǐng)復(fù)原。
A B C 2 8 6
× B A C × 8 2 6
------------- 答案： ------------
○○○○ 1 7 1 6
○○A 5 7 2
○○○B(yǎng) 2 2 8 8
------------- ----------------
○○○○○○ 2 3 6 2 3 6