C++

Forum

 
Decomposition Powers Three

DeathLeap (221)
So I am trying to write a program that produces the decomposition of an integer using powers of three which are: 1, 3, 9, 27, and 81.

example:

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

How can I start with such a problem? I'd appreciate your help.

Xclusive198 (7)
Seems like you'll need a variable for 1 and 3 to start. Those are your main variables and you can derive any number with those two.

What is this program trying to accomplish, exactly?

Is it suppose to include all real values that can be decomposed by the power of three, or only up until 121?
DeathLeap (221)
this program basically asks the user to input an integer. Then, the program should decompose that integer into integers which are powers of 3. for example:

7 can be decomposed to 9 - 3 + 1

Last edited on
giblit (3750)
I had something really long typed out... Then my browser crashed and lost it..Anyways it was something along the ling of you should look for values which are closest and work with them and not pick random values.

short example
Notes: equal or less = add next
greater = subtract next

123
closest is 81 (it is less so we add) current result: 81
distance = 123 - 81 = 42
closest is 27 (it is less so we add) current result: 81 + 27 = 108
distance = 42 - 27 = 15
closest is 9(it is less so we add) current result: 81 + 27 + 9 = 117
distance = 15 - 9 = 6
closest is 3(it is less so we add, we choose smallest of the closest to avoid subtracting) current result: 81 + 27 + 9 + 3 = 120
distance = 6 - 3 = 3
closest is 3(it is equal so we add) current result: 81 + 27 + 9 + 3 + 3 = 123

Coding this shouldn't be too difficult.

*eidt when I say add/subtract I mainly mean flip the next operation (starting with add)

60
closest = 81 current result: 81 -
distance = 21
closet = 27 current result: 81 - 27 +
distance = 6
closet = 3 current result: 81 - 27 + 3 +
distance = 3
closest = 3 current result: 81 - 27 + 3 + 3

so lets look at it now:
81 - 27 = 54
54 + 3 = 57
57 + 3 = 60

Last edited on
DeathLeap (221)
What kind of structures can I use to code this? and is it necessary to use modulus operator: % to accomplish this?

Edit: Sorry but I still don't understand how will I use the information you put and code it. I just don't understand the concept I guess. Can you explain it differently? Sorry for holding you up. And I really really appreciate your help!
Last edited on
giblit (3750)
You should be fine with a container for the factors of 3, and then a string for the result. I will write up an example but might take a few mins.
giblit (3750)
It's not very clean and might have a few bugs but I put this together pretty quickly so sorry ahead of time. Hopefully you can use some of this to work on yours. Please don't just copy paste it would be nice if you learned from it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
 
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <sstream>

int main()
{
    int result;
    std::cout << "Please enter the desired result: ";
    std::cin >> result;

    std::vector<int> const table = {1, 3, 9, 27, 81}; //set might be better but oh well

    std::string answer = "";

    int temp = result;
    bool add = true;
    while(temp)
    {
        int distance = std::abs(temp - 1); //you can get absolute manually really easy
        int closest = 1;
        for(std::size_t i = 1; i < table.size(); ++i) //might be able to get away with less iterations but its only 4 so no big deal
        {
            int tempDistance = std::abs(temp - table[i]);
            if(distance && distance > tempDistance) //make sure we didn't find a perfect match and its decreasing distance
            {
                distance = tempDistance;
                closest = table[i];
            }
            else
            {
                break; //getting farther away or we found a match no need to continue
            }
        }
        if(closest > temp)
        {
            add = !add;
        }
        temp = distance;
        if(temp) //the last number finished equation so don't putt sign at end
        {
            std::ostringstream ss;
            ss << closest;
            answer += ss.str();
            answer += add ? '+' : '-';
        }
        else
        {
            std::ostringstream ss;
            ss << closest;
            answer += ss.str();
        }
    }

    std::cout << result << " = " << answer << std::endl;
}
 
1 = 1
2 = 1+1
3 = 3
4 = 3+1
5 = 3+1+1
6 = 3+3
7 = 9-1-1
8 = 9-1
9 = 9
10 = 9+1
11 = 9+1+1
12 = 9+3
13 = 9+3+1
14 = 9+3+1+1
15 = 9+3+3
16 = 9+9-1-1
17 = 9+9-1
18 = 9+9
19 = 27-9+1
20 = 27-9+1+1
21 = 27-3-3
22 = 27-3-1-1
23 = 27-3-1
24 = 27-3
25 = 27-1-1
26 = 27-1
27 = 27
28 = 27+1
29 = 27+1+1
30 = 27+3
31 = 27+3+1
32 = 27+3+1+1
33 = 27+3+3
34 = 27+9-1-1
35 = 27+9-1
36 = 27+9
37 = 27+9+1
38 = 27+9+1+1
39 = 27+9+3
40 = 27+9+3+1
41 = 27+9+3+1+1
42 = 27+9+3+3
43 = 27+9+9-1-1
44 = 27+9+9-1
45 = 27+9+9
46 = 27+27-9+1
47 = 27+27-9+1+1
48 = 27+27-3-3
49 = 27+27-3-1-1
50 = 27+27-3-1
51 = 27+27-3
52 = 27+27-1-1
53 = 27+27-1
54 = 27+27
55 = 81-27+1
56 = 81-27+1+1
57 = 81-27+3
58 = 81-27+3+1
59 = 81-27+3+1+1
60 = 81-27+3+3
61 = 81-27+9-1-1
62 = 81-27+9-1
63 = 81-9-9
64 = 81-9-9+1
65 = 81-9-9+1+1
66 = 81-9-3-3
67 = 81-9-3-1-1
68 = 81-9-3-1
69 = 81-9-3
70 = 81-9-1-1
71 = 81-9-1
72 = 81-9
73 = 81-9+1
74 = 81-9+1+1
75 = 81-3-3
76 = 81-3-1-1
77 = 81-3-1
78 = 81-3
79 = 81-1-1
80 = 81-1
81 = 81
82 = 81+1
83 = 81+1+1
84 = 81+3
85 = 81+3+1
86 = 81+3+1+1
87 = 81+3+3
88 = 81+9-1-1
89 = 81+9-1
90 = 81+9
91 = 81+9+1
92 = 81+9+1+1
93 = 81+9+3
94 = 81+9+3+1
95 = 81+9+3+1+1
96 = 81+9+3+3
97 = 81+9+9-1-1
98 = 81+9+9-1
99 = 81+9+9
100 = 81+27-9+1
101 = 81+27-9+1+1
102 = 81+27-3-3
103 = 81+27-3-1-1
104 = 81+27-3-1
105 = 81+27-3
106 = 81+27-1-1
107 = 81+27-1
108 = 81+27
109 = 81+27+1
110 = 81+27+1+1
111 = 81+27+3
112 = 81+27+3+1
113 = 81+27+3+1+1
114 = 81+27+3+3
115 = 81+27+9-1-1
116 = 81+27+9-1
117 = 81+27+9
118 = 81+27+9+1
119 = 81+27+9+1+1
120 = 81+27+9+3
121 = 81+27+9+3+1
122 = 81+27+9+3+1+1
123 = 81+27+9+3+3
124 = 81+27+9+9-1-1
125 = 81+27+9+9-1
126 = 81+27+9+9
127 = 81+27+27-9+1
128 = 81+27+27-9+1+1
129 = 81+27+27-3-3
130 = 81+27+27-3-1-1
131 = 81+27+27-3-1
132 = 81+27+27-3
133 = 81+27+27-1-1
134 = 81+27+27-1
135 = 81+27+27
136 = 81+81-27+1
137 = 81+81-27+1+1
138 = 81+81-27+3
139 = 81+81-27+3+1
140 = 81+81-27+3+1+1
141 = 81+81-27+3+3
142 = 81+81-27+9-1-1
143 = 81+81-27+9-1
144 = 81+81-9-9
145 = 81+81-9-9+1
146 = 81+81-9-9+1+1
147 = 81+81-9-3-3
148 = 81+81-9-3-1-1
149 = 81+81-9-3-1
150 = 81+81-9-3
151 = 81+81-9-1-1
152 = 81+81-9-1
153 = 81+81-9
154 = 81+81-9+1
155 = 81+81-9+1+1
156 = 81+81-3-3
157 = 81+81-3-1-1
158 = 81+81-3-1
159 = 81+81-3
160 = 81+81-1-1
161 = 81+81-1
162 = 81+81
163 = 81+81+1
164 = 81+81+1+1
165 = 81+81+3
166 = 81+81+3+1
167 = 81+81+3+1+1
168 = 81+81+3+3
169 = 81+81+9-1-1
170 = 81+81+9-1
171 = 81+81+9
172 = 81+81+9+1
173 = 81+81+9+1+1
174 = 81+81+9+3
175 = 81+81+9+3+1
176 = 81+81+9+3+1+1
177 = 81+81+9+3+3
178 = 81+81+9+9-1-1
179 = 81+81+9+9-1
180 = 81+81+9+9
181 = 81+81+27-9+1
182 = 81+81+27-9+1+1
183 = 81+81+27-3-3
184 = 81+81+27-3-1-1
185 = 81+81+27-3-1
186 = 81+81+27-3
187 = 81+81+27-1-1
188 = 81+81+27-1
189 = 81+81+27
190 = 81+81+27+1
191 = 81+81+27+1+1
192 = 81+81+27+3
193 = 81+81+27+3+1
194 = 81+81+27+3+1+1
195 = 81+81+27+3+3
196 = 81+81+27+9-1-1
197 = 81+81+27+9-1
198 = 81+81+27+9
199 = 81+81+27+9+1
200 = 81+81+27+9+1+1
Last edited on
DeathLeap (221)
I really appreciate your help! I will definitely look at it and try to learn from it.
drmaniac (3)
I had to do a similar program last semester but had to account for -121 to -1 too. How would you account from starting with an integer from the negative side?
giblit (3750)
You may want to create your own thread. Anyways, It would pretty much be the same logic but instead of adding up to a positive number you are now adding up to a negative.
Topic archived. No new replies allowed.