1

我收到了以下挑战问题：

一个房间里有一圈一百个篮子；篮子按从 1 到 100 的顺序编号，每个篮子里有一个苹果。最终，篮子 1 中的苹果将被移除，但篮子 2 中的苹果将被跳过。然后将取出篮子 3 中的苹果。这将继续（绕圈移动，从篮子中取出一个苹果，跳过下一个），直到篮子里只剩下一个苹果。编写一些代码来确定剩下的苹果在哪个篮子里。

我得出结论，篮子 100 将包含最后一个苹果，这是我的代码：

     var allApples = [];
        var apples = [];
        var j = 0;
        var max = 100; 
        var o ='';
            while (j < max) {
                o += ++j;
                allApples.push(j);
            }

            var apples = allApples.filter(function(val) {
                return 0 == val % 2;
            });
            while (apples.length > 1) {
                for (i = 0; i < apples.length; i += 2) {
                    apples.splice(i, 1);
                }
            }

            console.log(apples);

我的问题是：我做对了吗？我关心的是对篮子“一圈”的描述。我不确定这与我如何编写解决方案有关。剩下的苹果所在的篮子是否会被跳过？

我希望有人可以让我知道我是否正确回答了这个问题，回答了部分正确或我的回答完全错误。谢谢您的帮助。

4

2 回答 2

1

我相信 Colin DeClue 是正确的，有一个声明可以解决这种模式。我真的很想知道这个答案。

这是我的蛮力解决方案。我没有将物品（“苹果”）从其原始容器（“篮子”）移到丢弃堆中，而是简单地将容器值从 true 或 false 更改为指示物品不再存在。

var items = 100;
var containers = [];

// Just building the array of containers
for(i=0; i<items; i++) {
    containers.push(true);
}

// count all containers with value of true
function countItemsLeft(containers) {
    total = 0;
    for(i=0; i<containers.length; i++) {
        if(containers[i]) {
            total++;
        }
    }
    return total;
}

// what is the index of the first container
// with a value of true - hopefully there's only one
function getLastItem(containers) {
    for(i=0; i<containers.length; i++) {
        if(containers[i]) {
            return(i);
        }
    }
    // shouldn't get here if the while loop did it's job
    return false;
}

var skip = false;
// loop through the items,
// setting every other to false,
// until there is only 1 left
while(countItemsLeft(containers) > 1) {
    for(i=0; i<containers.length; i++) {
        if(containers[i]) {
            if(skip) {
                skip = false;
            } else {
                containers[i] = false;
                skip = true;
            }
        }
    }
}

// what's the last item? add one to account for 0 index
// to get a human readable answer
var last_item  = getLastItem(containers) + 1;

需要错误检查等......但假设 items 是整数，它应该完成工作。

于 2013-04-03T19:53:58.843 回答
1

所以，......我也进入了这个问题:)

我打破了我上一个答案的输入/输出，这揭示了一个非常简单的模式。

基本上，如果项目总数是 2 的幂，那么它将是最后一个项目。之后的附加项目将使第二个项目成为最后一个项目。之后的每个附加项目将使最后一个项目增加 2，直到您达到另一个项目计数，该计数再次可以被 2 的幂整除。冲洗并重复。

仍然不是单线，但会比我之前的答案快得多。这不适用于 1 项。

var items = 100;

function greatestPowDivisor(n, p) {
    var i = 1;
    while(n - Math.pow(p, i) > 0) {
        i++;
    }
    return Math.pow(p, (i - 1));
}

var d = greatestPowDivisor(items, 2)
var last_item = (items - d) * 2;
于 2013-04-03T22:08:30.943 回答