Answered step by step
Verified Expert Solution
Link Copied!

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

image text in transcribedComputer 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

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Systems Design Implementation And Management

Authors: Carlos Coronel, Steven Morris

14th Edition

978-0357673034

More Books

Students also viewed these Databases questions

Question

Outline key considerations when making a hiring decision.

Answered: 1 week ago

Question

=+4 How did it affect HR?

Answered: 1 week ago