算法问题:鸡块有 7/13/29 三种规格,老板让你买 n 块,如何计算是否可行

平静的格子
  • 1
新手上路,请多包涵

问题:在一个平行宇宙中,麦当劳的麦乐鸡块分为 7 块装、13 块装和 29 块装。有一天,你的老板让你出去购买正好为 n 块(0 < n <= 10000)的麦乐鸡块回来,请提供一个算法判断是否可行。

说明:除了三重循环的解法,有没有效率更高一点的方法。求大佬指点。

回复
阅读 1.6k
3 个回答
风研雨墨
  • 360
function countAll(i, j, k, total) {
    if ((i * 7 + j * 13 + 29 * k) > total) {
        return false;
    }
    if (total === 7 || total === 13 || total === 29) {
        return true;
    }
    if (isVoid(i, j, k, total)) {
        return true;
    } else {
        return countAll(i, j, k + 1 , total) || countAll(i , j + 1, k , total) || countAll(i + 1, j , k , total) ||  false;
    }
}

function isVoid(i, j, k, total) {
    let value = i * 7 + j * 13 + 29 * k;
    if (total % value == 0 && value !== 0) {
        console.log(i , j  , k);
        return true;
    }
    return false;
}
var res = countAll(0, 0 , 0 ,9892);
console.log(res);

递归实现

千江月影
  • 547

取巧的一个思路,反正 n块(0< n <= 10000)

  1. 直接拿到 0-10000 里 7,13,29 所有可能构成的取值,建立哈希表,结束了
  2. 效率肯定很高
gaoryrt
  • 4k
const checkNuggets = (nuggets) => {
    let temp = []
    temp[7] = true
    temp[13]-= true
    temp[29] = true
    for (let i = 7; i < nuggets; i+= 1) {
        if (temp[i]) {
            temp[i + 7] = true
            temp[i + 13] = true
            temp[i + 29] = true
        } else continue
    }
    return !!temp[nuggets]
}

console.log(checkNuggets(25)) // false
console.log(checkNuggets(26)) // true
console.log(checkNuggets(27)) // true
console.log(checkNuggets(28)) // true
console.log(checkNuggets(29)) // true
console.log(checkNuggets(30)) // false

image.png

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏