Не получается решить задачу на программирование: калькулятор
1,00
р.
Пытаюсь решить задачу условие, которой приведено ниже. Проблема в том что на больших числах моя программа выдает какой-то совершенно адский результат. К примеру для числа 96234 программа выдает такую простыню чисел http://pastebin.com/8H5SvPKb (сравните с тем результатом, который приведен в условии). В принципе я понимаю почему так происходит, но другой идеи для решения данной задачи у меня нет. Подскажите как тут грамотно решить эту задачу.
Условие задачи:
У вас есть примитивный калькулятор, который умеет выполнять всего три операции с текущим числом x: заменить x на 2x, 3x или x+1. По данному целому числу 1≤n≤10^5 определите минимальное число операций k, необходимое, чтобы получить n из 1. Выведите k и последовательность промежуточных чисел.
Sample Input 1: 1 Sample Output 1: 0 1
Sample Input 2: 5 Sample Output 2: 3 1 2 4 5
Sample Input 3: 96234 Sample Output 3: 14 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
Мое решение:
#include #include
using namespace std
int main(int argc, const char * argv[]) { int n cin >> n
int i = 1 vector m m.push_back(i) while (i != n) { if (i * 3 <= n) { i *= 3 } else if (i * 2 <= n) { i *= 2 } else { i++ } m.push_back(i) }<br> cout << m.size() - 1 << endl for (int i = 0 i < m.size() i++) cout << m[i] << " " <br> return 0 }
Ответ
Напишу свое решение, которое, по-моему, намного проще понять, чем уже опубликованные (я, например, не понимаю, почему они правильные).
Алгоритм такой: заводим список, в котором в i-ой позиции будем хранить минимальное число шагов, известное на данный момент, за которое можно попасть в N. В начале нам будет известно только то, что в N-ой позиции стоит 0. Затем начинаем бежать по списку из конца в начало. На каждом шаге проверяем, из каких позиций мы можем попасть в текущую, и для этих позиций обновляем расстояние, если оно лучше, чем уже посчитанное ранее. К моменту когда мы прийдем в i-ый элемент, там будет записано минимальное расстояние, т.к. мы перебрали все варианты. Код такой:
#include #include #include
int main() { int N std::cin >> N std::vector steps(N + 1, INT_MAX) steps[N] = 0 std::vector next_num(N + 1, -1)
for (int i = N i > 1 --i) { int s = steps[i] + 1 // 3 * x if (!(i % 3) && steps[i / 3] > s) { steps[i / 3] = s next_num[i / 3] = i } // 2 * x if (!(i % 2) && steps[i / 2] > s) { steps[i / 2] = s next_num[i / 2] = i } // x + 1 if (steps[i - 1] > s) { steps[i - 1] = s next_num[i - 1] = i } }
std::cout << steps[1] << std::endl for (int i = 1 i != -1 i = next_num[i]) std::cout << i << ' ' std::cout << std::endl } <br>Сложность алгоритма -- линейная.
Результаты на тестах:
http://ideone.com/cuHyDP
stdin 1  stdout 0 1
http://ideone.com/Ttku2H
stdin 5  stdout 3 1 3 4 5
http://ideone.com/G5yg1I
 stdin 96234  stdout 14 1 3 9 10 11 33 99 297 891 2673 8019 16038 16039 48117 96234
Условие задачи:
У вас есть примитивный калькулятор, который умеет выполнять всего три операции с текущим числом x: заменить x на 2x, 3x или x+1. По данному целому числу 1≤n≤10^5 определите минимальное число операций k, необходимое, чтобы получить n из 1. Выведите k и последовательность промежуточных чисел.
Sample Input 1: 1 Sample Output 1: 0 1
Sample Input 2: 5 Sample Output 2: 3 1 2 4 5
Sample Input 3: 96234 Sample Output 3: 14 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
Мое решение:
#include #include
using namespace std
int main(int argc, const char * argv[]) { int n cin >> n
int i = 1 vector m m.push_back(i) while (i != n) { if (i * 3 <= n) { i *= 3 } else if (i * 2 <= n) { i *= 2 } else { i++ } m.push_back(i) }<br> cout << m.size() - 1 << endl for (int i = 0 i < m.size() i++) cout << m[i] << " " <br> return 0 }
Ответ
Напишу свое решение, которое, по-моему, намного проще понять, чем уже опубликованные (я, например, не понимаю, почему они правильные).
Алгоритм такой: заводим список, в котором в i-ой позиции будем хранить минимальное число шагов, известное на данный момент, за которое можно попасть в N. В начале нам будет известно только то, что в N-ой позиции стоит 0. Затем начинаем бежать по списку из конца в начало. На каждом шаге проверяем, из каких позиций мы можем попасть в текущую, и для этих позиций обновляем расстояние, если оно лучше, чем уже посчитанное ранее. К моменту когда мы прийдем в i-ый элемент, там будет записано минимальное расстояние, т.к. мы перебрали все варианты. Код такой:
#include #include #include
int main() { int N std::cin >> N std::vector steps(N + 1, INT_MAX) steps[N] = 0 std::vector next_num(N + 1, -1)
for (int i = N i > 1 --i) { int s = steps[i] + 1 // 3 * x if (!(i % 3) && steps[i / 3] > s) { steps[i / 3] = s next_num[i / 3] = i } // 2 * x if (!(i % 2) && steps[i / 2] > s) { steps[i / 2] = s next_num[i / 2] = i } // x + 1 if (steps[i - 1] > s) { steps[i - 1] = s next_num[i - 1] = i } }
std::cout << steps[1] << std::endl for (int i = 1 i != -1 i = next_num[i]) std::cout << i << ' ' std::cout << std::endl } <br>Сложность алгоритма -- линейная.
Результаты на тестах:
http://ideone.com/cuHyDP
stdin 1  stdout 0 1
http://ideone.com/Ttku2H
stdin 5  stdout 3 1 3 4 5
http://ideone.com/G5yg1I
 stdin 96234  stdout 14 1 3 9 10 11 33 99 297 891 2673 8019 16038 16039 48117 96234
