优化解决方案——我的作业

Question

优化解决方案——我的作业

5

一只蜗牛在白天爬上了x英尺的墙。经过一整天的劳作，它停下来休息了一会儿...但是睡着了！第二天早上醒来后，它发现在睡觉时滑落了y英尺。

如果这种情况每天都发生，那么蜗牛要爬n堵不同高度的墙，需要爬多少次？

我已经编写了一个函数来计算蜗牛爬行的次数，如下所示：

void count(int move_forward, int move_backward, int number_walls, int[] height)
    {
        int count = number_walls, diff = move_forward - move_backward;
        while (number_walls--)
            for (move_backward = move_forward; move_backward < height[number_walls]; move_backward += diff)
                count++;
    }

程序目前运行良好。但我想知道是否有其他方法来解决这个问题，以进一步优化程序的速度。

- iJade

3

（高度-x）/（x-y）+1，不需要循环。 - amit

2

@Jay，顺便说一句——在内部循环的上下文中使用有意义的变量名这个建议是有争议的。太多、太长的名称会使你的代码变得和一堆神秘的一两个字母的名称一样难以阅读。关键在于平衡。 - dmckee --- ex-moderator kitten

1

只是再多说一句，既然我已经插手了。这个练习的重点可能在于向你展示，通过静下心来思考一会儿，你可以将单个墙壁的问题从 O(height)（你尝试的方式）降至 O(1)（amit 的解决方式）。 - dmckee --- ex-moderator kitten

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

解决方案是((height-x)/(x-y))+1，不需要循环。

蜗牛需要爬到的高度为：height-x，他需要((height-x)/(x-y))天才能到那里。一旦到达那里，他需要额外花费一天来攀爬剩余的x。

编辑：正如评论中所提到的，此解决方案解决了每堵墙的问题，您需要遍历您的heights数组，并总结这些结果，至少可以省去内部循环，使其成为O(n)，而不是O(n*h)，其中n是墙的数量，h是墙的高度。

(*)注意：您可能希望保存每面墙[即蜗牛通过该墙后可以继续前进多少]的剩余部分，并从下一面墙中减去它，这取决于任务描述...如果蜗牛每天最多可以通过一堵墙，则忽略此最后一条评论。