Question

Professor drives a Tesla to travel from city ? to city ?. The distance between cities ? and ? is ? miles. The Tesla can go up to ? miles before it needs a charge and there are many charging locations along the way including those in city ? and city ?. Professor wants to minimize the number of charges needed so he can get to his destination ASAP. Assume that at any charging location there is at least another charging location within a t mile radius.

For example, for ? = 10, t = 4 and the following charging locations (underlined)
(?)1 2 3 4 5 6 7 8 9 10 11(?)

the numbers of charges needed is 2 (at #4 and #8).

Professor ? promises to give you an A in his class if you can design a procedure to help him to achieve the goal. Does your procedure provide an optimal solution? Why or why not? Write a pseudo-code for your procedure. Show its correctness and complexity.

Please use C++.This is all of the given information.

Answer 1

The idea is simple to start from t and move with and increment of +t , till we reach the end,

This will execute in O(n) time and is the most optimal solution if we want to desiplay the stations , if we simply want to show number of stops , that can be done in O(1) time , so we can say the procedure is the optimal one.

Pseudocode

1. Get n and t from user
2. while t<n,
   1. diplay t
   2. set t =t t+t
3. Exit

C++ Code

#include <iostream>

using namespace std;

//main driver code of the program

int main()

{

    //gte inputs from user

    int n, t;

    cout << "Enter value of n and t : ";

    cin >> n >> t;

    int org_t=t;//to store original vale

    //run loop

    while (t < n)

    {

        cout << t << " ";

        t += t;

    }

    cout<<"\nCharging Stations needed : "<<(n/org_t);

}

Screenshot

Proof of correctness

time complexity is O(n)