Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Кактус
67 / 67 / 19
Регистрация: 23.05.2012
Сообщений: 342
1

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

23.04.2013, 19:45. Просмотров 455. Ответов 3
Метки нет (Все метки)

Имеется натуральное число n. За один ход с ним можно произвести следующие действия:

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

Помогите с алгоритмом. Динамическое программирование, начертил даже формулу рекурсивную, и дерево вариантов нарисовал, а как алгоритм сварганить отбрасывая ненужные варианты - не понимаю.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.04.2013, 19:45
Ответы с готовыми решениями:

Алгоритм для нахождения минимальной невозрастающей последовательности
Здравствуйте, помогите срочно реализовать алгоритм. Необходимо написать алгоритм для нахождения...

Поиск минимальной суммы в дереве
Здравствуйте! Есть дерево и необходимо найти минимальную сумму в дереве, т.е. от корня до листа....

Нахождение минимальной суммы цифр из 2х чисел
Какого дьявола оно выдаёт то,что записано первым вместо того чтобы выдавать минимальное? ...

Поиск минимальной суммы троек входных значений
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой...

3
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 799
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;
}
0
Кактус
67 / 67 / 19
Регистрация: 23.05.2012
Сообщений: 342
23.04.2013, 21:30  [ТС] 3
Только N может быть размером в 10 000 000, слишком много памяти будет кушать.
0
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 799
24.04.2013, 15:09 4
это меньше 80 Мб... вы уверены, что это ML?

Добавлено через 2 минуты
я сколько себя помню, не видел задач такого плана с ограничениями меньше 64 Мб. пусть так, пусть даже 32. но вам очевидно нужна только треть массива, то есть без проблем память сводится к 27 Мб.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.04.2013, 15:09

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Класс "Матрица" для нахождения суммы, разности, умножения матриц и суммы элементов матрицы.
Всем привет. Вы могли бы протестировать работу на предмет ошибок, и если нетрудно указать места,...

Написать программу для нахождения A28, используя шесть операций умножения
Написать программу для нахождения A28, используя шесть операций умножения

Определение максимальной и минимальной суммы двух соседних элементов массива
дан массив целых чисел написать программу для определения максимальной и минимальной суммы двух...

Почему программа выводит вместо минимальной суммы последовательности последний элемент?
Программа выводит вместо минимальной суммы последовательности последний элемент. Подскажите...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.