为我的家庭作业优化解决方案

Question

在白天,一只蜗牛爬上墙壁x ft.经过一整天的劳动,它停下来休息了一会儿......但是睡着了!! 第二天早上它醒来时发现它在睡觉的时候滑倒了.

如果每天都发生这种情况,蜗牛会爬出多少次覆盖不同高度的墙壁？

我编写了一个函数来计算蜗牛的蠕变数,如下所示:

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++;
    }

它工作正常.但我想知道是否还有其他方法可以解决这个问题,以进一步优化程序的速度.

Answer 1

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

蜗牛需要爬到:height-x它需要((height-x)/(x-y))几天时间.一旦它在那里,他需要额外的一天来爬上剩余的x.

编辑:正如评论中提到的,这个解决方案解决了每个墙的问题,你需要迭代你的heights数组,并总结这些结果,至少为你节省内部循环,使其成为O(n),而不是O( n*h),其中n是墙的数量,h是墙的高度.

(*)注意:您可能希望保存每个墙的提醒[即蜗牛在通过此墙后可以保持多少],并从下一个墙中减去它,取决于任务描述...如果蜗牛每天最多可以通过一面墙,忽略最后一条评论.