I am trying to write an algorithm that decompose an integer that the user inputs into powers of three.
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
Rules: each power of 3, e.g: 1, 3, 9..etc should appear only once or never. It can't appear twice.
There are some intervals that must be considered: [-121,-41], [-40,-14], [-13,-5], [-4,-2], [-1,-1], [1,1], [2,4], [5,13],
[14,40], and [41,121]
My code shows the powers of three more than once. It's not that clean too. Can you guys help please?
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
|
#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);
int closest = 1;
for (std::size_t i = 1; i < table.size(); ++i)
{
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;
system("pause");
return 0;
}
|