เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่ใช้ตัวเลข ฟังก์ชั่นควรแบ่งตัวเลขออกเป็นชิ้น ๆ ตามกฎต่อไปนี้ -
-
จำนวนชิ้นควรเป็นกำลังสอง
-
แต่ละอันควรมีกำลังสองของจำนวนไอเท็ม (โดยที่ขนาดเพิ่มเป็นกำลังสูงสุด 2 อัน ดังนั้น 1, 2, 4, 8, 16, 32, 32 เป็นค่าสูงสุด)
ดังนั้น ตัวอย่างเช่น 8 สามารถแบ่งออกเป็น 1 ถัง −
[8]
9 อาจเป็น -
[8, 1]
ได้ผลเพราะตัวเลขทั้งสองเป็นกำลังสอง และขนาดของอาร์เรย์คือ 2 (เช่นยกกำลังสองด้วย)
มาลองกัน 11 −
[8, 2, 1]
ไม่ได้ผล
เพราะขนาดของอาร์เรย์คือ 3 ซึ่งไม่ใช่กำลังสองถึงแม้จะรวมกันเป็น 11
[4, 4, 2, 1]
ได้ผล! เป็นธาตุ 4 อันเป็นกำลังสอง
ตัวอย่าง
รหัสสำหรับสิ่งนี้จะเป็น −
function permuteCombinations(n, maximum){
const maxPowerOf2 = 1 << maximum;
const m = ~~(n / maxPowerOf2);
const A = new Array(maximum + 1).fill(0);
A[maximum] = m;
let num = n − m * maxPowerOf2;
let p = 0;
let bitCount = 0;
while (num){
if (num & 1){
bitCount += 1;
A[p] = 1;
}
num >>= 1;
p += 1;
}
const min = m + bitCount;
let target = 1;
while (target < min)
target *= 2;
if (target > n)
return −1;
if (target == min)
return A.map((c, p) => [1 << Number(p), c]);
if (target == n)
return [n];
target = target − min;
let i = m ? maximum : p;
while (target && i > 0){
if (!A[i]){
i −= 1;
continue;
}
const max = Math.min(target, A[i]);
A[i] −= max;
A[i−1] += 2*max;
target −= max;
i −= 1;
}
return target ? −1 : A.map((c, p) => [1 << Number(p), c]);
};
console.log(permuteCombinations(11, 5)); ผลลัพธ์
และผลลัพธ์ในคอนโซลจะเป็น −
[ [ 1, 1 ], [ 2, 1 ], [ 4, 2 ], [ 8, 0 ], [ 16, 0 ], [ 32, 0 ] ]
