魔法師小遁手里沒有硬幣谒拴，現有A機器，投入硬幣后可得到2x+1個涉波，有B機器英上，投入硬幣可得到2x+2 個，
請幫助小遁獲得數目恰好的硬幣
1.窮舉法
在違法的邊緣試探.jpg
let x = 0;
//已有硬幣總數
let count = 10;
//想要獲得硬幣的總數
let j = 0;
put_x(0, 0, 0, [])
/*
i 投入的硬幣數目
x 已有硬幣數
size 已有硬幣數
stack 記錄投入的信息
*/
function put_x(i, x, size, stack) {
if (j++ > 1600) {
//預防編寫階段進入死循環(huán)
return;
}
let current = size;
let length = stack.length;
do {
//先投入A機器
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機器
//這里重新計算了 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)
}
經過上面的思考我發(fā)現
應該總是先投B機器啤覆，而且每次盡量投最多的硬幣
每次應該減去投進去的硬幣才是最終獲得硬幣數量
2 最少的投擲次數
我覺得ok.jpg
let j = 0;
coin(9);
function coin(count){
//記錄投入的信息
let stack = [];
computer(0,0);
console.table(stack)
/*
size 想要得到的硬幣數
*/
function computer(size,number){
//防止陷入死循環(huán)
if(j++ > 1600) return;
//由 count = 2*time - 2 - size 推導
//得到最多可以投入的硬幣數
//先投入B機器
let time = Math.floor(count - size - 2);
if(time < 0){//再次投入B機器會超出
//投入A機器
time = Math.floor(count - size - 1 );
number = time + 1 + size ;
//投入的機器 投入的硬幣數 得到的硬幣數 上次擁有的硬幣數 現擁有的硬幣數
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機器不需要time<0的判定苍日，是因為time數是推算出來的，如果B機器不能投窗声，A機器也不能投相恃，那豈不是存在無法得到的數？
是否真的存在當前算法無法得到的數笨觅？
經過幾個數的測試 我發(fā)現如下規(guī)律
需要一個1的時候才會用到A 因為奇數 = 偶數 - 1
總是可以通過投入B機器 來減少投入A機器需要得到的硬幣數 因為我們先投入B機器
因為投入B機器的硬幣數可以是奇數 => 產生偶數 + 上次總的是偶數 - 投入奇數取 = 奇數
所以并非所有奇數都會用到A機器（1拦耐，3，7會用到）
綜上所述 可以用
number = count ;
stack.push(['A',0,1,size,count])
代替if(time < 0) 里面的代碼
然而有一種叫做逆向推理的過程
為么不計算想要得到總數之前需要投入多少硬幣呢见剩，也就是每次把所擁有的硬幣都投入進去
打臉.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)于之前的杀糯，之前算法出現不能將已擁有所有硬幣放入B機器時，可能會多出一步
