今天继续分享少儿编程项目经验，前一篇主要讲使用循环嵌套语句打印规则图形，其思路是按先行后列方式逐个打印出空格和星号，其技巧就是针对对称图形，对半输出。

讲完了打印图形，我们就来讲循环穷举法。

什么是循环穷举法？
对于穷举来说,我们大人是很好理解的，就是列出所有可能的情况，然后找出满足条件的数据。而对于10岁左右的小朋友，要解释这个概念，要费不少时间.

那什么是循环穷举？它就是通过循环语句,列出所有可能的数据,然后再判断符合条件的数据。

今天不去讲怎么跟小朋友解释，而是通过题目来举例说明。

针对这个知识点,有7个试题,下面分别说明.

【题目一】鸡兔同笼
一个笼子里有若干只鸡，若干只兔子。其中头共有150只，腿共有480只，问鸡和兔各有多少只？

这个题目是数学中经典题目了，若是采用数学的方法来解决。
一般是设x，y两个未知数，然后列出算式
x + y = 150
2*x + 4 *y = 480
最后求解 x，y值。

然而，这里我们要用编程的方式来求解，具体怎么解呢？
使用穷举方法:
一只鸡,一只兔 -> 2个头(1 + 1), 6只脚(2 + 4)
一只鸡, 两只兔 -> 2个头(1 + 2), 6只脚(2 + 2 * 4)
….
如此,依次地遍历下去.
最后找到 满足条件的鸡,兔.

根据上面的思路,就能编写如下的程序:

include

using namespace std;
int main() {

int i = 1;
int a = 150;
int b = 480;
while(i < a) {
if ( 2 * i + (a – i) * 4 == b) {
cout<<“鸡: “<< i << ” 兔子: “<< a -i << endl;
}
i++;
}
}
很容易得到答案: 鸡为60只，兔为90只。

上述方法是比较简单的,然而不符合穷举法.那么穷举法又是如何实现的呢? 按上面的思路，就是如下的程序：

include

using namespace std;
int main() {
//鸡的个数从1到150(最少1只, 150)
int a = 150;
int b = 480;
//i表示鸡的数量, 从1 开始循环遍历鸡的个数,直到 149(因为鸡兔都存在,不能为150,至少有一只兔子)
for(int i = 1; i < a; i++) {

 //j表示兔的数量, 从1 开始循环遍历兔的个数,直到 总数 减去 鸡的个数 
    for( int j = 1; j <= a - i; j++) {
     // 鸡的头数 + 兔的头数 等于 150 
     int t = i + j;

     // 鸡的腿数 + 兔的腿数 等于 480
     int t1 = 2 * i + 4 * j;

     if ((t  == a) && (t1 == b)) {
       cout<<"鸡: "<< i << " 兔子: "<<j << endl;
     }  
   } 
}

}
但是，注意啦：上述做法,从性能角度来说,是大大浪费了.所以建议使用方式一.

【题目二】公园卖票
某公园门票价格是：儿童票3元/张，成人票8元/张，某天学校组织家长和学生来公园游玩。这次活动家长和学生都有参加，门票共花了40元，请分别列出家长和学生都可能的人数。

这个问题的解决思路如下:
思路:
从买一张一张儿童票轮询
买一张, 剩下的钱,刚好买完成人票(剩余的钱 % 8 == 0).
买二张, 剩下的钱,刚好买完成人票 (剩余的钱 % 8 == 0)
买三张, 剩下的钱,刚好买完成人票 (剩余的钱 % 8 == 0)
……..
买 i 张, 剩下的钱,刚好买完成人票 (剩余的钱 % 8 == 0)

需要注意的地方:
问题中要求成人和儿童必须要有一个. 所以儿童票的最多能买的票为(40 减去 一张成人票 / 3)

这样,就得到如下的编程:
for (int i = 1; i < (40 – 8) / 3; i++) {
int x = 40 – 3 * i;
if ( x % 8 == 0) {
cout<< ” 儿童票:”<< i<< ” 成人票:”<< x / 8<<endl;
}
}
得到结果：儿童票8张，成人票2张

这个题目还可以使用二重For循环枚举。
思路:
从买一张儿童票 + 一张成人票开始循环叠加
1张 儿童票, 1张成人票
1张 儿童票 2张成人票
….
i张 儿童票, j张成人票
保证 儿童票的票价总数 + 成人票的票价总数 = 40元

还需要注意的地方:
问题中要求成人和儿童必须要有一个. 所以儿童票的最多能买的票为(40 减去 一张成人票 / 3) 。得到程序如下：
for (int i = 1; i <= (40 – 8) / 3; i++) {
int x = 40 – 3 * i;
for (int j = 1; j <= x / 8; j++) {
int t = i * 3 + j * 8;
if (t == 40) {
cout<< ” i:”<< i<< ” j:”<<j<<endl;
}
}
}
这两个题目都是属于循环穷举法的例子，针对这样类型的题目还有两个:
【题目三】买小猫小狗问题
某宠物中心，决定用X元来购买一批小猫小狗，其中小猫为a元/只，小狗为b元/只。要求做到专款专用，问正好用完这笔钱，求出可行方案的总数。转换下(X= 1700元， a = 31元/只， b = 21元/只)

【题目四】阿凡提的难题
阿凡提去集市上买餐具，财主正好在卖餐具，所以准备为难一下阿凡提；财主的餐具有两种：大碗和小碗，财主和阿凡提说，你买我的碗，要花光你带的钱，并且，两种碗都要买，买的两种碗的数量都的是偶数。请帮助下阿凡提，求出所有的方法。转换(阿凡提有100元， 大碗20， 小碗10）

其解题思路和上面一样,我这里就直接贴出编程了
//题目三

include

using namespace std;
int main() {

//n 表示总共的 价格 = 1700
//a 表示 小猫的单价 a元/只 = 31
//b 表示 小狗的单价 b元/只 = 21

int n,a,b;
cin>>n>>a>>b;
int cnt = 0;

for ( int i = 1; i < (n – b) / a; i++) {
int x = n – i * a;
if( x % b == 0) {
cout<<” 小猫: “<<i<<” 小狗: “<< x / b<<endl;
cnt++;
}
}
cout<<“count :”<<cnt<<endl;
}
//题目四

include

using namespace std;
int main() {

int n,a,b;
cin>>n>>a>>b;
int cnt = 0;
/* //大碗
for(int i = 1; i <= (n – b ) / a; i++) {

int x = n - a * i;  //剩余的钱 

int y = x / b;    //小碗的数量 

if (x % b == 0) {  //剩余的钱,刚好买完小碗. 
  if ( i % 2 == 0  &&  y % 2 == 0) {

    cout<<endl;
    cout<<"    大碗: "<< i<<" 小碗: " << y<<endl;
    cnt++;
  } 
}

}
/ /
利用偶数关系求解.
大碗是偶数个买, 最小为2个; 最多为 (n – 2 * b) / a; 叠加为 i= i+ 2

 小碗的数量是 %2 == 0; 且  剩余的钱 % 小碗单价 == 0 (刚好用完) 

*/
for( int i = 2; i <= (n – 2 * b) / a; i = i+2) {

   int x = n - i * a;  //剩余的钱
   int y = x / b;  // 小碗的数量 
   if ( y % 2 == 0 &&  x % b == 0) {
      cout<<"大碗: "<< i<<" 小碗: " << y<<endl;
      cnt++;
   }

}
cout<<“cnt: “<<cnt<<endl;
}
了解和掌握的循环穷举法,其本质上就是一个for循环就可以搞定的.当然,上面的例子中,我在第二种方法中使用了两个for,是非标准的循环穷举.而是下面要讲到了循环嵌套穷举。

什么是循环嵌套穷举？
循环嵌套穷举,顾名思义,就是两个或两个以上的for循环使用.
针对这个知识点,也有三个典型题目

【题目五】百钱百鸡
用100元购买100只鸡，公鸡，母鸡和小鸡都要有，其中公鸡5元/只，母鸡3元/只， 小鸡1元3只。问公鸡，母鸡和小鸡各应该买多少只？

思路:
这里有三种类型的鸡:公鸡,母鸡,小鸡
那么针对每种类型的鸡,使用循环穷举:

1.若公鸡为i只,且最少1只,最多(100只 – 1只母鸡 – 1只小鸡).同样的可以 (100元 – 一只母鸡的价格 – 一只小鸡的价格) / 公鸡的单价

2.二重循环,母鸡为j只,且最少1只,最多( 买公鸡剩余的钱 减去 一只小鸡的价格) / 母鸡的单价

3.最后,剩余的钱刚好可以买完小鸡.

根据这个思路,就得到如下的程序:

include

using namespace std;
int main() {

//公鸡为i, 最少一只, 最多 (100元 – 1只母鸡 – 一只小鸡) / 公鸡单价
for (int i = 1; i<= (100 – 3 – 1/3) / 5; i++) {
int x = 100 – 5 * i; //剩余的钱

    //母鸡为j, 最少一只, 最多 剩余的钱 / 母鸡单价 
    for(int j = 1; j <= (x - 1 /3 ) / 3; j++) {

         int y = x - 3 * j;  //买完公鸡,母鸡后,剩余的钱 

         int t = 3 * y;   //  小鸡的数量 =  剩余的钱/ 小鸡单价 

          if ( i + j + t == 100) {
              cout<<" 公鸡: "<<i<< "  母鸡: "<<j << " 小鸡:"<< t<<endl;
          }
     }    

}
}
这里有一个小问题, 在二重for循环中,理论上不需要再减小鸡的数量了,因为在公鸡循环中已经减了一只小鸡的数量. 这样就得到如下的程序.

include

using namespace std;
int main() {
//公鸡为i, 最少一只, 最多 (100元 – 1只母鸡 – 一只小鸡) / 公鸡单价
for (int i = 1; i<= (100 – 3 – 1 /3) / 5; i++) {
int x = 100 – 5 * i; //剩余的钱
//母鸡为j, 最少一只, 最多剩余的钱/ 母鸡单价 // 这里不需要再 减一只小鸡的价格,因为前面已经减去了.
for(int j = 1; j <= x / 3; j++) {

        int y = x - 3 * j;  //买完公鸡,母鸡后,剩余的钱 

        int t = 3 * y ;   //  小鸡的数量 =  剩余的钱/ 小鸡单价 

        if ( i + j + t == 100) {
            cout<<" i : "<<i<< " j: "<<j << " t:"<< t<<endl;
        }
    }  

}
}
这一点的改动,也没有影响最终的结果. 但我个人认为这个思路是对的.这里记录下.

【题目六】兑换硬币
用一张1元票换1分，2分和5分的硬币，每种至少要一枚，问有多少种换法？

类似于问题5的方法,同样的处理,唯一的区别,这里是求总数,那么就需要一个cnt来计数,就OK. 程序如下:

include

using namespace std;
int main() {
int n = 1;
n = n * 100;

int cnt = 0;

// i 表示1分, 最少一枚,最多 100 – 一枚2分 – 一枚5分
for(int i = 1; i <= n – 2 -5; i++) {

int x = n - i * 1;   //兑换完1分后,剩余的钱

for (int j = 1; j <= x / 2 ; j++) {

  int y = x - j * 2;//兑换完2分后, 剩余的钱

  int z = y / 5;  //兑换 5分的数量 

  int sum = i + j * 2 +  z * 5;

  if (y != 0 &&  sum == n) {
    // cout<<" 1分:" << i<< " 2分: "<< j << " 5分:" << y /5<<endl; 
     cnt++;
  } 

} 

}

/*
for(int i = 1; i <= n – 2 -5; i++) {

int x = n - i * 1;   //兑换完1分后,剩余的钱

for (int j = 1; j <= x / 2 ; j++) {

  int y = x - j * 2;//兑换完2分后, 剩余的钱       

  if (  y != 0 && y % 5 == 0) {
     cout<<" 1分:" << i<< " 2分: "<< j << " 5分:" << y /5<<endl; 
     cnt++;
  } 

} 

}*/
cout<<” cnt : “<<cnt<<endl;
}
结果是461种换法。
这里需要注意的情况: 1分,2分,5分的硬币都要有. 即不能存在y为0的情况(5分硬币一个都没有)，

【题目七】购买文具
新学期开学了，爸爸拿N元给小明，让他去购买一批文具，并要求如下：只能买圆珠笔，铅笔和铅笔芯，且每样至少买一支；钱要全部花完。小明到文具店了解到：圆珠笔是8角/支，铅笔是2角/支，铅笔芯是1角/支。问小明如何买才能满足爸爸的要求呢？

思路还是和问题五一样.那么得到的程序如下:

include

using namespace std;
int main() {
int n ;
cin>>n;

n = n * 10;// 把元 统一转成角单位,方便计算
int cnt = 0;

//圆珠笔 ,最少1支, 最多(总价 – 单支铅笔价格 – 单支铅笔芯的价格) / 圆珠笔单价)
for(int i = 1; i < (n – 2 -1 ) / 8; i++) {

int x = n - i * 8; //买完圆珠笔后 剩余的钱

//铅笔,最少1支,最多 (剩余的钱-) / 铅笔的单价;; 这里没有减铅笔芯的价格,因为前面已经减去了 
for(int j = 1; j < x /2; j++) {

  int y = x - j * 2; //买完铅笔后 剩余的钱

  int sum = i * 8 + j * 2 + y;  //三种笔的总价格 等于总数 

  if ( sum == n) {
    cout<<" 圆珠笔:" << i<< " 铅笔: "<< j << " 铅笔芯:" << y<<endl; 
    cnt++;
  }
} 

}
cout<<cnt<<endl;
}
结果是：输入8 元，输出有168种方案。
至此，循环穷举，包括循环嵌套穷举就举例完成了。