【多重循环】【流程控制】abc组合（“百文白鸡”穷举法）

104 阅读 0 评论 69 点赞

我是靠谱客的博主紧张哑铃，最近开发中收集的这篇文章主要介绍【多重循环】【流程控制】abc组合（“百文白鸡”穷举法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在这道题之前，我要先介绍一种经典的问题“百文白鸡”的解法。

问题大致为：鸡翁一只5块，鸡母一只3块，三只鸡雏1块，请问100块可以买多少组合，最终的鸡数必须也是100只。

在C语言中，解决这样情况较多，但是关联点在于钱数加和确定的问题，可以用多重循环来解决。由于我找不到百文白鸡的原题，下面用一个类似的问题来充当引例：

【换硬币问题】
将一笔零钱换成5分、2分和1分的硬币，要求每种硬币至少有一枚，有几种不同的换法？

输入格式:
输入在一行中给出待换的零钱数额x∈(8,100)。

输出格式:
要求按5分、2分和1分硬币的数量依次从大到小的顺序，输出各种换法。每行输出一种换法，格式为：“fen5:5分硬币数量, fen2:2分硬币数量, fen1:1分硬币数量, total:硬币总数量”。最后一行输出“count = 换法个数”。

输入样例:
13

输出样例:
fen5:2, fen2:1, fen1:1, total:4
fen5:1, fen2:3, fen1:2, total:6
fen5:1, fen2:2, fen1:4, total:7
fen5:1, fen2:1, fen1:6, total:8
count = 4

已经说过，这类问题分类情况较多，但是关联点在于加和给定，属于“百文白鸡”类型的问题。我们先看代码：

#include<stdio.h>
int main(void)
{
	int a;
	scanf("%d",&a);
	int i,j,k;
	int sum=0,p=0;
  for (i=a/5; i>0; i--)
    {
    	for (j=a/2; j>0; j--)
    	  {
    	  	  for (k=1; k<=a; k++)
    	  	    {
    	  	      	p=k+j*2+i*5;
    	  	      if (p==a)  
					{
					  printf("fen5:%d, fen2:%d, fen1:%d, total:%dn",i,j,k,i+j+k);
					  sum++;
					  p=0;
				    }
				  else  p=0;
				}
		  }
	}
	  printf("count = %d",sum);
	  return 0;
 }

整个程序的核心在于一个“三重循环”。

for (i=a/5; i>0; i--)
    {
    	for (j=a/2; j>0; j--)
    	  {
    	  	  for (k=1; k<=a; k++)
    	  	    {
    	  	      	p=k+j*2+i*5;
    	  	      if (p==a)  
					{
					  printf("fen5:%d, fen2:%d, fen1:%d, total:%dn",i,j,k,i+j+k);
					  sum++;
					  p=0;
				    }
				  else  p=0;
				}
		  }
	}

观察这段代码，其实不难理解：
如果k+2j+5i加和不满足条件，则最内循环变量k首先递增来迎合当前的j和i。k一轮循环如果还是不满足条件，那么接下来中间循环变量j会递增1，再让内循环k循环一轮……如此反复，必能遍历到所有满足条件的情况。
.
.
.
学会了这样的流程控制方法，我们来看这道题：

【abc组合问题】

问题描述
已知abc+cba=n，其中a,b,c均为一位数，1000<n<2000,编程求出满足条件的a,b,c所有组合。

输入说明
一个整数n

输出说明
按照整数abc从小到大的顺序,输出a, b, c, 用空格分隔，每输出一组a，b，c后换行.

输入样例
1352

输出样例
3 7 9
4 7 8
5 7 7
6 7 6
7 7 5
8 7 4
9 7 3

我们看，这道题也是情况繁多，但是关联点在于abc+cba=n的条件是始终不变的。
那么，我们想，把a、b、c分别最为三层循环的变量，最内循环节的判断语句是abc+cba是否为n，这样就能遍历到所有的情况了！同时我们也发现，这其实也是一道“百文白鸡”类型的题目，只是比较隐晦罢了！
理解到这一步，我们开始写程序吧：

#include<stdio.h>

int judge (int a,int b,int c)
{
	int x;
	int y;
	x=a*100+b*10+c;
	y=c*100+b*10+a;
	return x+y;
}

int main (void)
{
	int x;
	scanf("%d",&x);
	int a,b,c;
  for (a=0; a<=9; a++)
  {
  	for (b=0; b<=9; b++)
  	{
  		for (c=0; c<=9; c++)
  		{
  			if (judge(a,b,c)==x)
  			{
  				printf("%d %d %dn",a,b,c);
  			}
  		}
  	}
  }
  return 0;
}