Project 1: 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 -14 = -27 + 9 + 3 + 1

43 = 81 27 9 3 + 1

Show that the algorithm Decomposition_Powers_Three is correct using an informal proof

(i.e., discussion).

Give a program corresponding to Decomposition_Powers_Three, using C++ programming

language.

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.