分糖果问题

分糖果问题

/**
此程序在node环境下执行
分析规律
假设 M = 10; k = 5; n = [1, 3, 4, 6, 10];
A[i]标记了小明在有i个糖果下并使用最优策略是否一定取胜，1代表取胜，0代表失败
1  A[1] = 1
2  A[2] = 0
3  A[3] = 1
4  A[4] = 1
5  A[5] = 1
6  A[6] = 1
7  A[7] = 0
8  A[8] = 1
9  A[9] = 0
10 A[10] = 1
分析可知：每次小明选取的糖果个数n[j](j代表n数组序号)以后，如果剩余糖果个数只要有一个A[i - n[j]]等于0则说明小明一定可以取胜，否则小华一定获胜
故可以使用动态规划解题，先出计算A[0]=0,A[1]=1,A[2]=0。
*/
//A是一个长度为M+1的数组，A[i]标记了小明在有i个糖果下并最优策略下是否一定取胜，1代表取胜，0代表失败
function candy(M, k, n) {
    let A = [];
    A[0] = 0;
    A[1] = 1;
    A[2] = 0;
    for (let i = 3; i <= M; i++){
        A[i] = 0;
        for (let j = 0; j <= k; j++){
            if ((i - n[j]) >= 0 && A[i - n[j]] === 0) {
                A[i] = 1;
                break;
            }
        }
    }
    console.log(`A=${JSON.stringify(A)}`);
    if (A[M] === 1) {
        console.log("小明");
    } else {
        console.log("小华");
    }
}
//用于在控制台输入和校验参数
let M;
let k;
let n = [];
console.log(`请输入M(1<=M<=500)`);
let inputParam = "M";
process.stdin.on('data', (input) => {
    input = input.toString().trim();
    if (inputParam === "M") {
        if (parseInt(input) >= 1 && parseInt(input) <= 500) {
            M = parseInt(input);
            console.log(`M=${M}`);
            inputParam = "k";
            console.log(`请输入k(1<=k<=50)`);
        } else {
            console.log(`输入M不合法，请重新输入！`);
        }

    } else if (inputParam === "k") {
        if (parseInt(input) >= 1 && parseInt(input) <= 50) {
            k = parseInt(input);
            console.log(`k=${k}`);
            inputParam = "n";
            console.log(`请输入n:每个数字在1和${M}之间且必须包含一个1，以英文逗号隔开,个数为k个`);
        } else {
            console.log(`输入k不合法，请重新输入！`);
        }
    } else if(inputParam === "n"){
        n = input.split(",");
        console.log(`n=${n}`);
        let input1 = false;
        for (let index = 0; index < n.length; index++){
            n[index] = parseInt(n[index]);
            if (n[index] >= 1 && n[index] <= M) {
                if (n[index] === 1) {
                    input1 = true;
                }
            } else {
                console.log(`输入n不合法，请重新输入！`);
                break;
            }
            if (index === n.length - 1) {
                if (input1 === false) {
                    console.log(`输入n中不包含1，请重新输入！`);
                    break;
                }
                if (n.length !== k) {
                    console.log(`输入n的长度要等于k，请重新输入！`);
                    break;
                }
                candy(M, k, n);
                process.exit(0);

            }

        }
    }
});

image.png