Форум программистов, компьютерный форум CyberForum.ru

Нахождения минимальной суммы операций - C++

Восстановить пароль Регистрация
 
eocron
Кактус
 Аватар для eocron
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
23.04.2013, 19:45     Нахождения минимальной суммы операций #1
Имеется натуральное число n. За один ход с ним можно произвести следующие действия:

Вычесть единицу
Разделить на два
Разделить на три
При этом стоимость каждой операции - текущее значение n. Стоимость преобразования - суммарная стоимость всех операций в преобразовании. Вам необходимо с помощью последовательностей указанных операций преобразовать число n в единицу таким образом, чтобы стоимость преобразования была наименьшей. Делить можно только нацело.

Помогите с алгоритмом. Динамическое программирование, начертил даже формулу рекурсивную, и дерево вариантов нарисовал, а как алгоритм сварганить отбрасывая ненужные варианты - не понимаю.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.04.2013, 19:45     Нахождения минимальной суммы операций
Посмотрите здесь:

C++ Написать программу для нахождения A28, используя шесть операций умножения
C++ Класс "Матрица" для нахождения суммы, разности, умножения матриц и суммы элементов матрицы.
C++ Написать программу нахождения суммы
C++ Функция нахождения суммы
C++ Определение максимальной и минимальной суммы двух соседних элементов массива
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
23.04.2013, 19:56     Нахождения минимальной суммы операций #2
вы должны считать ответ для каждого числа на отрезке [1; N]. критерий перехода очевиден.

Добавлено через 29 секунд
ответом будет значение в N...)

Добавлено через 4 минуты
давайте так:
C++
1
2
3
4
5
6
7
8
for(int i=1; i <= n; i++) {
     ans[i] = ans[i-1];
     if(i % 2 == 0)
        ans[i] = min(ans[i], ans[i/2]);
     if(i % 3 == 0)
        ans[i] = min(ans[i], ans[i/3]);
     ans[i] += i;
}
eocron
Кактус
 Аватар для eocron
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
23.04.2013, 21:30  [ТС]     Нахождения минимальной суммы операций #3
Только N может быть размером в 10 000 000, слишком много памяти будет кушать.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
24.04.2013, 15:09     Нахождения минимальной суммы операций #4
это меньше 80 Мб... вы уверены, что это ML?

Добавлено через 2 минуты
я сколько себя помню, не видел задач такого плана с ограничениями меньше 64 Мб. пусть так, пусть даже 32. но вам очевидно нужна только треть массива, то есть без проблем память сводится к 27 Мб.
Yandex
Объявления
24.04.2013, 15:09     Нахождения минимальной суммы операций
Ответ Создать тему
Опции темы

Текущее время: 06:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru