魔法師小遁手里沒有硬幣，現(xiàn)有A機(jī)器，投入硬幣后可得到2x+1個，有B機(jī)器，投入硬幣可得到2x+2 個，
請幫助小遁獲得數(shù)目恰好的硬幣

1.窮舉法

在違法的邊緣試探.jpg

let x = 0;
//已有硬幣總數(shù)
let count = 10;
//想要獲得硬幣的總數(shù)    

let j = 0;
put_x(0, 0, 0, [])
/* 
    i 投入的硬幣數(shù)目
    x 已有硬幣數(shù)
    size 已有硬幣數(shù)
    stack  記錄投入的信息
*/
function put_x(i, x, size, stack) {
    if (j++ > 1600) {
        //預(yù)防編寫階段進(jìn)入死循環(huán)
        return;
    }
    let current = size;
    let length = stack.length;
    do {
        //先投入A機(jī)器
        size = current + 2 * i + 1;
        stack[length] = i;
        stack[length + 1] = 1;
        stack[length + 2] = size;
        if (size < count) {
            put_x(0, size, size, [].concat(stack))
        } else {
            if (size == count) {
                console.log(size, stack)
            }
            return;
        }

        //放入B機(jī)器
        //這里重新計算了 size 以及stack的信息

        size = current + 2 * i + 2;
        stack[length] = i;
        stack[length + 1] = 2;
        stack[length + 2] = size;
        if (size < count) {
            put_x(0, size, size, [].concat(stack))
        } else {
            if (size == count) {
                console.log(size, stack)
            }
            return;

        }
        i++;

    } while (i <= x)
}

經(jīng)過上面的思考我發(fā)現(xiàn)

應(yīng)該總是先投B機(jī)器，而且每次盡量投最多的硬幣
每次應(yīng)該減去投進(jìn)去的硬幣才是最終獲得硬幣數(shù)量

2 最少的投擲次數(shù)

我覺得ok.jpg

let j = 0;
coin(9);
function coin(count){

    //記錄投入的信息
    let stack = [];
    
    computer(0,0);
    console.table(stack)
    /*
        size  想要得到的硬幣數(shù)
    */
    function computer(size,number){
        //防止陷入死循環(huán)
        if(j++ > 1600) return;

        //由 count = 2*time - 2 - size 推導(dǎo)  
        //得到最多可以投入的硬幣數(shù)
        //先投入B機(jī)器
        let time = Math.floor(count - size - 2);
        
        
        if(time < 0){//再次投入B機(jī)器會超出
            //投入A機(jī)器
            time =  Math.floor(count - size - 1 );
            number = time + 1 + size ;
            //投入的機(jī)器  投入的硬幣數(shù)  得到的硬幣數(shù) 上次擁有的硬幣數(shù)  現(xiàn)擁有的硬幣數(shù) 
            stack.push(['A',time,2*time+1,size,number])
        }
        else{
            if(time > number){//防止投入的硬幣超出已有的
                time = number;
            }
            number = time + 2 + size;
            stack.push(['B',time,2*time+2,size,number])
        }
        
        if(number < count){
            computer(number,number);
        }

    }

}

image.png

為什么投入A機(jī)器不需要time<0的判定，是因為time數(shù)是推算出來的，如果B機(jī)器不能投，A機(jī)器也不能投，那豈不是存在無法得到的數(shù)？

是否真的存在當(dāng)前算法無法得到的數(shù)？

經(jīng)過幾個數(shù)的測試 我發(fā)現(xiàn)如下規(guī)律

需要一個1的時候才會用到A 因為奇數(shù) = 偶數(shù) - 1
總是可以通過投入B機(jī)器 來減少投入A機(jī)器需要得到的硬幣數(shù) 因為我們先投入B機(jī)器
因為投入B機(jī)器的硬幣數(shù)可以是奇數(shù) => 產(chǎn)生偶數(shù) + 上次總的是偶數(shù) - 投入奇數(shù)取 = 奇數(shù)
所以并非所有奇數(shù)都會用到A機(jī)器（1，3，7會用到）

綜上所述 可以用

number = count ;
stack.push(['A',0,1,size,count])

代替if(time < 0) 里面的代碼

然而有一種叫做逆向推理的過程

為么不計算想要得到總數(shù)之前需要投入多少硬幣呢，也就是每次把所擁有的硬幣都投入進(jìn)去

打臉.jpg

computer(110);
function computer(count){

    let stack = [];
    let size = count;
    let lastSize = size;
    while(size>0){
        
        if(size%2 == 0){
            size = Math.floor((size - 2)/2);
            stack.push(['B',size,lastSize])
        }
        else{
            size = Math.floor((size - 1)/2)
            stack.push(['A',size,lastSize])
        }
        lastSize = size;
        
    }
    console.table(stack)
}

顯然這種解法要優(yōu)于之前的，之前算法出現(xiàn)不能將已擁有所有硬幣放入B機(jī)器時，可能會多出一步