We assume that the standard input contains a sequence of non

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. Write an algorithm, called Decomposition _Powers_Three, which produces the decomposition of each integer using powers of 3. namely I, 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 5 - 9 - 3 - 1 7-9-3+1 -14--27 + 9 +3+ 1 28 = 27 + 1 43 = 81 - 27 - 9 - 3 + 1 -121 = -81 - 27 - 9 - 3 - 1 Show that the algorithm Decomposition_Powers_Three is correct using an informal proof (i.e., discussion). Glive a program corresponding to Decomposition_Powers_Three, using C++ programming language. Observation: The intervals [-121, -41], 1-40, -14], (-13, -5], [-4, -2], [-1, -1], [1, 1], (2, 4], [5, 13], (14, 40], and (41, 121] play a particular role.

Solution

An approach is converting the number into the ternary base system. For example:

The decomposition of an integer using powers of three which are: 1, 3, 9, 27, and 81. Can only use the numbers once in each calculation.

example:

1 = 1

2 = 3 – 1

3 = 3

4 = 3 + 1

5 = 9 – 3 – 1