2015 年蓝桥杯 C 语言 B 组省赛第 3 题: 三羊献瑞 (三种方法 + 详细分析)
赞
踩
本文由荒原之梦原创，原文链接：http://zhaokaifeng.com/?p=1366
题目
三羊献瑞
观察下面的加法算式：
祥 瑞 生 辉
+ 三 羊 献 瑞
-------------------
三 羊 生 瑞 气
- 1
- 2
- 3
- 4
(如果有对齐问题，可以参看【图1.jpg】)
其中，相同的汉字代表相同的数字，不同的汉字代表不同的数字。
请你填写“三羊献瑞”所代表的4位数字（答案唯一），不要填写任何多余内容。
图 1
题目分析
将这八个汉字分别用字母 a~h 和数组 aa[0]~aa[7] 对应表示如下:
三 -> a -> aa[0]
羊 -> b -> aa[1]
献 -> c -> aa[2]
瑞 -> d -> aa[3]
祥 -> e -> aa[4]
生 -> f -> aa[5]
辉 -> g -> aa[6]
气 -> h -> aa[7]
换算成题目中的形式分别是:
e d f g
+ a b c d
-------------------
a b f d h
- 1
- 2
- 3
- 4
和
aa[4] aa[3] aa[5] aa[6]
+ aa[0] aa[1] aa[2] aa[3]
-------------------------------
aa[0] aa[1] aa[5] aa[3] aa[7]
- 1
- 2
- 3
- 4
这里之所以要分别使用字母和数组表示一个汉字是因为下面提到的三种方法要用到.
本题的要求可以总结如下:
- 每个汉字对应的数字都是不同的.
- a~h 这 8 个字母 (或者说 8 个数组元素) 的取值范围是从 0 到 9 十个数字.
- 其中 a (aa[0]) 不能等于 0, e (aa[4]) 也不能等于 0.
- 要求填入的结果是"三羊献瑞"所代表的四位数字, 而不是一共有多少种组合方式 (根据题意可知满足题目条件的组合方式只有一种).
解法一
这个解法基于 C++ 标准函数库 STL 中的 next_permutation() 全排列函数进行. 对 0~9 十个数字进行全排列, 取每次排列的前 8 个代入公式进行计算并检验是否满足要求. 由于进行的是全排列, 所以数组 aa[] 的前 8 个元素都有机会包含 0~9 这 10 个数字.
代码如下:
#include<iostream> #include<bits/stdc++.h> using namespace std; int main(){ int aa[10]={0,1,2,3,4,5,6,7,8,9}; int sum=0; int sum1=0; int sum2=0; int ans=0; while(next_permutation(aa,aa+10)){ if(aa[0]!=0&&aa[4]!=0){ sum1=aa[4]*1000+aa[3]*100+aa[5]*10+aa[6]; sum2=aa[0]*1000+aa[1]*100+aa[2]*10+aa[3]; sum=aa[0]*10000+aa[1]*1000+aa[5]*100+aa[3]*10+aa[7]; if(sum==(sum1+sum2)){ break; } } } cout<<"祥瑞生辉:"<<endl; cout<<" "<<sum1<<endl; cout<<"三羊献瑞:"<<endl; cout<<" "<<sum2<<endl; cout<<"三羊生瑞气:"<<endl; cout<<sum<<endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
正确答案:
1085
解法二
这个解法的思路和解法一类似, 只不过不使用 STL 提供的 next_permutation() 全排列函数, 而改用 8 个 for 循环进行暴力破解.
代码如下:
#include<iostream> #include<bits/stdc++.h> int main(){ int sum, sum1, sum2; for(int a=1;a<=9;a++){ //a 不能等于 0 for(int b=0;b<=9;b++){ if(b!=a){ for(int c=0;c<=9;c++){ if(c!=a&&c!=b){ for(int d=0;d<=9;d++){ if(d!=a&&d!=b&&d!=c){ for(int e=1;e<=9;e++){ //e 不能等于 0 if(e!=a&&e!=b&&e!=c&&e!=d){ for(int f=0;f<=9;f++){ if(f!=a&&f!=b&&f!=c&&f!=d&&f!=e){ for(int g=0;g<=9;g++){ if(g!=a&&g!=b&&g!=c&&g!=d&&g!=e&&g!=f){ for(int h=0;h<=9;h++){ if(h!=a&&h!=b&&h!=c&&h!=d&&h!=e&&h!=f&&h!=g){ sum1=e*1000+d*100+f*10+g; sum2=a*1000+b*100+c*10+d; sum=a*10000+b*1000+f*100+d*10+h; if(sum==(sum1+sum2)){ printf("%d\n",sum2); } } } } } } } } } } } } } } } } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
正确答案:
1085
为了进一步验证结果的正确性, 也可以将 8 个汉字对应的结果都输出数来. 由于解法一中已经这么做, 这里就不再加入输出全部计算结果的代码. 输出全部计算结果后需要注意的是, 看清题意和计算结果, 不要误提交不符合题目要求的答案.
解法三
这个解法用到了一些数学原理, 可以减少 for 循环的个数, 能够提高计算效率. 虽然对于填空题而言没必要考虑计算效率的问题, 但是这也是一种计算方式, 有必要尝试一下.
首先, 我们看一下这个式子:
e d f g
+ a b c d
-------------------
a b f d h
- 1
- 2
- 3
- 4
两个四位数相加得出了一个五位数, 根据加法中"满十进一"的法则, 五位数的最高位一定是 1, 即:
a=1
- 1
于是, 原式就变成了:
e d f g
+ 1 b c d
-------------------
1 b f d h
- 1
- 2
- 3
- 4
这样我们就可以去掉对 a 的 for 循环, 对解法二中的代码进行一下修改即可.
代码如下:
#include<iostream> #include<bits/stdc++.h> using namespace std; int main(){ int sum, sum1, sum2; int a=1; for(int b=0;b<=9;b++){ if(b!=a){ for(int c=0;c<=9;c++){ if(c!=a&&c!=b){ for(int d=0;d<=9;d++){ if(d!=a&&d!=b&&d!=c){ for(int e=1;e<=9;e++){ //e 不能等于 0 if(e!=a&&e!=b&&e!=c&&e!=d){ for(int f=0;f<=9;f++){ if(f!=a&&f!=b&&f!=c&&f!=d&&f!=e){ for(int g=0;g<=9;g++){ if(g!=a&&g!=b&&g!=c&&g!=d&&g!=e&&g!=f){ for(int h=0;h<=9;h++){ if(h!=a&&h!=b&&h!=c&&h!=d&&h!=e&&h!=f&&h!=g){ sum1=e*1000+d*100+f*10+g; sum2=a*1000+b*100+c*10+d; sum=a*10000+b*1000+f*100+d*10+h; if(sum==(sum1+sum2)){ printf("%d\n",sum2); } } } } } } } } } } } } } } } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
一段错误的代码
下面这段代码是错误的:
#include<iostream> #include<bits/stdc++.h> using namespace std; int main(){ int aa[10]={0,1,2,3,4,5,6,7,8,9}; int sum=0; int sum1=0; int sum2=0; int ans=0; while(next_permutation(aa,aa+10)){ if(aa[0]!=0&&aa[4]!=0){ sum1=aa[4]*1000+aa[3]*100+aa[5]*10+aa[6]; sum2=aa[0]*1000+aa[1]*100+aa[2]*10+aa[3]; sum=aa[0]*10000+aa[1]*1000+aa[5]*100+aa[3]*10; if(sum==(sum1+sum2)){ break; } } } cout<<sum2<<endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
运行结果是:
1083
- 1
由运行结果可以看到, 最后计算的和为"10430", 出现了重复的 “0”, 而在题目中的结果里 “三 羊 生 瑞 气” 并没有重复的汉字, 因此这个结果是错误的, 原因在下面这段代码:
sum=aa[0]*10000+aa[1]*1000+aa[5]*100+aa[3]*10;
- 1
上面这段代码中没有加入个位, 因此导致错误,
在做题时要注意以下三点:
- 认真读题, 充分理解题意后再做题.
- 认真写代码, 长代码能分行写的就分开写, 不要出现不符合题意的代码.
- 计算出结果后如果能手动验算, 一定要手动验算一遍.
