全国青少年信息学奥林匹克竞赛(信奥赛)备考实战之循环结构(for循环语句)(七)

发布于:2025-02-10 ⋅ 阅读:(79) ⋅ 点赞:(0)

实战训练—鸡兔同笼

问题描述:

一个笼子里面关了鸡和兔子(鸡有2只脚,兔子有4只脚,没有例外)。已经知道了笼子里面脚的总数为a,问笼子里面至少有多少只动物,至多有多少只动物。

输入格式:

一行,一个正整数a(a<32768)。

输出格式:

一行,包含两个正整数,第一个是笼子里最少的动物数,第二个是笼子里最多的动物数,两个正整数用一个空格分开。如果没有满足要求的答案,则输出两个0,中间用一个空格分开。

输入输出样例:

输入样例1

输出样例1

40

10 20

输入样例2

输出样例2

50 

13 25

输入样例3

输出样例3

31

0 0

问题分析:

根据题意,已知笼子里面动物的脚总个数,来求解笼子里动物数的最小值和最大值,分别用minv和maxv来表示动物数的最少值和最大值,最直接的做法,依次罗列鸡和兔子可能的个数,然后用这两种动物数总和和最大值最小值比较,其中鸡的个数最少为0只,最大就是脚的总数a去除以2的值,兔子的个数最小值为0只,最大值为a/4,具体实现可以使用for嵌套循环枚举鸡和兔子的数量,鸡的个数用外层循环变量i来控制,兔子的个数用内层循环变量j来控制,然后判断i和j的值是否满足题目中的条件,即它们的脚总数为a,如果满足条件,紧接着去判断当前个数和最大值最小值的关系,并根据实际情况修改最大值最小值。具体程序代码如下:


#include<bits/stdc++.h>
using namespace std;
int main(){
    int a;//定义动物脚总数变量a 
    cin>>a;//输入a的值 
    int maxv=0,minv=32768;//定义动物总数最大值变量maxv并初始化为0、最小值变量 minv并初始化为32768 
    for(int i=0;i<=a/2;i++){//定义外层循环变量i控制鸡的个数,从0到a/2 
        for(int j=0;j<=a/4;j++){//定义内层循环变量j控制兔子的个数,从0到a/4 
            if(2*i+4*j ==a){//鸡i的个数乘以2加上兔子的个数j乘以4的总脚数是否为a, 
                if(i+j>maxv){//判断当前鸡的个数加兔子的个数是都比最大值大,如果大,将最大值设置为i+j 
                    maxv = i+j;
                }
                if(i+j<minv){//判断当前鸡的个数加兔子的个数是都比最小值小,如果小,将最小值设置为i+j 
                    minv = i+j;
                }
            }
        }
    }
    if(maxv>0){//判断是否有符合条件的解,maxv不为初始值,表明有解 
        cout<<minv<<" "<<maxv<<endl;
    }else{//否则无解,输出0 0 
        cout<<0<<" "<<0<<endl;
    }	
    return 0;
}

在程序运行之后有可能出现超时的问题,for嵌套循环,每次执行一次外层循环,内层循环要全部执行一次,通过计算执行的最大次数为a/2乘以a/4,a的最大值为32768,代入计算可以发现执行的最大次数为134217728次,可以对其进行优化,具体优化思路:仅使用for循环来实现,循环变量为兔子的数量i,那么鸡的脚数就为(a-4*i),如果鸡脚数能被2整除(对2取余为0),这时该解为一种可能的值分别和最大值最小值进行比较并修改,只有一层循环,循环执行的最大次数为a/4,即8192次。具体程序代码如下:


#include<bits/stdc++.h>
using namespace std;
int main() {
	int a;//定义动物脚总数变量a
	cin>>a;//输入a的值
	int maxv=0,minv=32768;//定义动物总数最大值变量maxv并初始化为0、最小值变量 minv并初始化为32768
	for(int i=0; i<=a/4; i++) { //定义循环变量i控制兔子的个数,从0到a/4
		int j = a - 4*i;//定义鸡脚总数j,并赋值
		if(j%2==0) { //如果鸡脚总数j能被2整除
			if(i+j/2>maxv) { //判断当前鸡的个数加兔子的个数是都比最大值大,如果大,则更新最大值 
				maxv = i+j/2;
			}
			if(i+j/2<minv) { //判断当前鸡的个数加兔子的个数是都比最小值小,如果小,则更新最小值 
				minv = i+j/2;
			}
		}
	}
	if(maxv>0) { //判断是否有符合条件的解,maxv不为初始值,表明有解
		cout<<minv<<" "<<maxv<<endl;
	} else { //否则无解,输出0 0
		cout<<0<<" "<<0<<endl;
	}
	return 0;
}

此题还可以继续优化,如果存在合理的解,那么脚的总数a一定是偶数,要想动物数量多,那么脚一定是越少越多,由于鸡的脚是2只,所以笼子里面全部为鸡时,动物最多,即maxv等于a/2;同理,要想动物数量最少,那么脚一定是越多越小,由于兔子的脚是4只,所以笼子里面全部为兔子时,动物最少,这时必须满足a能被4整除,即a%4的值为0,如果不为0,那么除了兔子还有鸡,这时可以将2只脚给了鸡,剩余的全部为兔子,那么兔子的总数为(a-2)/4,所以最小值有两种情况,a能被4整除,minv为a/4,否则为(a-2)/4+1。具体程序代码如下:


#include<bits/stdc++.h>
using namespace std;
int main() {
	int a;//定义动物脚总数变量a
	cin>>a;//输入a的值
	int maxv=0,minv=32768;//定义动物总数最大值变量maxv并初始化为0、最小值变量 minv并初始化为32768
	if(a%2==0){//如果a是偶数,动物最大值为a/2 
		maxv = a/2;//全部为鸡 
	}
	if(a%4==0){//如果a能被4整除 
		minv = a/4; //全部为兔子
	}else{
		minv = (a-2)/4+1;//一只鸡,剩余的为兔子
	}
	if(maxv>0) { //判断是否有符合条件的解,maxv不为初始值,表明有解
		cout<<minv<<" "<<maxv<<endl;
	} else { //否则无解,输出0 0
		cout<<0<<" "<<0<<endl;
	}
	return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到