Weekly Exercise #7 Divide & Conquer

CMPUT 275 – Tangible Computing II Winter 2021
Weekly Exercise #7
Divide & Conquer
Mountain climbing
You are provided with a strictly increasing array of positive integers heights, and two positive integers rest and limit. The array heights represents the various heights (in feet)
of ledges on a cliff. The value rest represents how many seconds you have to rest between
climbing bursts (see the description below). The value limit is how many seconds you have
to climb the cliff, and is guaranteed to be at least the last height in the array.
Suppose you are able to climb 1 foot per second consecutively for a certain amount of time,
let’s call this time burst. However, after at most burst seconds you have to rest for rest
seconds on one of the ledges of the cliff to regain your stamina. You cannot rest while hanging on to the cliff, you have to be on a ledge when you rest. You rest the same amount of
time even if your latest climb was not for burst seconds.
Your task is to find the minimum value of burst such that you are able to reach the highest
ledge in at most limit seconds. To do this you will write a function with the following
signature:
uint climbing(const uint *heights, uint length, uint rest, uint limit);
where length is the number of integers in the array, and uint is another name for unsigned
int defined using typedef. This function should return the minimum value of burst.
Example:
uint mountain[] = {30, 70, 95, 120, 145, 190};
std::cout << climbing(mountain, 6, 10, 210) << std::endl;
Output:
70
Explanation:
If you can climb for 70 seconds consecutively between rests, then:
• In your first burst, you can reach ledge 70.
• In your second burst, you can reach ledge 120.
• In your final burst, you reach the top.
In total, you spend 190 seconds climbing and 20 seconds resting, which is exactly the value
of limit (hence not exceeding it).
However, if you can only climb for 69 seconds then the fastest you can climb the cliff is:
• In your first burst, you can only reach ledge 30.
• In your second burst, you reach ledge 95.
• In your third burst, you reach ledge 145.
• Finally, you reach ledge 190.
In total, you spent 190 seconds climbing and 30 seconds resting, too long!
Example:
uint mountain[] = {50, 100};
std::cout << climbing(mountain, 2, 1, 100) << std::endl;
Output:
100
Explanation:
You can reach the top in a single burst if you can climb for 100 seconds consecutively.
However, if you can only climb for 99 seconds consecutively then the best you can do is
reach ledge 50, rest for 1 second, then reach the top for a total of 101 seconds.
Example:
uint mountain[] = {50, 99};
std::cout << climbing(mountain, 2, 1, 100) << std::endl;
Output:
50
Explanation:
If you can climb for 50 seconds consecutively then you can reach the ledge at height 50 in
your first burst, rest for 1 second, then reach the top after 49 more seconds for a total of 100
seconds. But if you can only climb for 49 seconds consecutively then you can’t even reach
the first ledge!
For full marks, your algorithm must run in O(length · log(limit)) time.
Starter Code
You will implement your function in climbing.cpp. A driver file driver.cpp that has a
main function is provided so that you can test your implementation.
Submission Guidelines
Submit all of the following files as a divide-and-conquer.tar.gz or divide-and-conquer.zip
file:
• climbing.cpp which contains the implementation of your solution. Do not write a
main function in this file.
• driver.cpp which is the same driver file that is included in the starter code. You won’t
change this file.
• your README file (following the Code Submission Guidelines).
• a Makefile with these targets:
– climbing: links all objects required for testing the climbing function and builds
an executable called climbing.
– climbing.o: compiles climbing.cpp.
– clean: removes all executable and object files.
You may add additional targets if needed.
Grading Comments
• We will be testing your program with a different driver file that will replace driver.cpp.
This driver file also contains a main function.
• Style matters. Add file header to the file you submit. Use appropriate comments,
proper indentation, etc. Consult the style guide on eClass.