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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
eocron
Кактус
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
#1

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

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

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

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

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

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

Нахождение минимальной суммы цифр из 2х чисел - C++
Какого дьявола оно выдаёт то,что записано первым вместо того чтобы выдавать минимальное? #include <iostream> using namespace std; ...

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

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

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

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

3
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 734
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
eocron
Кактус
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
23.04.2013, 21:30  [ТС] #3
Только N может быть размером в 10 000 000, слишком много памяти будет кушать.
0
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 734
24.04.2013, 15:09 #4
это меньше 80 Мб... вы уверены, что это ML?

Добавлено через 2 минуты
я сколько себя помню, не видел задач такого плана с ограничениями меньше 64 Мб. пусть так, пусть даже 32. но вам очевидно нужна только треть массива, то есть без проблем память сводится к 27 Мб.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.04.2013, 15:09
Привет! Вот еще темы с ответами:

Рекурсия: вычисление суммы и количества цифр числа, максимальной и минимальной его цифры - C++
Помогите, пожалуйста, разобраться и написать программу на С++. Условие такое: Для числа, введеного с клавиатуры, определить рекурсивные...

Написать программу для определения максимальной и минимальной суммы двух соседних элементов массива - C++
Дан массив целых чисел Написать программу для определения максимальной и минимальной суммы двух соседних элементов массива

Функция нахождения суммы - C++
Есть программный код на с++, с функцией нахождения суммы s1 и s2. Почему-то сумму s1,s2 не считает, помогите. #include&lt;stdio.h&gt; ...

Программа нахождения суммы ряда на си - C++
Помогите пожалуйста написать программу на си. нахождения суммы ряда. Цикл должен считать сумму ряда как минимум 100.000.000 раз. ...


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

Или воспользуйтесь поиском по форуму:
4
Yandex
Объявления
24.04.2013, 15:09
Ответ Создать тему
Опции темы

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