Problem Statement: We assume that the standard input contains a sequence of non-zero integers between – 121 and 121, which ends with 0. This sequence will be given by the user. 1. Write an algorithm, called Decomposition_Powers_Three, which produces the decomposition of each integer using powers of 3, namely 1, 3, 9, 27, and 81, and the + and operators. Each power of 3 should appear at most once in the decomposition. Examples: 1 = 1 2 = 3 1 3 = 3 4 = 3 + 1 7 = 9 3 + 1 14 = 27 9 3 1 43 = 81 27 9 3 + 1 121 = 81 + 27 + 9 + 3 + 1 2. Show that the algorithm Decomposition_Powers_Three is correct using an informal proof (i.e., discussion). 3. Give a program corresponding to Decomposition_Powers_Three, using any of your favorite programming languages. Observation: The intervals [-121,-41], [-40,-14], [-13,-5], [-4,-2], [-1,-1], [1,1], [2,4], [5,13], [14,40], and [41,121] play a particular role. Deliverables: Students may choose to work in team of up to two members. You should turn in a report explaining all the design decisions and your code should be commented appropriately for readability and understanding. More precisely, a report should include the problem statement, proposed approach/solution along with a detailed discussion, algorithm (high-level description of all the design parts along with some details when necessary), commented code, tests (input given by the user and output generated by your program execution), and lessons learned from such an implementation experience.
