javascript——m个月饼分给n个人_有一个0.5倍数的数字m,按照最小0.5分配给n个人,分不够的话给0分,用js如何实现

题目描述

        中秋节，公司分月饼，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

输出描述：

输出有多少种月饼分法

例：

输入

3 12

输出

6

解法1：动态规划 筛选出差值小于3的分配方法

/**
 * @param n 人数
 * @param m 月饼数
 * @param diff Max(n)-Max(n-1)
 */
function main1(n, m, diff) {
	if(m < n) {
		throw new Error("月饼数小于人数");
	}
 
	let result = [];
 
	// 月饼数与人数相等时
	if (n === m){
		result.push(new Array(n).fill(1));
		return result;
	}
 
	// 递归
	let ways = main1(n, m-1);
	ways.forEach(way => {
		way.forEach((item, i) => {
			let newway = [...way];
			newway[i] = item + 1;
			newway.sort(); // 将新分配方法排序
			if (!isExist(newway,result)){ //排除相同分法
				checkDiff(newway, diff) && result.push(newway);
				// result.push(newway);
			}
		});
	})
	return result;
}
 
/** 
 * 比较value数组是否存在总数组中
 * @params value 被比较的数组
 * @params list 总数组
 */
function isExist(value, list){
	return list.some(listItem => {
		if (value.length !== listItem.length){
			return false;
		}
		return listItem.every((childItem, index) => {
			if(value[index] !== childItem){
				return false;
			}
			return true;
		})
	})
}
 
function checkDiff(value, diff){
	if(typeof diff !== 'number' || diff < 0) {
		return true;
	}
	return value.every((item, index) => {
		if(index === 0) return true;
		if(item - value[index - 1] > diff){
			return false;
		}
		return true;
	})
}

解法2 

/**
 * @param n 人数
 * @param m 月饼数
 * @param diff Max(n)-Max(n-1)
 */
function main2(n, m, diff) {
 
	// 如果diff格式错误，则将其置为最大值 得到所有分配方法
	if(typeof diff !== 'number' || diff < 0) {
		diff = m;
	}
	// 人数大于月饼数 无法分配
	if (n > m) {
    	return 0;
    }
 
	// 每人分一个后 剩余月饼数
    const p = m - n;
 
    let count = 0;
 
    for(let k = 0; k < p; k++){
        count = count + distribute(n-1, p-k, k, diff);
    }
    return count;
}
 
/**
 * @param n 剩余未分配人数
 * @param p 剩余月饼数
 * @param k 当前被分配人得到的月饼数
 * @param diff Max(n)-Max(n-1)
 */
function distribute(n, p, k, diff) {
 
    if (p <= 0) return 0;
    if (n <= 0) return 0;
 
    if (n === 1) {
    	// 如果最后一个人应该获得的月饼数在剩余月饼数的范围之内
    	// 则存在新的一种分配方式 返回1
        if (p >= k && p <= k + diff) {
            return 1;
        }
        return 0;
    }
 
    let ncount = 0;
    // 迭代 当前被分配人获得 k+(0~diff) 个月饼时
    for (let knext = k; knext <= k + diff; knext++) {
        ncount = ncount + distribute(n-1, p-knext, knext, diff);
    }
    return ncount;
}