Description
You are given a list of numbers:
[28, 22, 7, 2, 8, 14, 24, 56]
.
.
Your task is to find the longest sub-set of this list, such that all of the items in the subset can be taken as
pairs where the larger value of the pair is perfectly divisible by the smaller. For example, in the above
list there is a sub-set
. This sub-set satisfies the “divisibility requirement” because all
{8, 2, 24}
the pairings demonstrate perfect divisibility:
,
, and
8/2 = 4
24/8 = 3
24/2 = 12
However
is
not the longest
sub-list that can be found that satisfies the divisibility
{8, 2, 24}
requirement. That would be:
Another would be:
{7, 14, 28, 56}
. Actually, there are multiple possible answers.
{2, 14, 28, 56}
Write a program that finds the longest and “pair-wise divisible” sub-set of a given list of numbers. You should implement the following functions:
vector<int> largest_divisible_pairs(vector<int> input);
string vec_to_string(vector<int> v);
Note, your program should work with any list that (a) contains only positive numbers and (b) does not contain any duplicate numbers. You may write a test() function, or you might hard-code a list into your main method. In either case, know that your program will be tested (graded) using a variety of input lists. In general your program only needs to output one solution, even when there are multiple solutions possible.
Pro-Tip: Using recursion to solve this problem is a good strategy.
Sample Output:
user@machine:solution$ ./ldp Input: [28 22 7 2 8 14 24 56] Answer: [56 14 7 28]
Submission: Your program will be submitted using canvas and git + github.
1) You should create a private github.com repository (repo) with your code in it. You may need to create a github user account and a github repository. To achieve this. The name you choose for the repo and your username are arbitrary but I suggest “HW4” as the repo name.
2) Your repository on github.com should be private and you should add my account as a collaborator by going to “settings” → “manage access” → “invite collaborator” and entering my username: fmresearchnovak
3) On canvas you should upload a link to this github repository
https://github.com/fmresearchnovak/HW4.git
I.
