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

Question

白天，一只蜗牛爬上一堵墙 x 英尺。在完成了一整天的所有工作后，它停下来休息了一会儿……但睡着了!!第二天早上它醒来，发现它在 sleep 时滑倒了 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++;
    }

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

Answer 1

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

蜗牛需要爬到:height-x，他需要 ((height-x)/(x-y)) 天。一旦到达那里，他就需要额外一天的时间才能爬完剩下的 x。

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

(*)注意:您可能希望为每面墙保存提醒 [即蜗牛在通过这堵墙后还能继续前进多少]，并从下一堵墙中减去它，这取决于任务描述……如果蜗牛每天最多可以通过一堵墙，请忽略最后一条评论。