本文共 7797 字，大约阅读时间需要 25 分钟。

每日刷题（三十四）

蓝桥杯第七届C语言B组省赛习题

习题C：凑算式

图1.jpg

如果想看正确思路以及正确代码及答案的可以一直往下翻到文末，前面的都是整合了一些朋友的代码错误，各位可以引以为鉴！

暴力枚举法

由题意分析可知，各个数的各位都不相同，共需要五层循环嵌套，A、B、C都是从0~9循环，DEF和GHI是在100—999的范围内

详细C代码如下

#include
   
    int 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代码如下

#include
   
    int 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;}
   

运行结果比上一个没出数字的好

因为实在太长了，这里我就截取了首尾两部分，很明显，又出问题了 我把代码修改了一下

#include
   
    int 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代码答案

#include
   
    int 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/