一. 题目-分月饼
中秋节，公司分月饼，m个员工，买了n个月饼，m<=n，每个员工至少分1个月饼，但可以分多个，单人分到最多月饼的个数是Max1，单人分到第二多月饼个数是Max2，Max1-Max2 <= 3，单人分到第n-1多月饼个数是Max(n-1)，单人分到第n多月饼个数是Max(n)，Max(n-1) – Max(n) <= 3, 问有多少种分月饼的方法？
输入描述：
每一行输入m n，表示m个员工，n个月饼，m<=n
输出描述：
输出有多少种月饼分法
补充说明：
收起
示例1
输入：
2 4
输出：
2
说明：
分法有2种：
4=1+3
4=2+2
注意：1+3和3+1算一种分法
示例2
输入：
3 5
输出：
2
说明：
5=1+1+3
5=1+2+2
示例3
输入：
3 12
输出：
6
说明：
满足要求的有6种分法：
12=1+1+10（Max1=10，Max2=1，不满足要求）
12=1+2+9（Max1=9, Max2=2, 不满足要求）
12=1+3+8（Max1=8, Max2=3, 不满足要求）
12=1+4+7（Max1=7, Max2=4, Max3=1，满足要求）
12=1+5+6（Max1=6, Max2=5, Max3=1，不满足要求）
12=2+2+8（Max1=8, Max2=2, 不满足要求）
12=2+3+7（Max1=7, Max2=3, 不满足要求）
12=2+4+6（Max1=6, Max2=4, Max3=2， 满足要求）
12=2+5+5（Max1=5, Max2=2，满足要求）
12=3+3+6（Max1=6, Max2=3, 满足要求）
12=3+4+5（Max1=5, Max2=4, Max3=3，满足要求）
12=4+4+4（Max1=4, 满足要求）
二.解题思路
这是一个关于分月饼的组合问题，要求每个员工至少分到一个月饼，但可以分多个。同时，限制了每个员工分到月饼的个数，使得相邻两个员工分到的月饼个数差不超过3。你可以使用递归来解决这个问题。
思路：
- 输入m和n，表示m个员工，n个月饼，m<=n。
- 初始化一个列表cakeMap，用于存储每个员工分到的月饼个数。
- 计算一个基准值base，使得base * m + 3 * m * (m - 1) / 2 < n。
- 从base开始，遍历每个员工分到的月饼个数，调用递归函数moonCake。
- 递归函数moonCake中，逐个员工确定月饼个数，保证相邻两个员工分到的月饼个数差不超过3。
- 如果idx（当前员工索引）等于m - 1，检查最后一个员工是否符合条件，是则累加res。
- 否则，继续递归调用moonCake，递增idx，更新月饼个数。
这段代码的核心是使用递归进行深度搜索，找到符合条件的分月饼方法。在递归过程中，通过不断更新cakeMap列表中的月饼个数来满足相邻员工的条件。最后，输出符合条件的分月饼方法的数量。
三.题解代码
Python题解代码
import sys
res = 0 # 初始化结果
n, m = 0, 0 # 定义变量n和m
def dfs(u, sum, down, up): # 定义深度优先搜索函数
global res # 声明全局变量res
if u == m: # 如果u等于m
if sum == 0: # 如果sum等于0
res += 1 # 结果加一
return # 返回
if down > sum or sum < 0 or down > up: # 如果down大于sum或sum小于0或down大于up
return # 返回
for i in range(down, up + 1): # 遍历down到up之间的值
dfs(u + 1, sum - i, i, min(sum - i, i + 3)) # 递归调用dfs函数
for line in sys.stdin: # 读取用户输入
m, n = map(int, line.strip().split()) # 将用户输入的字符串转换为数字
dfs(0, n, 1, n) # 调用dfs函数
print(res) # 输出结果
break
JAVA题解代码
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
public class Main {
private static int res = 0;
private static List<Integer> cakeMap;
private static int base = 1;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] keys = in.nextLine().split(" ");
int m = Integer.parseInt(keys[0]);
int n = Integer.parseInt(keys[1]);
if (m == 1) {
System.out.println(1);
return;
}
cakeMap = new ArrayList<Integer>(m);
int space = 3 * m * (m - 1) / 2;
while (base * m + space < n) {
base++;
}
for (int first = base; first <= n / m; first++) {
cakeMap.add(first);
moonCake(1, m, n - first);
cakeMap.remove(0);
}
System.out.println(res);
}
private static void moonCake(int idx, int m, int n) {
if (idx == m - 1) {
if (n - cakeMap.get(idx - 1) >= 0 && n - cakeMap.get(idx - 1) <= 3) {
res++;
}
return;
}
int lastCakes = cakeMap.get(idx - 1);
int restM = m - idx;
for (int i = lastCakes;i<=Math.min(lastCakes+3,n/restM);i++) {
cakeMap.add(i);
moonCake(idx+1,m,n-i);
cakeMap.remove(cakeMap.size()-1);
}
}
}
C/C++题解代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int w[N],n,m,res;
void dfs(int u,int sum,int down,int up){ //枚举分给第u个人时,月饼总量还剩下sum 第u个人能分到的最小月饼数量为down 最大月饼数量为up
if(u==m){
if(sum==0)res++;
return;
}
if(down>sum||sum<0||down>up)return; //不合法情况
for(int i=down;i<=up;i++){ //枚举下一个人所获得的月饼数量
dfs(u+1,sum-i,i,min(sum-i,i+3));
}
}
int main(){
cin>>m>>n;
dfs(0,n,1,n);
cout<<res<<endl;
return 0;
}
JS题解代码
const readline = require('readline'); // 引入readline模块
const rl = readline.createInterface({ // 创建readline接口
input: process.stdin, // 设置输入流
output: process.stdout // 设置输出流
});
let res = 0; // 初始化结果
let n, m; // 定义变量n和m
function dfs(u, sum, down, up) { // 定义深度优先搜索函数
if (u === m) { // 如果u等于m
if (sum === 0) { // 如果sum等于0
res++; // 结果加一
}
return; // 返回
}
if (down > sum || sum < 0 || down > up) { // 如果down大于sum或sum小于0或down大于up
return; // 返回
}
for (let i = down; i <= up; i++) { // 遍历down到up之间的值
dfs(u + 1, sum - i, i, Math.min(sum - i, i + 3)); // 递归调用dfs函数
}
}
rl.on('line', (line) => { // 监听用户输入
[m, n] = line.trim().split(' ').map(Number); // 将用户输入的字符串转换为数字
dfs(0, n, 1, n); // 调用dfs函数
console.log(res); // 输出结果
rl.close(); // 关闭readline接口
});
代码OJ评判结果
通过测试点
四.代码讲解(Java&Python&C++&JS分别讲解)
Python题解代码解析:
-
全局变量与输入初始化:
res: 全局变量，用于存储符合条件的月饼分法数量。n, m: 用于存储输入的员工数和月饼数。
-
深度优先搜索函数
dfs:- 参数：
u表示当前员工的索引，sum表示剩余的月饼数，down和up表示当前员工分到的月饼数量的范围。 - 判断递归结束条件：如果当前员工索引
u等于总员工数m，并且剩余月饼数sum等于 0，则将结果res增加 1。 - 判断递归合法性：如果
down大于sum或者sum小于 0 或者down大于up，则返回。 - 使用循环枚举下一个员工分到的月饼数量，调用递归函数。
- 参数：
-
读取用户输入并调用函数:
- 使用
for line in sys.stdin循环读取用户输入的每一行。 - 将输入的字符串转换为数字，并调用
dfs函数。 - 输出最终结果
res。
- 使用
JAVA题解代码解析:
-
全局变量与输入初始化:
res: 全局变量，用于存储符合条件的月饼分法数量。cakeMap: 用于存储每个员工分到的月饼个数。base: 初始化为 1，用于计算基准值。
-
主函数
main:- 使用 Scanner 读取用户输入的员工数
m和月饼数n。 - 如果员工数
m等于 1，直接输出 1。 - 计算基准值
base，使得base * m + 3 * m * (m - 1) / 2小于等于月饼数n。 - 使用循环遍历每个员工分到的月饼数量，调用递归函数
moonCake。
- 使用 Scanner 读取用户输入的员工数
-
递归函数
moonCake:- 参数：
idx表示当前员工的索引，m表示总员工数，n表示剩余的月饼数量。 - 递归结束条件：如果当前员工索引
idx等于m - 1，检查最后一个员工是否符合条件，是则累加res。 - 记录上一个员工分到的月饼数量
lastCakes和剩余员工数restM。 - 使用循环枚举下一个员工分到的月饼数量，调用递归函数。
- 参数：
-
输出结果:
- 输出最终结果
res。
- 输出最终结果
C/C++题解代码解析:
-
全局变量与输入初始化:
w[N]: 数组，用于存储每个员工分到的月饼数量。n, m, res: 用于存储输入的月饼数、员工数和结果。
-
深度优先搜索函数
dfs:- 参数：
u表示当前员工的索引，sum表示剩余的月饼数，down和up表示当前员工分到的月饼数量的范围。 - 判断递归结束条件：如果当前员工索引
u等于总员工数m，并且剩余月饼数sum等于 0，则将结果res增加 1。 - 判断递归合法性：如果
down大于sum或者sum小于 0 或者down大于up，则返回。 - 使用循环枚举下一个员工分到的月饼数量，调用递归函数。
- 参数：
-
主函数:
- 读取用户输入的月饼数
m和员工数n。 - 调用深度优先搜索函数
dfs。 - 输出最终结果
res。
- 读取用户输入的月饼数
JS题解代码解析:
-
全局变量与输入初始化:
res: 全局变量，用于存储符合条件的月饼分法数量。n, m: 用于存储输入的员工数和月饼数。
-
深度优先搜索函数
dfs:- 参数：
u表示当前员工的索引，sum表示剩余的月饼数，down和up表示当前员工分到的月饼数量的范围。 - 判断递归结束条件：如果当前员工索引
u等于总员工数m，并且剩余月饼数sum等于 0，则将结果res增加 1。 - 判断递归合法性：如果
down大于sum或者sum小于 0 或者down大于up，则返回。 - 使用循环枚举下一个员工分到的月饼数量，调用递归函数。
- 参数：
-
读取用户输入并调用函数:
- 使用
readline模块监听用户输入。 - 将输入的字符串转换为数字，并调用
dfs函数。 - 输出最终结果
res。
- 使用