例18 火柴棒等式
用n根火柴棍，可以拼出多少個形如“A+B=C”的等式？等式中的A、B、C是用火柴棒拼出的整數（若該數非零，則最高位不能是0），用火柴棒拼數字0~9的拼法如圖1所示，
圖1 用火柴棒拼的數字0~9
另外，加號與等號各自需要兩根火柴棒，
撰寫一個程式，輸入火柴棒的根數n，輸出能拼成的不同等式的數目，說明：（1）如果A≠B，則A+B=C與B+A=C視為不同的等式（A、B、C>=0）；（2）A和B最多為3位數；（3）n根火柴棒必須全部用上，
例如，輸入18，輸出應為9，即18根火柴棒可以拼出0+4=4、0+11=11、1+10=11、2+2=4 、2+7=9、4+0=4、7+2=9、10+1=11、11+0=11這9個等式，
（1）編程思路1，
用一個陣列保存0~9每個數字所需火柴棒數，另外加號和等號需用去4根，
撰寫一個函式int needMatch(int num)用于統計數 num 需要的火柴棒個數，
程式中用二重回圈對A（0~999）和B（0~999）的取值組合進行窮舉，呼叫函式needMatch(A)、needMatch(B)和needMatch(A+B)分別回傳等式中三個數所需的火柴棒的數目，若needMatch(A)+needMatch(B)+needMatch(A+B)+4==n，則計數，
（2）源程式1，
#include <stdio.h>
int needMatch(int num); // 統計數 num 需要的火柴棒個數
int main()
{
int n,i,j,sum1,sum2,sum3,cnt;
scanf("%d",&n);
cnt=0;
for(i=0;i<1000;i++)
for(j=0;j<1000;j++) // 二重回圈列舉兩個加數
{
sum1=needMatch(i);
sum2=needMatch(j);
sum3=needMatch(i+j); // 分別求出兩個加數和一個和分別需要的火柴棒
if(sum1+sum2+sum3+4==n)
cnt++;
}
printf("%d\n",cnt);
return 0;
}
int needMatch(int num) // 統計數 num 需要的火柴棒個數
{
int table[10]={6,2,5,5,4,5,6,3,7,6};
int sum=0;
if(num==0) // 數0 特殊處理
return(6);
else
{
while(num!=0)
{
sum+=table[num%10]; // 分解出每一位并加上此位的火柴棒個數
num=num/10; // 準備處理下一位
}
return(sum);
}
}
（3）編程思路2，
編程思路1中呼叫一個函式needMatch來回傳每個數字num所需火柴棒數，在窮舉時，這個函式會被呼叫1000*1000*3=3000000（3百萬次），程式執行速度較慢，下面采用以空間換時間的方法，提高程式的執行速度，
由于等式中可能出現的數在0~1998之間，因此可以定義一個陣列int needmatch[1999]，保存拼出0~1998每個數字所需要的火柴棒數，needmatch[i]的值為拼出數字i所需的火柴棒數，這樣，先計算好陣列中的每個元素的值后，在對等式中數A和B進行窮舉時，等式中三個數所需的火柴棒數只需直接參考陣列元素的值即可，相當于思路1中的needMatch函式只呼叫了1999次，因此程式的運行速度會大大提高，
（4）源程式2，
#include <stdio.h>
int main()
{
int n,i,j,cnt;
int match[10]={6,2,5,5,4,5,6,3,7,6}; // 定義0~9每個數字所需要的火柴棒數
int needmatch[2000]; // 保存拼出0~1999每個數字所需要的火柴棒數
scanf("%d",&n);
for (i=0;i<=9;i++)
needmatch[i]=match[i];
for (i=10;i<2000;i++) // 計算10~1999中每個數需要的火柴棒數目
{
if (i<100) // 10~99 兩位數
needmatch[i]=match[i/10]+match[i%10];
else if (i<1000) // 100~999 三位數
needmatch[i]=match[i/100]+match[i/10%10]+match[i%10];
else // 1000~1999 四位數
needmatch[i]=match[i/1000]+match[i/100%10]+match[i/10%10]+match[i%10];
}
cnt=0;
for(i=0;i<1000;i++)
for(j=0;j<1000;j++) //二重回圈列舉兩個加數
if(needmatch[i]+needmatch[j]+needmatch[i+j]+4==n)
cnt++;
printf("%d\n",cnt);
return 0;
}
習題18
18-1 計數問題
本題選自洛谷題庫 （https://www.luogu.org/problem/P1980）
題目描述
試計算在區間 1 到 n的所有整數中，數字 x(0 ≤ x ≤ 9)共出現了多少次？例如，在 1到 11中，即在 1,2,3,4,5,6,7,8,9,10,11中，數字 1 出現了 4 次，
輸入格式
2個整數n,x，之間用一個空格隔開，
輸出格式
1個整數，表示x出現的次數，
輸入樣例
11 1
輸出樣例
4
（1）編程思路1，
定義一個陣列count[10]，元素count[0]~count[9]分別保存數字0~9在全部n個整數中用到的次數，初始值全為0，表示開始時每個數字均沒用到，
程式可以寫成一個回圈，框架為：
for （i=1； i<=n ；i++）
{
對每個整數i，依次分離出i的各位數字k，對應的count[k]++；
}
對于整數i，分離出各位數字的操作為：不斷除以10，記下余數，直到商為0，所得余數序列就是整數i從低位到高位的各位數字，具體描述為：
while (i)
{ count[ i %10] ++;
i=i/10;
}
（2）源程式1，
#include <stdio.h>
int main()
{
int n,i,t,x;
int count[10] = {0};
scanf("%d%d",&n,&x);
for(i = 1; i <= n; i++)
{
t = i;
while(t)
{
count[t%10]++; t/=10;
}
}
printf("%d\n",count[x]);
return 0;
}
（3）編程思路2，
程式1中n個整數各個數字的統計用一個二重回圈完成，外回圈處理n個整數，內回圈處理n的每位數字，n的數字位數為log10n+1，所以這個演算法的時間復雜度為O（n*log10n），
下面我們給出一種更高效解決這個問題的方法，
1）考察由0、1、2、…、9十個數字組成的所有n位數，從n個0到n個9共有10n個n位數，在這10n個n位數中，0、1、2、…、9這十個數字使用次數相同，設為f(n)，f(n)滿足如下遞推式：
2）對于一個m位整數，我們可以把0到n之間的n+1個整數從小到大這樣來排列：
000……0
…………
099……9
100……0
…………
199……9
…………
這樣一直排到自然數n，對于從0到099……9這個區間來說，拋去最高位的數字不看，其低m-1位恰好就是m-1個0到m-1個9共個數，利用上面的遞推公式，在這個區間里，每個數字出現的次數（不包括最高位數字）為，假設n的最高位數字是x，那么在n之間上述所說的區間共有x個，那么每個數字出現的次數x倍就可以統計完這些區間，再看最高位數字的情況，顯然0到x-1這些數字在最高位上再現的次數為，因為一個區間長度為；而x在最高位上出現次數就是，接下來對，即n去掉最高位后的那個數字再繼續重復上面的方法，直到個位，就可以完成各個數字的統計了，
比如，對于一個數字3482，我們可以這樣來計算從1到3482之間所有數字中每個數字出現的次數，
從0到999，這個區間的每個數字的出現次數可以使用前面給出的遞推公式，即每個數字出現400次，從1000到1999，中間除去千位的1不算，又是一個從000到999的排列，這樣的話，從0到3482之間的這樣的區間共有3個，所以從0000到2999之間除千位外，每個數字（0~9）出現次數均為3*400次，
然后再統計千位數字，每個區間長度為1000，所以0、1、2在千位上各出現1000次，而3則出現482+1=483次，
之后，拋掉千位數字，對于482，再使用上面的方法計算，一直計算到個位即可，
（4）源程式2，
#include <stdio.h>
#include <math.h>
int main()
{
int n,x,i,len,m,k,h;
int pow10[10] = {1}, count[10] = {0};
char d[11];
for(i = 1; i < 10; i++)
{
pow10[i] = pow10[i-1] * 10;
}
scanf("%d%d",&n,&x);
len = log10(n); // len 表示當前數字的位權,一個5位數，
// 最高位權為10的4次方，len=4
m = len;
sprintf(d, "%d", n); // 將數n 轉換為字串存入陣列d中
k = 0; // k 存盤當前最高位數字在d陣列中的下標
h = d[k] - '0'; // h 存盤當前最高位的數字
n %= pow10[len]; // 去掉n的最高位
while(len > 0)
{
if(h == 0) // 當前數字如果為0
{
count[0] += n + 1; h = d[++k] - '0';
len--; n %= pow10[len];
continue;
}
for(i = 0; i < 10; i++)
count[i] += h * len * pow10[len-1]; //
for(i = 0; i < h; i++) // 最高位0~h-1出現次數
count[i] += pow10[len];
count[h] += n + 1; // 最高位 h 出現次數
len--; h = d[++k] - '0';
n %= pow10[len]; // n 拋掉最高位
}
for(i = 0; i <= h; i++) // 個位上0~h出現次數
count[i] += 1;
for(i = 0; i <= m; i++) // 減去前導0的個數
count[0] -= pow10[i];
printf("%d\n",count[x]);
return 0;
}
18-2 三連擊
本題選自洛谷題庫 （https://www.luogu.org/problem/P1008）
題目描述
將1,2,?,9共9個數分成3組，分別組成3個三位數，且使這3個三位數構成1:2:3的比例，試求出所有滿足條件的3個三位數，
輸入格式
沒有輸入
輸出格式
若干行，每行3個數字，按照每行第1個數字升序排列，
輸入樣例
無
輸出樣例
192 384 576
* * *
...
* * *
（輸出被和諧了）
（1）編程思路1，
三個三位數，一共9個位，可以將每一個數位為列舉物件，一位一位地去列舉，
定義9個整型變數A、B、C、D、E、F、G、H、I分別表示三個數的9個位，每個變數取1~9之間的一個值，如ABC表示第1個數x、DEF表示第2個數y，GHI表示第3個數z，
根據A~I的具體取值，可以計算x、y、z，三個數需要滿足條件2*x==y && 3*x==z（構成1：2：3的比例）；另外，還得考慮A~I各個數位的數字取值不相同，為確保9個變數取值各不相同，只要同時滿足A+B+C+D+E+F+G+H+I==45（1+2+3+4+5+6+7+8+9=45）和A*B*C*D*E*F*G*H*I==362880（1*2*3*4*5*6*7*8*9=362880）即可，
（2）源程式1，
#include <stdio.h>
int main()
{
int a,b,c,d,e,f,g,h,i,x,y,z;
for (a=1;a<=9;a++)
for (b=1;b<=9;b++)
for (c=1;c<=9;c++)
for (d=1;d<=9;d++)
for (e=1;e<=9;e++)
for (f=1;f<=9;f++)
for (g=1;g<=9;g++)
for (h=1;h<=9;h++)
for (i=1;i<=9;i++)
{
x=a*100+b*10+c;
y=d*100+e*10+f;
z=g*100+h*10+i;
if (a+b+c+d+e+f+g+h+i==45 && a*b*c*d*e*f*g*h*i==362880
&& 2*x==y && 3*x==z)
printf("%d %d %d\n",x,y,z);
}
return 0;
}
（3）編程思路2，
按程式1的思路，窮舉次數有99次，如果分別設三個數為x、2x和3x，以x為列舉物件，則x的最小值為123、最大值為329（因為下一個數341*3=1023>987），窮舉的范圍就減少為107，
由于對x進行窮舉，因此需要將3個三位數的各個位上的數字分離出來，這9個數字可以像程式1中一樣，用A~I這9個變數來保存，在程式2中，我們采用另外一種方法，定義一個一維陣列a[9]，把組成整數x、2x、3x的9個數字存放在陣列a中，然后用一個二重回圈統計1~9這9個數字是否全在陣列中出現，
（4）源程式2，
#include <stdio.h>
int main()
{
int a[9],x,cnt,i,j,flag;
for (x=123;x<=329;x++) // 列舉所有可能的解
{ // 把組成整數x、2x、3x的9個數字存放在陣列a中
a[0]=x/100; a[1]=x/10%10; a[2]=x%10;
a[3]=(2*x)/100; a[4]=(2*x)/10%10; a[5]=(2*x)%10;
a[6]=(3*x)/100; a[7]=(3*x)/10%10; a[8]=(3*x)%10;
cnt=0;
for (i=1;i<=9;i++) // 檢查1~9這9個數字是否都在a中
{
flag=-1;
for (j=0;j<9;j++)
if (i==a[j])
{ flag=j; break; }
if (flag!=-1)
cnt++;
else
break; // 如果有數字不在a中，則退出回圈
}
if (cnt==9)
printf("%d %d %d\n",x,x*2,x*3);
}
return 0;
}
18-3 三連擊（升級版）
本題選自洛谷題庫 （https://www.luogu.org/problem/P1618）
題目描述
將1，2，…，9共9個數分成三組，分別組成三個三位數，且使這三個三位數的比例是A:B:C，試求出所有滿足條件的三個三位數，若無解，輸出“No!!!”，
輸入格式
三個數，A B C（A<B<C），
輸出格式
若干行，每行3個數字，按照每行第一個數字升序排列，
輸入樣例
1 2 3
輸出樣例
192 384 576
219 438 657
273 546 819
327 654 981
（1）編程思路，
分別設三個數為x1、x2和x3，以x1為列舉物件，計算出x2和x3（x2=b*x1/a; x3=c*x1/a），且x1的最小值為123、最大值為987*a/c（x3最大為987），
由于對x1進行窮舉，因此需要判斷1~9這9個數字是否全在x1、x2和x3這三個數中出現，為此定義一個陣列hash[10]，其中hash[i]的值代表數字i（0<=i<=9）在3個三位數中出現的次數，每次窮舉前hash陣列的元素值全為0，若窮舉某個x1時，hash[1]~hash[9]的值全為1，則表示1~9這9個數字全在三個數中出現了，得到一組解，
（2）源程式，
#include <stdio.h>
int main()
{
int hash[10],x1,x2,x3,a,b,c,i,flag=0;
scanf("%d%d%d",&a,&b,&c);
for (x1=123;x1<=987*a/c;x1++) // 列舉所有可能的解
{
for (i=0;i<=9;i++) hash[i]=0;
x2=b*x1/a; x3=c*x1/a;
hash[x1/100]++; hash[x1/10%10]++; hash[x1%10]++;
hash[x2/100]++; hash[x2/10%10]++; hash[x2%10]++;
hash[x3/100]++; hash[x3/10%10]++; hash[x3%10]++;
for (i=1;i<=9;i++) // 檢查1~9這9個數字是否都出現
if (hash[i]!=1) break;
if (i>9)
{
printf("%d %d %d\n",x1,x2,x3);
flag=1;
}
}
if (flag==0) printf("No!!!\n");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/61763.html
標籤：C