一、枚举

一、枚举

【本次课程来自《coursera-北京大学-算法基础-第二周》】

在这个问题中，我们可以不用取到100.因为公鸡五块一只，母鸡三块一只，那么公鸡最多20只，母鸡最多33只，因此可以写去如下实现：

#include <iostream>
using namespace std;
int main() {
  // 初始化公鸡，母鸡和小鸡为0
    int cocks = 0, hens = 0,chicks = 0;
    int i,j,k;
  //循环计算
    for(i = 1;i < 20; i++)
        for(j = 1; j < 33; j++)
        {
            k = 100 - i -j;
            //第一步，判断小鸡是三的倍数
            if(k % 3 == 0 )
                //第二步，判断价钱总和为100
                if( 5 * i + 3 * j + k / 3 == 100 )
                {
                    cocks = i;
                    hens = j;
                    chicks = k;
                }
        }
//输出
    cout << "ccocks: "<<cocks<<" hens: "<<hens<<" chicks: "<<chicks<<endl;
//这个是为了cmd运算完后不立即结束一闪而过
    cin.clear();
    cin.sync();
    cin.get();
    return 0;
}

二、熄灯问题

程序要求：

#include <iostream>
#include <stdio.h>
using namespace std;

int puzzle[6][8],press[6][8];
bool guess(){
    int c, r; //行， 列
    //我们只计算中间的五行六列，因此序号从1开始
    for (r = 1; r < 5; r++)
        for( c = 1; c < 7 ; c++)
        {
            //对于下一行点击状态，等于上一行本身状态和点击状态，
            //加上受到上，左右三方面影响的和 模 2
            press[r + 1][c] = (puzzle[r][c] + press[r][c] +
            press[r-1][c] + press[r][c-1] + press[r][c+1]) % 2;
        }
    //判断最后一行能够灯全灭
    for(c =1;c<7;c++)
    {
        // 计算第五行的press如果不能灭掉第五行的灯
        if((press[5][c-1] + press[5][c] + press[5][c+1] +
        press[4][c]) % 2 != puzzle[5][c])
        return false;
    }
    return true;
}

//如果灯无法得到全灭的解，就更新press数组第一行
int enumerate(){
    int c;
    bool success;
    //初始化press第一行为0 
    for(c=1;c<7;c++){
        press[1][c] = 0;
    }
    //更新每一行，每一行作为二进制进位的方式，只有0 ，1
    while(guess() == false){
        press[1][1]++;
        c = 1;
        while(press[1][c] > 1){
            press[1][c] = 0;
            c++;
            press[1][c]++;
        }
    }
    return 0;
}

int main() {
    int cases,i,r,c ;
    //几个初始组
    cout<<"input cases: ";
    scanf("%d",&cases);
    //对于外围0,7列和第0行默认为0
    cout<<"cases:"<<cases<<endl;
    for(r=1;r<6;r++)
        press[r][0] = press[r][7] = 0;
    for(c=1;c<7;c++)
        press[0][c] = 0;
    
    //输入初始
    for(i=0;i<cases;i++)
    {
        cout<<"input puzzle: "<<endl;
        for(r=1;r<6;r++)
            for(c=1;c<7;c++)
                //scanf("%d",&puzzle[r][c]);
                cin>>puzzle[r][c];
        //计算每组结果
        enumerate();
        cout<<"output puzzle: "<<i+1<<'\n';
        for(r=1;r<6;r++){
            for(c=1;c<7;c++)
                cout<<press[r][c]<<" ";
            cout<<'\n';
        }
    }



    cin.clear();
    cin.sync();
    cin.get();
    return 0;
}