题解 | 小东分苹果
小东分苹果
https://www.nowcoder.com/practice/532d89889b974506a0805062fd1089fb
解题思路
这是一个递归解法的苹果分配问题。关键点：
-
递归函数定义：
- getInitial(n, k, x)：表示还剩
头熊，当前苹果数为
时是否可行
：总熊数
- getInitial(n, k, x)：表示还剩
-
递归条件：
- 基础情况：k=0时返回true，表示所有熊都分完了
- 剪枝条件：(x-1)%n != 0时返回false，表示不能均分
- 递归：检查下一头熊分苹果的情况
-
主函数：
- 从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
