开发者

Optimized solutions for my homework

A snail creeps x ft up a wall during the daytime. After all the labor it does throughout the day, it stops to rest a while... but falls asleep!! The next morning it wakes up and discovers that it has slipped down y ft while sleeping.

If this happens every day, how many times will the snail creep to cover n walls of different height?

I have written a function to count the number of creeps of the snail as shown below:

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 < 开发者_C百科height[number_walls]; move_backward += diff)
                count++;
    }

It's working fine. But I wanted to know if there is any other way of solving this problem to optimize the speed of the program further.


solution is ((height-x)/(x-y))+1, no loops required.

the snail needs to climb to: height-x, and it takes him ((height-x)/(x-y)) days. Once it is there, it takes him an extra day to climb the remaining x.

EDIT: as mentioned in the comments, this solution solves the problem for each wall, you'll need to iterate over your heights array, and summarize these results, saving you at least the inner loop, making it O(n), instead O(n*h), where n is the number of walls, and h is the walls' heights.

(*)note: that you might want to save the reminder for each wall [i.e. how much the snail can keep going after he had passed this wall], and subtract it from the next wall, dependes on the task description... If the snail can pass a maximum of one wall per day, ignore this last comment.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜