首页 > 代码库 > 算法练习--小球下落
算法练习--小球下落
小球下落:
全然二叉树。最大深度D。所有节点从上到下从左到右编号为1,2,3...2的D次方-1.在节点1处放一个小球。它会往下落。
全然二叉树。最大深度D。所有节点从上到下从左到右编号为1,2,3...2的D次方-1.在节点1处放一个小球。它会往下落。
每一个内节点上都由一个开关,初始所有关闭。当每次有小球落到一个开关上时,它的状态都会改变。当小球达到一个内节点时,假设该节点上的开关关闭,往左走,否则往右走,直到遍历到叶子节点。
问题。输入 深度和小球个数
输出节点编号
输入 4 2 输出 12
输入 3 4 输出 7
參考实现
function f(depth,count){ var states = new Array(); var r; for(var i = 0;i < count;i++){ for(var root = 1;root <Math.pow(2,depth-1);){ if(states[root] && states[root].open){ states[root].open = false; root = root * 2 + 1; } else{ if(!states[root]){states[root]={open:true};} else if(states[root].open == false){states[root].open = true;} root = root * 2; } r=root; } } return r; } console.log(f(4,2)); console.log(f(3,4)); console.log(f(10,1)); console.log(f(2,2)); console.log(f(8,128)); console.log(f(16,12345));
算法练习--小球下落
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。