Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Computer Science. Please explain this. I have no idea what the question is even stating even after looking at the answer. Fall 2018 Algorithms and
Computer Science. Please explain this. I have no idea what the question is even stating even after looking at the answer.
Fall 2018 Algorithms and Analysis Tools Exam, Part B 3) (10 pts) ALG (Backtracking) We define a number as Digit Sum Divisible if, for each value of i, the sum of its first i digits is divisible by i. For example, the number 6451 is Digit Sum Divisible because 6 is divisible by 1, 6 + 4 = 10 is divisible by 2, 6+4 + 5 = 15 is divisible by 3 and 6 + 4+ 5+1 = 16 is divisible by 4. Consider writing a backtracking function that outputs all Digit Sum Divisible numbers of a particular length given a particular prefix. This function would take in a prefix, such as "64" and a number of digits left to add to it (for this example, 2), and the function would print out each Digit Sum Divisible number starting with the digits 64 that are four digits long. The function would use backtracking because instead of adding each possible digit to the given prefix and making a recursive call, it would first check to see if doing so would maintain the divisibility requirement for the next length. (In this example, 640 would be skipped since 6 + 4 + 0 = 10 and 10 isn't divisible by 3.) Write out a tree structure that shows each unique prefix that occurs for each recursive call for the specific function call with the prefix 64 and 2 digits left to add to it. (Note: The root node of your tree should be 64, each child of 64 should be a three digit number, and each child of those children should have a four digit number. There should be eight leaf nodes in the tree, so make sure to leave enough room for eight nodes at the bottom level. These leaf nodes are the eight numbers the function would print out for this specific call.) Note: Please do NOT write any code for this problem, just write out the underlined specified task above. 64,2 642,1 645,1 648,1 1 1 1 6420 6424 6428 6451 6455 6459 6482 6486 (all calls on the last level have a k=0 with them)Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started