蓝桥杯2016第七届C语言B组省赛习题题解——习题C.凑算式
本文共 7797 字，大约阅读时间需要 25 分钟。
每日刷题（三十四）
蓝桥杯第七届C语言B组省赛习题
习题C：凑算式
如果想看正确思路以及正确代码及答案的可以一直往下翻到文末，前面的都是整合了一些朋友的代码错误，各位可以引以为鉴！
暴力枚举法
由题意分析可知，各个数的各位都不相同，共需要五层循环嵌套，A、B、C都是从0~9循环，DEF和GHI是在100—999的范围内
详细C代码如下#includeint main(){ int sum = 0, num1, num2, num3, num4, i, j, k, num5, a, b, c, d; for(num1 = 0; num1 <= 9; num1++) //A { for(num2 = 0; num2 <= 9; num2++) //B { if(num2 == num1) num2 += 1; for(num3 = 0; num3 <= 9; num3++) //C { if(num3 == num1 || num3 == num2) num3 += 1; for(num4 = 102; num4 <= 999; num4++) //DEF { if(num4 / 100 == num1 || num4 / 100 == num2 || num4 / 100 == num3) num4 += 100; else if(num4 / 10 % 10 == num1 || num4 / 10 % 10 == num2 || num4 / 10 % 10 == num3) num4 += 10; else if(num4 % 10 == num1 || num4 % 10 == num2 || num4 % 10 == num3) num4 += 1; i = num4 / 100; //百位 j = num4 / 10 % 10; //十位 k = num4 % 10; //个位 for(num5 = 102; num5 <= 999; num5++) //GHI { if(num5 / 100 == num1 || num5 / 100 == num2 || num5 / 100 == num3 || num5 / 100 == i) num5 += 100; else if(num5 / 10 % 10 == num1 || num5 / 10 % 10 == num2 || num5 / 10 % 10 == num3 || num5 / 10 % 10 == j) num5 += 10; else if(num5 % 10 == num1 || num5 % 10 == num2 || num5 % 10 == num3 || num5 % 10 == k) num5 += 1; a = num5 / 100; //百位 b = num5 / 10 % 10; //十位 c = num5 % 10; //个位 if(num5 % num3 == 0) { d = num5 / num3; if((num2 + d + num4) / num5 + num1 == 10) { sum++; printf("Project%5d : %5d + %5d / %5d + %5d / %5d = 10\n",sum,num1,num2,num3,num4,num5); } } } } } } } return 0; }
运行结果如下
凡是出现return value 3221225620 或者4294967295都表示代码运行不了 
所以虽然上面的代码逻辑思维是正确的，但执行不了，只能换一种方案 把A、B、C、D、E、F、G、H、I看做独立的数字，然后查看有多少解法 详细C代码如下 #includeint main(){ int A, B, C, D, E, F, G, H, I, sum = 0; for(A = 0; A <= 9; A++) { for(B = 0; B <= 9; B++) { if(B == A) B++; for(C = 0; C <= 9; C++) { while(C == A || C == B) C++; for(D = 0; D <= 9; D++) { while(D == A || D == B || D == C) D++; for(E = 0; E <= 9; E++) { while(E == A || E == B || E == C || E == D) E++; for(F = 0; F <= 9; F++) { while(F == A || F == B || F == C || F == D || F == E) F++; for(G = 0; G <= 9; G++) { while(G == A || G == B || G == C || G == D || G == E || G == F) G++; for(H = 0; H <= 9; H++) { while(H == A || H == B || H == C || H == D || H == E || H == F || H == G) H++; for(I = 0; I <= 9; I++) { while(I == A || I == B || I == C || I == D || I == E || I == F || I == G || I == H) I++; if((G * 100 + H * 10 + I) % C == 0) if(A + ((G * 100 + H * 10 + I) / C * B + D * 100 + E * 10 + F) / (G * 100 + H * 10 + I) == 10) { sum++; printf("Project %5d : %5d + %5d / %5d + %5d / %5d = 10\n",sum, A, B, C, D * 100 + E * 10 + F, G * 100 + H * 10 + I); } } } } } } } } } } return 0;}
运行结果比上一个没出数字的好
因为实在太长了，这里我就截取了首尾两部分，很明显，又出问题了 我把代码修改了一下 #includeint main(){ int A, B = 0, C = 0, D = 0, E = 0, F = 0, G = 0, H = 0, I = 0, sum = 0; for(A = 0; A <= 9; A++) { for(B %= 10; B <= 9; B++) { if(B == A) B++; for(C %= 10; C <= 9; C++) { while(C == A || C == B) C++; for(D %= 10; D <= 9; D++) { while(D == A || D == B || D == C) D++; for(E %= 10; E <= 9; E++) { while(E == A || E == B || E == C || E == D) E++; for(F %= 10; F <= 9; F++) { while(F == A || F == B || F == C || F == D || F == E) F++; for(G %= 10; G <= 9; G++) { while(G == A || G == B || G == C || G == D || G == E || G == F) G++; for(H %= 10; H <= 9; H++) { while(H == A || H == B || H == C || H == D || H == E || H == F || H == G) H++; for(I %= 10; I <= 9; I++) { while(I == A || I == B || I == C || I == D || I == E || I == F || I == G || I == H) I++; if((G * 100 + H * 10 + I) % C == 0) if(A + ((G * 100 + H * 10 + I) / C * B + D * 100 + E * 10 + F) / (G * 100 + H * 10 + I) == 10) { sum++; printf("Project %5d : %5d + %5d / %5d + %5d / %5d = 10\n",sum, A, B, C, D * 100 + E * 10 + F, G * 100 + H * 10 + I); } } } } } } } } } } return 0;}
运行结果
这题直接暴力枚举就行了，有关优化版的暴力枚举法可以参看博文 终极C代码答案
#includeint main(){ int a, b, c, d, e, f, g, h, i; int num = 0; for(a = 1; a < 10; a++) { for(b = 1; b < 10; b++) { if(b == a) continue; for(c = 1; c < 10; c++) { if(c == b || c == a) continue; for(d = 1; d < 10; d++) { if(d == a || d == b || d == c) continue; for(e = 1; e < 10; e++) { if(e == a || e == b || e == c || e == d) continue; for(f = 1; f < 10; f++) { if(f == a || f == b || f == c || f == d || f == e) continue; for(g = 1; g < 10; g++) { if(g == a || g == b || g == c || g == d || g == e || g == f) continue; for(h = 1; h < 10; h++) { if(h == a || h == b || h == c || h == d || h == e || h == f || h == g) continue; for(i = 1; i < 10; i++) { if(i == a || i == b || i == c || i == d || i == e || i == f || i == g || i == h) continue; int m = a * c * (g * 100 + h * 10 + i); int n = b * (g * 100 + h * 10 + i); int o = c * (d * 100 + e * 10 + f); int tmp = 10 * c * (g * 100 + h * 10 + i); if(m + n + o == tmp) num++; } } } } } } } } } printf("%d\n", num); return 0;}
运行结果如下
本题答案就是29 全排列递归回溯法
不妨设
使得每个字母对应一个数组元素 C++代码：
#include#include using namespace std;int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9};int ans = 0;bool check(){ int x = a[3] * 100 + a[4] * 10 + a[5]; int y = a[6] * 100 + a[7] * 10 + a[8]; if((a[1] * y + a[2] * x) % (y * a[2]) == 0 && a[0] + (a[1] * y + a[2] * x) / (y * a[2]) == 10) return true; return false;}//递归回溯生成全排列，适用于无重复元素的情况void f(int k){ if(k == 9) { if(check()) ans++; } for(int i = k; i < 9; ++i) { { int t = a[i]; a[i] = a[k]; a[k] = t; } f(k + 1); //递归 { //回溯 int t = a[i]; a[i] = a[k]; a[k] = t; } }} int main(){ f(0); cout << ans << endl; return 0; }
递归全排列套路模版：
void f(int k){ if(k == 9) { if(check()) ans++; } for(int i = k; i < 9; ++i) { { int t = a[i]; a[i] = a[k]; a[k] = t; } f(k + 1); //递归 { //回溯 int t = a[i]; a[i] = a[k]; a[k] = t; } }} 直接调用库函数next_permutation法
如果对全排列递归回溯不是很熟悉的朋友，可以用algorithm库函数的next_permutation，可以参看
这里要强调一下它的用法注意事项，这个函数适用于非重复的元素的排列，而且初始给定的数组必须是有序的！
对应该题的做法如下：（C++代码）
#include#include #include using namespace std;int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9};int ans = 0;bool check(){ int x = a[3] * 100 + a[4] * 10 + a[5]; int y = a[6] * 100 + a[7] * 10 + a[8]; if((a[1] * y + a[2] * x) % (y * a[2]) == 0 && a[0] + (a[1] * y + a[2] * x) / (y * a[2]) == 10) return true; return false;}//递归回溯生成全排列，适用于无重复元素的情况void f(int k){ if(k == 9) { if(check()) ans++; } for(int i = k; i < 9; ++i) { { int t = a[i]; a[i] = a[k]; a[k] = t; } f(k + 1); //递归 { //回溯 int t = a[i]; a[i] = a[k]; a[k] = t; } }} int main(){ //f(0); do{ if(check()) ans++; }while(next_permutation(a, a + 9)); cout << ans << endl; return 0; }
最近我还会有更多博文更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持，下期更精彩！！！
转载地址：http://ubynz.baihongyu.com/
你可能感兴趣的文章
mysql InnoDB数据存储引擎 的B+树索引原理
查看>>
mysql innodb通过使用mvcc来实现可重复读
查看>>
mysql insert update 同时执行_MySQL进阶三板斧（三）看清“触发器 (Trigger)”的真实面目...
查看>>
mysql interval显示条件值_MySQL INTERVAL关键字可以使用哪些不同的单位值？
查看>>
Mysql join原理
查看>>
MySQL Join算法与调优白皮书（二）
查看>>
Mysql order by与limit混用陷阱
查看>>
Mysql order by与limit混用陷阱
查看>>
mysql order by多个字段排序
查看>>
MySQL Order By实现原理分析和Filesort优化
查看>>
mysql problems
查看>>
mysql replace first,MySQL中处理各种重复的一些方法
查看>>
MySQL replace函数替换字符串语句的用法（mysql字符串替换）
查看>>
mysql replace用法
查看>>
Mysql Row_Format 参数讲解
查看>>
mysql select， from ，join ，on ，where groupby,having ,order by limit的执行顺序和书写顺序
查看>>
MySQL Server 5.5安装记录
查看>>
mysql server has gone away
查看>>
mysql slave 停了_slave 停止。求解决方法
查看>>
MySQL SQL 优化指南：主键、ORDER BY、GROUP BY 和 UPDATE 优化详解
查看>>