summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp89
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] << " ";
+ }
}