例16 巧解算式 問題描述 在1、2、3、4、5、6、7、8、9、10個數中間加上加號或減號，使得到的表達式的值為自然數N，如果中間沒有符號，則認為前後為一個數，如1 2 3認為是一百二十三（123）。 例如：當N=100時，表達式值為100的填法有24種。123+4+5+67-89-10=100是 ...
例16 巧解算式
問題描述
在1、2、3、4、5、6、7、8、9、10個數中間加上加號或減號，使得到的表達式的值為自然數N，如果中間沒有符號，則認為前後為一個數，如1 2 3認為是一百二十三（123）。
例如：當N=100時，表達式值為100的填法有24種。123+4+5+67-89-10=100是一種填法，1+2+3+4+56+7+8+9+10=100也是一種填法。
編寫一個程式，找出使表達式的值等於N的填寫方法有多少種？
輸入格式
輸入包含多組測試數據。每組測試數據一個自然數n，占據獨立一行。0表示輸入結束。
輸出格式
對每組測試數據，輸出一行，即使表達式的值等於n的填寫方法的種數。
輸入樣例
1
10
100
0
輸出樣例
45
26
24
（1）編程思路。
為了表示等式左邊的算式，可以定義一個數組int a[20]，其中元素a[0]、a[2]、…、a[16]分別保存數字1、2、…、9，a[18]和a[19]合起來保存數10。a[1]、a[3]、…、a[17]用0、1、2保存可能填寫的運算符，其中0代表空格、1代表加號+、2代表減號 -。如下所示：
|
1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
1 |
0 |
這樣，可以用一個9重迴圈對9個空位可能填寫的3種算符進行窮舉，得到等式左邊的算式，保存在數組a[20]中，然後對這個算式進行解析，若運算結果為N，則就是一種解法。
程式中將算式的解析編寫成一個函數，原型為int Parse(int a[]); 。
解析時，從左到右對數組進行掃描。初始時，算式值value=0，應進行運算的算符preCalc=1（這樣當掃描到第一個加或減運算符時，value（0）加上算符前的數值就是第1個算符前的數，從而可進行迴圈處理），當前參與運算的數preVal初始為a[0]。
用迴圈對a[1]、a[3]、…、a[17]這9個位置填寫情況進行處理，分兩種情況：
1）填寫的是空格，則前面的數（保存在preVal中）和後面的一個數字構成一個數，如1和2之間是空格，則1和2構成12，若“2”後面又是一個空格，則“12”和“3”構成123。處理方法為 preVal=preVal*10+a[i+1];
2）填寫的是加號或減號。則進行前面的運算（保存在應進行運算的算符preCalc中，註意不是當前的加法或減法運算，當前的加號或減號的運算需等到掃描到下一個加或減運算符時才進行）。若preCale==1，則進行加法，若preCale==2，則進行減法。之後，將當前的算符保存到preCale中，並將算符後的一個數字保存到參與運算的數preVal中。
if (preCalc==1)
value=value+preVal;
else
value=value-preVal;
preCalc=a[i];
preVal=a[i+1];
（2）源程式。
#include <stdio.h>
int Parse(int a[]);
int main()
{
int a[20]={1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,0,1,0};
// 數組a中a[1]、a[3]、…、a[17]用0、1、2保存可能的運算符
// 其中，0代表空格，1代表加號+、2代表減號-
int n;
while (scanf("%d",&n) && n!=0)
{
int a1,a2,a3,a4,a5,a6,a7,a8,a9,num=0;
for(a1=0;a1<3;a1++)
for(a2=0;a2<3;a2++)
for(a3=0;a3<3;a3++)
for(a4=0;a4<3;a4++)
for(a5=0;a5<3;a5++)
for(a6=0;a6<3;a6++)
for(a7=0;a7<3;a7++)
for(a8=0;a8<3;a8++)
for(a9=0;a9<3;a9++)
{
a[1]=a1; a[3]=a2; a[5]=a3;
a[7]=a4; a[9]=a5; a[11]=a6;
a[13]=a7; a[15]=a8; a[17]=a9;
if (Parse(a)==n)
{
num++;
}
}
printf("%d\n",num);
}
return 0;
}
int Parse(int a[])
{
int value=0,i,preVal,preCalc;
preVal=a[0]; preCalc=1;
for(i=1;i<=17;i=i+2)
{
switch (a[i])
{
case 0: preVal=preVal*10+a[i+1];
break;
case 1:
case 2: if (preCalc==1)
value=value+preVal;
else
value=value-preVal;
preCalc=a[i];
preVal=a[i+1];
}
}
preVal=preVal*10+a[19];
if (preCalc==1)
value=value+preVal;
else
value=value-preVal;
return value;
}
習題16
16-1 零的數列 Zero Sum
本題選自洛谷題庫（https://www.luogu.org/problem/P1473）
題目描述
考慮一個由1到N（N=3, 4, 5 ... 9）的數字組成的遞增數列：1 2 3 ... N。 現在在數列中插入“+”表示加，或者“-”表示減，“ ”表示空白(例如1-2 3就等於1-23)，來將每一對數字組合在一起（請不要在第一個數字前插入符號）。 計算該表達式的結果並判斷其值是否為0。 請你寫一個程式找出所有產生和為零的長度為N的數列。
輸入格式
單獨的一行表示整數N (3 <= N <= 9)。
輸出格式
按照ASCII碼的順序，輸出所有在每對數字間插入“+”, “-”, 或 “ ”後能得到結果為零的數列。
輸入樣例
7
輸出樣例
1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7
（1）編程思路。
弄懂了例16的編程思路，適當變化可以解決本習題。
同樣定義數組 int a[17]={1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9};
數組a中，a[1]、a[3]、…、a[15]用0、1、2保存可能的運算符。其中，0代表空格、1代表加號+、2代表減號-。
本題關鍵是解決如何給a[1]、a[3]、…a[2*n-3]這n-1個元素賦以0、1、2這三種算符構成的全排列。
以n=3為例，應該在a[1]和a[3]處賦兩種算符。全排列為：00、01、02、10、11、12、20、21、22共9種。
編寫如下的遞歸函數可以生成在0、1、2中任取n-1個數字構成的全排列（可重覆取某個數字），並賦給相應的a[1]、a[3]、…a[2*n-3]這n-1個元素。
void dfs(int a[], int pos,int n)
{
if(pos == 2*n-1) // 已賦了N-1個位置的算符
{
// 對生成的表達式進行解析，看結果是否為0，若為0，輸出該表達式
return;
}
for(int i = 0;i <= 2;i++)
{
a[pos] = i;
dfs(a,pos+2,n); // 給下一位置賦算符
}
}
表達式生成後，其解析方式也如同例16的思路，只是本題中解析到a[2*n-2]為止。
（2）源程式。
#include <stdio.h>
int Parse(int a[],int n);
void dfs(int a[], int pos,int n);
int main()
{
int a[17]={1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9};
// 數組a中a[1]、a[3]、…、a[15]用0、1、2保存可能的運算符
// 其中，0代表空格、1代表加號+、2代表減號-
int n;
scanf("%d",&n);
dfs(a,1,n);
return 0;
}
void dfs(int a[], int pos,int n)
{
if(pos == 2*n-1) // 已賦了N-1個位置的算符
{
if (Parse(a,n)==0)
{
char b[3]={' ','+','-'};
for(int i=0;i<2*n-2;i++)
if (i%2==0) printf("%d",a[i]);
else printf("%c",b[a[i]]);
printf("%d\n",a[2*n-2]);
}
return;
}
for(int i = 0;i <= 2;i++)
{
a[pos] = i;
dfs(a,pos+2,n);
}
}
int Parse(int a[],int n)
{
int value=0,i,preVal,preCalc;
preVal=a[0]; preCalc=1;
for(i=1;i<2*n-1;i=i+2)
{
switch (a[i])
{
case 0: preVal=preVal*10+a[i+1];
break;
case 1:
case 2: if (preCalc==1)
value=value+preVal;
else
value=value-preVal;
preCalc=a[i];
preVal=a[i+1];
}
}
if (preCalc==1)
value=value+preVal;
else
value=value-preVal;
return value;
}
16-2 填數字游戲
問題描述
設有等式ABCD*E=DCBA，A、B、C、D、E代表的數字各不相同，編程求A、B、C、D、E。
輸入樣例
無輸入
輸出樣例
2178*4=8712
（1）編程思路1
直接對a（1<=a<=4）、b（0<=b<=9）、c（0<=c<=9）、d（1<=d<=9）、e（2<=e<=9）五個數字的各種取值情況進行窮舉，用s表示四位數ABCD（即s=1000*a+100*b+10*c+d）、k表示四位數DCBA（即k=a+10*b+100*c+1000*d），若滿足s*e==k且a、b、c、d、e互不相等（即a!=b && a!=c && a!=d && a!=e && b!=c && b!=d && b!=e && c!=d && c!=e && d!=e），則找到問題的解。
（2）源程式1。
#include <stdio.h>
int main()
{
int a,b,c,d,e,s,k;
for(a=1;a<=4;a++)
for (b=0;b<=9;b++)
for(c=0;c<=9;c++)
for(d=1;d<=9;d++)
for (e=2;e<=9;e++)
{
s=1000*a+100*b+10*c+d;
k=a+10*b+100*c+1000*d;
if(s*e==k && a!=b && a!=c && a!=d && a!=e
&& b!=c && b!=d && b!=e && c!=d && c!=e && d!=e)
{
printf("%d*%d=%d\n",s,e,k);
}
}
return 0;
}
（3）編程思路2
由於等式中ABCD是一個四位數，最高位A在1~4之間，且各位數字互不相等，因此，可以在1023~4987之間窮舉找到滿足條件的四位數。
為判斷四位數ABCD的各位數字和數字E均互不相等，編寫一個函數int isRepeat(int n,int e)，若整數n的各位數字和整數e均互不相等，函數返回值1，否則返回0。判斷方法是：定義一個一維數組b[10]，用於保存0~9各個數字出現的次數，將整數n的各位數字分解出來，每分解出一個數字i，對應的數組元素b[i]加1，數字e對應的數組元素b[e]也加1，然後統計數組b中值為1的元素個數cnt，若cnt等於整數n的位數加1，則每個數字出現一次，即各個數字互不相等，函數返回1。
由於等式中四位數DCBA是ABCD的逆序數，因此編寫一個函數int reversenum(int n)用於求整數n的逆序數。
（4）源程式2。
#include <stdio.h>
int isRepeat(int n,int e);
int reversenum(int n);
int main()
{
int i,j,k;
for(i=1023;i<=4987;i++)
{
for (j=2;j<=9;j++)
{
if (isRepeat(i,j)==1) continue;
k=reversenum(i);
if (i*j==k)
printf("%d*%d=%d\n",i,j,k);
}
}
return 0;
}
int isRepeat(int n,int e)
{
int m=0,b[10]={0},i,cnt;
while (n!=0)
{
i=n%10; b[i]++;
n=n/10; m++;
}
b[e]++;
cnt=0;
for(i=0;i<=9;i++)
if(b[i]!=0) cnt++;
if(cnt!=m+1) return 1;
else return 0;
}
int reversenum(int n)
{
int m=0;
while(n!=0)
{
m=m*10+n%10;
n=n/10;
}
return m;
}
按編程思路2編寫的程式，比編程思路1靈活多了。如題目改為設有等式ABCDE*F=EDCBA，A、B、C、D、E、F代表的數字各不相同，編程求A、B、C、D、E、F。只需將程式中的窮舉範圍改變即可。
將程式中的語句“for(i=1023;i<=4987;i++) ”改寫為“for(i=10234;i<=49876;i++)”，重新編譯並執行以上程式，得到如下所示的結果。
21978*4=87912
16-3 馬虎的算式
問題描述
小明是個急性子，上小學的時候經常把老師寫在黑板上的題目抄錯了。有一次，老師出的題目是：36 x 495 = ? 他卻給抄成了：396 x 45 = ? 但結果卻很戲劇性，他的答案竟然是對的！因為 36 * 495 = 396 * 45 = 17820
類似這樣的巧合情況可能還有很多，比如：27 * 594 = 297 * 54。
假設a、b、c、d、e 代表1~9不同的5個數字（註意是各不相同的數字，且不含0），能滿足形如：ab * cde = adb * ce 這樣的算式一共有多少種呢？
輸入格式
一個正整數n（5≤n≤9），表示a、b、c、d、e 代表1~n不同的5個數字。
輸出格式
一個整數，表示滿足形如 ab * cde = adb * ce 這樣的算式的種數。
輸入樣例
9
輸出樣例
142
（1）編程思路1。
本題關鍵是窮舉a、b、c、d、e在1~n之間取5個不同數所構成的全排列。
定義一個數組int num[6]，其中num[1]~num[5]五個元素分別表示a、b、c、d、e的取值。定義一個數組int visit[10]={0}標記數字是否出現，如visit[3]=1表示數字3已被使用，visit[3]=0表示數字3還未被使用。編寫如下的遞歸函數可以生成1~n中任取5個數字構成的全排列。
void dfs(int num[], int pos,int n, int visit[])
{
if(pos ==6) // 已有5個數
{
for (int i=1;i<6;i++)
printf(“%d ”,num[i]);
printf(“\n”);
return;
}
For (int i = 0 ;i <= n;i++)
{
if(!visit[i])
{
num[pos] = i;
visit[i] = 1;
dfs(num,pos+1,n,visit);
visit[i] = 0;
}
}
}
生成1~n不同的5個數字存儲到數組中後，檢測對應算式ab*cde == adb*ce是否成立，如果成立，是一組解，輸出並計數。
（2）源程式1。
#include <stdio.h>
int cnt=0;
void dfs(int num[], int pos,int n,int visit[])
{
if(pos == 6) // 已有5個數
{
int ab = num[1]*10 + num[2];
int cde = num[3]*100 + num[4]*10 + num[5];
int adb = num[1]*100 + num[4]*10 + num[2];
int ce = num[3]*10 + num[5];
if(ab*cde == adb*ce)
{
cnt++;
}
return;
}
for(int i = 1;i <= n;i++)
{
if(!visit[i])
{
num[pos] = i; visit[i] = 1;
dfs(num,pos+1,n,visit);
visit[i] =0;
}
}
}
int main()
{
int num[6],n;
int visit[10];
scanf("%d",&n);
for (int i=1;i<=9;i++)
visit[i]=0;
dfs(num,1,n,visit);
printf("%d\n",cnt);
return 0;
}
當然，本題不用遞歸，採用迴圈進行窮舉也能很方便地解決。編寫的迴圈窮舉程式如下源程式2所示。
（3）源程式2。
#include <stdio.h>
int main()
{
int n;
scanf("%d",&n);
int a,b,c,d,e,cnt=0;
for(a = 1; a <= n;a++)
for(b = 1; b <= n;b++)
for(c = 1; c <= n;c++)
for(d = 1; d <= n;d++)
for(e = 1; e <=n;e++)
{
int ab = 10*a + b;
int cde = 100*c + 10*d + e;
int adb = 100*a + 10*d + b;
int ce = 10*c + e;
if(ab*cde != adb*ce)
continue;
int num[10],i;
for (i=1;i<=9;i++)
num[i]=0;
num[a]++; num[b]++; num[c]++;
num[d]++; num[e]++;
for(i = 1;i <= 9;i++)
if(num[i] > 1) break;
if(i == 10)
{
cnt++;
}
}
printf("%d\n",cnt);
return 0;
}
