题解 | #百钱买百鸡问题#

解题思路

• 使用三重循环遍历所有可能的组合
• 设公鸡 只，母鸡 只，小鸡 只
• 满足条件：
  1. (总数为100只)
  2. (总价为100钱)
  3. 必须是3的倍数（小鸡1钱三只）

代码

def solve_chicken_problem():
    # 遍历所有可能的公鸡数量(0-20)
    for x in range(21):  # 公鸡5钱一只，最多20只
        # 遍历所有可能的母鸡数量(0-33)
        for y in range(34):  # 母鸡3钱一只，最多33只
            # 计算小鸡数量
            z = 100 - x - y
            # 检查是否满足条件
            if z >= 0 and z % 3 == 0 and 5*x + 3*y + z//3 == 100:
                print(x, y, z)

while True:
    try:
        n = int(input())  # 输入任意整数即可运行程序
        solve_chicken_problem()
    except:
        break

import java.util.Scanner;

public class Main {
    public static void solveChickenProblem() {
        // 遍历所有可能的公鸡数量(0-20)
        for (int x = 0; x <= 20; x++) {  // 公鸡5钱一只，最多20只
            // 遍历所有可能的母鸡数量(0-33)
            for (int y = 0; y <= 33; y++) {  // 母鸡3钱一只，最多33只
                // 计算小鸡数量
                int z = 100 - x - y;
                // 检查是否满足条件
                if (z >= 0 && z % 3 == 0 && 5*x + 3*y + z/3 == 100) {
                    System.out.println(x + " " + y + " " + z);
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();  // 输入任意整数即可运行程序
            solveChickenProblem();
        }
    }
}

#include <iostream>
using namespace std;

void solveChickenProblem() {
    // 遍历所有可能的公鸡数量(0-20)
    for (int x = 0; x <= 20; x++) {  // 公鸡5钱一只，最多20只
        // 遍历所有可能的母鸡数量(0-33)
        for (int y = 0; y <= 33; y++) {  // 母鸡3钱一只，最多33只
            // 计算小鸡数量
            int z = 100 - x - y;
            // 检查是否满足条件
            if (z >= 0 && z % 3 == 0 && 5*x + 3*y + z/3 == 100) {
                cout << x << " " << y << " " << z << endl;
            }
        }
    }
}

int main() {
    int n;
    while (cin >> n) {  // 输入任意整数即可运行程序
        solveChickenProblem();
    }
    return 0;
}

算法分析

• 算法：穷举法
• 时间复杂度：，其中 为可能的鸡的数量范围
• 空间复杂度：，只需要常数级别的额外空间