diff options
| -rw-r--r-- | PlaygroundCpp/Sources/Playground.cpp | 89 |
1 files changed, 69 insertions, 20 deletions
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp index 070cf04..45bb5fc 100644 --- a/PlaygroundCpp/Sources/Playground.cpp +++ b/PlaygroundCpp/Sources/Playground.cpp @@ -1,32 +1,81 @@ #include <iostream> #include <climits> +#include <vector> +#include <algorithm> //#include <gtest/gtest.h> -int getChange(int money) { - // denominations: 1, 3, 4 - int denominations[3] = { 1, 3, 4 }; - int minNumCoins[money + 1] = { }; - for (int m = 1; m < money + 1; m++) { - minNumCoins[m] = INT_MAX; - for (int i = 0; i < 3; i++) { - if (m >= denominations[i]) { - int numCoins = minNumCoins[m - denominations[i]] + 1; - if (numCoins < minNumCoins[m]) { - minNumCoins[m] = numCoins; - } - } +using std::vector; + +vector<int> optimal_sequence(int n) { + vector<int> sequence; + int stepsCount[n]; + // the path int array indicates the next step to reduce it: + // 1: minus 1 + // 2: divide by 2 + // 3: divide by 3 + int path[n]; + int div2Steps, div3Steps, minus1Steps; + for (int i = 1; i < n; i++) { + int j = i + 1; + div2Steps = INT_MAX; + div3Steps = INT_MAX; + if (j % 3 == 0) { + div3Steps = stepsCount[j / 3 - 1]; + } + if (j % 2 == 0) { + div2Steps = stepsCount[j / 2 - 1]; + } + minus1Steps = stepsCount[i - 1]; + + int minStepsCount = std::min(minus1Steps, + std::min(div2Steps, div3Steps)); + stepsCount[i] = minStepsCount + 1; + if (minStepsCount == minus1Steps) { + path[i] = 1; + continue; + } + if (minStepsCount == div2Steps) { + path[i] = 2; + continue; + } + if (minStepsCount == div3Steps) { + path[i] = 3; } } - return minNumCoins[money]; + sequence.push_back(n); + while (n > 1) { + int i = path[n - 1]; + if (i == 3) { + n = n / 3; + sequence.push_back(n); + continue; + } + if (i == 2) { + n = n / 2; + sequence.push_back(n); + continue; + } + n = n - 1; + sequence.push_back(n); + } + reverse(sequence.begin(), sequence.end()); + return sequence; } -//TEST(SortPoint, Sort1) { -// ASSERT_EQ(2, getChange(2)); -// ASSERT_EQ(9, getChange(34)); +//TEST(PrimitiveCalc, Calc1) { +// ASSERT_EQ(2, optimal_sequence(6).size() - 1); +//} +// +//TEST(PrimitiveCalc, Calc2) { +// ASSERT_EQ(14, optimal_sequence(96234).size() - 1); //} int main() { - int m; - std::cin >> m; - std::cout << getChange(m) << '\n'; + int n; + std::cin >> n; + vector<int> sequence = optimal_sequence(n); + std::cout << sequence.size() - 1 << std::endl; + for (size_t i = 0; i < sequence.size(); ++i) { + std::cout << sequence[i] << " "; + } } |