Arrays
Imagine you had a travel scheme where by for every city you visited you had a mapping of what city you would travel to next. You are curious what is the longest chain (or cycle) of cities you could visit before returning to where you started. For example if your mapping was:
Current Next
LA NY
NY Seattle
Denver Chicago
Chicago Denver
Seattle LA
Then, if you found yourself in LA then you would go to NY, then Seattle, then back to LA where you started. You visited 3 cities before returning to the starting point. However, if you found your self in Chicago you would go to Denver and then back again to Chicago. You visited only 2 cities before returning. We are going to write a program that performs similar computations.
Description & Requirements
In this program, the user will enter some permutation of the integers 0 to n-1, inclusive, (each integer in that range will appear exactly once) followed by -1 to indicate the end of the input. The user will never input more than 100 numbers. Your job is to store all the numbers in an array in the order they are input. For example if the user inputs 3 0 2 1 -1 then you should store the 3 at index 0 in an array, 0 at index 1, 2 and index 2, and 1 at index 3. Once you have stored the data in your array your task is to find the maximum length cycle in the array. To answer the question, "What does cycle mean?", interpret the value at index i as the next index in the array that we should visit. So in the example above, at index 0 is the value 3. This indicates that we should go visit index 3 of the array next. Once we go to index 3 we find the value 1. This tells us to go visit index 1 next. Once we go to index 1 we find the value 0. This tell us to go visit index 0 next. But we've already visited index 0 (it's where we started). If and when you get back to your starting location (i.e. we started at location 0 and then got back to that location because the value at index 1 told us to go to 0) we stop and define those indices to be a cycle. So in this case the cycle is created from index 0 3 1 (and then back to 0). This cycle has a length of 3 since it tooks us 3 steps to get back to the starting location. Your job is to detect the longest (max number of steps to get back to the starting point) cycle in the array. Notice, once we start at 0 and find a cycle of length 3, we could then repeat the process starting at index 1. As we start at index 1 we would visit 0, from 0 we would go to 3, and from 3 back to 1. The same cycle is detected and thus its length is the same. We have not found anything longer. From there we could look for a cycle starting at location 2. At index 2 we find the value 2 which tells us to simply stay put (or go back to itself). Thus, we have a cycle of length 1 since 2 only requires one step before we get back to the starting point. By doing this cycle-walking process starting at each point in the array we can determine the longest cycle.
Note: You may realize there is some inefficiency in what we've described. We would find the cycle of 0 3 1 three times as we start our search from 0, then from 1, and finally from 3. You can potentially use another array to avoid this duplicated work, but you are not required to do so. It is fine to use an "inefficient" approach to solve this problem.
Your program should only output a single number on the last line of output which should be the length of the longest cycle present in the array.
Example 1
If the user entered:
3 0 2 1 -1
Your program should output exactly the lines:
3
Need some help on this problem ASAP. It's due tonight.
Current Next
LA NY
NY Seattle
Denver Chicago
Chicago Denver
Seattle LA
Then, if you found yourself in LA then you would go to NY, then Seattle, then back to LA where you started. You visited 3 cities before returning to the starting point. However, if you found your self in Chicago you would go to Denver and then back again to Chicago. You visited only 2 cities before returning. We are going to write a program that performs similar computations.
Description & Requirements
In this program, the user will enter some permutation of the integers 0 to n-1, inclusive, (each integer in that range will appear exactly once) followed by -1 to indicate the end of the input. The user will never input more than 100 numbers. Your job is to store all the numbers in an array in the order they are input. For example if the user inputs 3 0 2 1 -1 then you should store the 3 at index 0 in an array, 0 at index 1, 2 and index 2, and 1 at index 3. Once you have stored the data in your array your task is to find the maximum length cycle in the array. To answer the question, "What does cycle mean?", interpret the value at index i as the next index in the array that we should visit. So in the example above, at index 0 is the value 3. This indicates that we should go visit index 3 of the array next. Once we go to index 3 we find the value 1. This tells us to go visit index 1 next. Once we go to index 1 we find the value 0. This tell us to go visit index 0 next. But we've already visited index 0 (it's where we started). If and when you get back to your starting location (i.e. we started at location 0 and then got back to that location because the value at index 1 told us to go to 0) we stop and define those indices to be a cycle. So in this case the cycle is created from index 0 3 1 (and then back to 0). This cycle has a length of 3 since it tooks us 3 steps to get back to the starting location. Your job is to detect the longest (max number of steps to get back to the starting point) cycle in the array. Notice, once we start at 0 and find a cycle of length 3, we could then repeat the process starting at index 1. As we start at index 1 we would visit 0, from 0 we would go to 3, and from 3 back to 1. The same cycle is detected and thus its length is the same. We have not found anything longer. From there we could look for a cycle starting at location 2. At index 2 we find the value 2 which tells us to simply stay put (or go back to itself). Thus, we have a cycle of length 1 since 2 only requires one step before we get back to the starting point. By doing this cycle-walking process starting at each point in the array we can determine the longest cycle.
Note: You may realize there is some inefficiency in what we've described. We would find the cycle of 0 3 1 three times as we start our search from 0, then from 1, and finally from 3. You can potentially use another array to avoid this duplicated work, but you are not required to do so. It is fine to use an "inefficient" approach to solve this problem.
Your program should only output a single number on the last line of output which should be the length of the longest cycle present in the array.
Example 1
If the user entered:
3 0 2 1 -1
Your program should output exactly the lines:
3
Need some help on this problem ASAP. It's due tonight.
Please, do not doublepost. Other thread: http://www.cplusplus.com/forum/general/224490/
Topic archived. No new replies allowed.