解题思路

这是一个递归解法的苹果分配问题。关键点：

  1. 递归函数定义：

    • getInitial(n, k, x)：表示还剩 头熊，当前苹果数为 时是否可行
    • ：总熊数
    • ：剩余熊数
    • ：当前苹果数

  2. 递归条件：

    • 基础情况：k=0时返回true，表示所有熊都分完了
    • 剪枝条件：(x-1)%n != 0时返回false，表示不能均分
    • 递归：检查下一头熊分苹果的情况

  3. 主函数：

    • 从1开始枚举可能的初始苹果数
    • 找到第一个满足条件的数即为答案

代码

class Apples {
public:
    bool getInitial(int n, int k, int x) {
        if(k == 0) return true;
        if((x-1) % n != 0) return false;
        return getInitial(n, k-1, (x-1)*(n-1)/n);
    }
    
    int getInitial(int n) {
        for(int i = 1; i <= INT_MAX; i++) {
            if(getInitial(n, n, i)) {
                return i;
            }
        }
        return 0;
    }
};

import java.util.*;
public class Apples {
    public boolean getInitial(int n, int k, int x) {
        if(k == 0) return true;
        if((x-1) % n != 0) return false;
        return getInitial(n, k-1, (x-1)*(n-1)/n);
    }
    
    public int getInitial(int n) {
        for(int i = 1; i <= Integer.MAX_VALUE; i++) {
            if(getInitial(n, n, i)) {
                return i;
            }
        }
        return 0;
    }
}

# -*- coding:utf-8 -*-

class Apples:
    def check(self, n, k, x):
        if k == 0:
            return True
        if (x-1) % n != 0:
            return False
        return self.check(n, k-1, (x-1)*(n-1)//n)
    
    def getInitial(self, n):
        i = 1
        while True:
            if self.check(n, n, i):
                return i
            i += 1

算法及复杂度

  • 算法：递归 + 枚举
  • 时间复杂度：，其中 为最小解的大小，每个数需要递归 次
  • 空间复杂度：，递归栈的深度为n