沧州企业网站专业定制wordpress 修改网址导航

T1. 鸡兔同笼

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

时间限制：1 s
内存限制：64 MB

• 输入
  一行，一个正整数 $a(a<32768)$。
• 输出
  一行，包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开。如果没有满足要求的答案，则输出两个 $0$，中间用一个空格分开。
• 样例输入

  20
  

• 样例输出

  5 10
  

思路分析

此题考查数学思维，属于入门题。

由于鸡和兔子的脚都是偶数，因此

• 如果 $a$ 为奇数，则没有满足要求的答案；
• 如果 $a$ 为偶数，则最少的动物数量应满足兔子数量最多，此时答案为 $\lceil a/4\rceil$；最多的动物数量应满足鸡的数量最多，此时答案为 $a/2$。

/** Name: T1.cpp* Problem: 鸡兔同笼* Author: Teacher Gao.* Date&Time: 2024/12/02 19:41*/#include <cstdio>int main()
{int a;scanf("%d", &a);if (a % 2) printf("0 0");else printf("%d %d", (a + 3) / 4, a / 2);return 0;
}

T2. 猴子吃桃

海滩上有一堆桃子，$n$ 只猴子来分。第一只猴子把这堆桃子平均分为 $n$ 份，多了一个，这只猴子把多的一个扔入海中，拿走了一份。第二只猴子接着把剩下的桃子平均分成 $n$ 份，又多了一个，它同样把多的一个扔入海中，拿走了一份。第三、第四、…… 第 $n$ 只猴子仍是最终剩下的桃子分成 $n$ 份，扔掉多了的一个，并拿走一份。

编写程序，输入猴子的数量 $n$，输出海滩上最少的桃子数，使得每只猴子都可吃到桃子。

时间限制：1 s
内存限制：64 MB

• 输入
  一个整数 $n$。
• 输出
  输出当猴子数量为 $n$ 时海滩上最少的桃子数。结果保证在 int 型范围内。
• 样例输入

  2
  

• 样例输出

  7
  

思路分析

更新于 2024/12/05：

1. 修正此前思路分析中的错误；
2. 给出适合小学生的解题思路。

此题考查枚举算法和递推算法，属于基础题。

递推思路一：假设第 $i$ 只猴子分桃子时的总数为 $s_i$，根据题意，第 $i$ 只猴子拿走的桃子数量为 $\frac{(s_i-1)}{n}$，于是第 $i+1$ 只猴子分桃子时的总数为 $s_{i+1}=\frac{(s_i-1)}{n}\times (n-1)$。由于知道末项，需要求解首项，因此需要转变递推式为 $s_i=\frac{s_{i+1}\times n}{n-1}+1$，最终答案为 $s_1$。

递推思路二：假设第 $i$ 只猴子拿走的桃子数量为 $s_i$，根据题意，第 $i+1$ 只猴子分桃子时的总数为 $s_i\times (n-1)$，于是第 $i+1$ 只猴子拿走的桃子数量为 s i + 1 = s