例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=https://www.cnblogs.com/cs-whut/p/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=https://www.cnblogs.com/cs-whut/p/value+preVal;
else
value=https://www.cnblogs.com/cs-whut/p/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=https://www.cnblogs.com/cs-whut/p/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=https://www.cnblogs.com/cs-whut/p/value+preVal;
else
value=https://www.cnblogs.com/cs-whut/p/value-preVal;
preCalc=a[i];
preVal=a[i+1];
}
}
preVal=preVal*10+a[19];
if (preCalc==1)
value=https://www.cnblogs.com/cs-whut/p/value+preVal;
else
value=https://www.cnblogs.com/cs-whut/p/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=https://www.cnblogs.com/cs-whut/p/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=https://www.cnblogs.com/cs-whut/p/value+preVal;
else
value=https://www.cnblogs.com/cs-whut/p/value-preVal;
preCalc=a[i];
preVal=a[i+1];
}
}
if (preCalc==1)
value=https://www.cnblogs.com/cs-whut/p/value+preVal;
else
value=https://www.cnblogs.com/cs-whut/p/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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/61756.html
標籤：C