魔法师小遁手里没有硬币，现有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) {
//预防编写阶段进入死循环
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)
}
经过上面的思考我发现
应该总是先投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){
//防止陷入死循环
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机器也不能投，那岂不是存在无法得到的数？
是否真的存在当前算法无法得到的数？
经过几个数的测试 我发现如下规律
需要一个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)
}
显然这种解法要优于之前的，之前算法出现不能将已拥有所有硬币放入B机器时，可能会多出一步
