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

Уменьшение числа(динамика) - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Задача на структуры C++ Составить инвентарную ведомость http://www.cyberforum.ru/cpp-beginners/thread448169.html
Есть задачка: Решить задачу, используя стрктуру содержащую члены-данные и члены-функции На основе данных входного файла составить инвентарную ведомость игрушек, включив следующие данные: название игрушки, её стоимость (в руб.). возрастные границы детей, для которых предназначена игрушка. Вывести в новый файл информацию о тех игрушках, которые преназначены для детей от N до M лет. Шаблон задачи...
C++ Инсталяция библиотеки FLTK В книге чтобы инсталировать, открыть файл fltk.dsw, а в каталоге нет файлов такого формата, все *.vcproj. Помогите установить http://www.cyberforum.ru/cpp-beginners/thread448154.html
C++ Построить график функции
написать программу, которая выводит на экран график функции y=2*sin(x)*exp(sqrt(5)
C++ Работа с INI-файлами в Visual Studio 2010
Можете, пожалуйста, объяснить, как работать с ini-файлами в Visual Studio 2010. Их создание, чтение с существующих файлов, редактирование и какие модули подключать
C++ Динамические структуры данных на языке С/С++ http://www.cyberforum.ru/cpp-beginners/thread448087.html
Сформировать динамическую структуру,содержащую данные по студентам в следующем виде: "Фамилия Имя Группа ГР RS", где ГР – год рождения, RS – средний рейтинг (не менее 5 записей). Осуществить обработку структуры СТЕК : Все студенты, чьи имена начинаются с буквы "А"
C++ Возращение значения в рекурсии Есть бинарное дерево и есть функция, которая должна рекурсивно пройти по вершинам в порядке возрастания ключей и вернуть первое значение, подходящее по условию. Но почему-то функция доходит до самого последнего элемента, хотя не должна. Как это исправить? Код дерева Код: class Tree { public: static int Count; struct tree { int key; подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт C++
4667 / 2493 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.02.2012, 02:23     Уменьшение числа(динамика)
Niсe, У Вас даже в названии задачи написано - динамика, а в коде никакой динамики нет.
Я Вам в ручную покажу как решать с помощью ДП до 6, думаю дальше все будет понятно.
Заводим массив mas[7][2] (можно вопользоваться и чем нибудь другим):
0 1 2 3 4 5 6 <- индексы (числа N)
0 0 0 0 0 0 0 <-элементы первой строки (минимальные суммы чисел N)
0 0 0 0 0 0 0 <- элементы второй строки (операция достижения минимальной суммы, например 1 - это -1, 2 - это /2, 3 - это /3 )
После этого начинаем с индекса 1 (числа 1). Это число могло получится методом -1 (из 2), значит ставим по индексу 2 такие значения:
0 1 2 3 4 5 6 <- индексы (числа N)
0 0 2 0 0 0 0 <-элементы первой строки (минимальные суммы чисел N)
0 0 1 0 0 0 0 <- элементы второй строки (операция достижения минимальной суммы, например 1 - это -1, 2 - это /2, 3 - это /3 )
Также могло получится методом /2 из 2 (но так как минимальная сумма не изменится, то в массиве по индексу 2 не меняем ничего).
Также это значение могло получится методом /3 из 3. Так как по индексу 3 пока нет значений, то записываем их в наш массив:
0 1 2 3 4 5 6 <- индексы (числа N)
0 0 2 3 0 0 0 <-элементы первой строки (минимальные суммы чисел N)
0 0 1 3 0 0 0 <- элементы второй строки (операция достижения минимальной суммы, например 1 - это -1, 2 - это /2, 3 - это /3 )

Далее переходим на индекс 2 (число 2):
Это число могло получится операцией -1 из 3, но тогда стоимость в 3 должна быть 5, а у нас сейчас меньше, поэтому оставляем значение по индексу 3 без изменений.
Также это число могло получится операцией /2 из 4, там ничего нет, поэтому записываем:
0 1 2 3 4 5 6 <- индексы (числа N)
0 0 2 3 6 0 0 <-элементы первой строки (минимальные суммы чисел N)
0 0 1 3 2 0 0 <- элементы второй строки (операция достижения минимальной суммы, например 1 - это -1, 2 - это /2, 3 - это /3 )
Также это число могло получится операцией /3 из 6, там нет значений значит записываем:
0 1 2 3 4 5 6 <- индексы (числа N)
0 0 2 3 6 0 8 <-элементы первой строки (минимальные суммы чисел N)
0 0 1 3 2 0 3 <- элементы второй строки (операция достижения минимальной суммы, например 1 - это -1, 2 - это /2, 3 - это /3 )

Далее число (индекс) 3:
Это значение могло получится операцией -1 из 4, но тогда сумма будет равна 7, а у нас там меньше - оставляем без изменений
Также это значение могло получится операцией /2 из 6, но тогда сумма получится 9, поэтому тоже оставляем без изменений
Также могло получится операцией /3 из 9 - для данного примера превышает максимальное значение, поэтому пропускаем.

Далее число (индекс) 4:
Это значение могло получится операцией -1 из 5, так как там значений нет, то записываем их в массив:
0 1 2 3 4 5 6 <- индексы (числа N)
0 0 2 3 6 11 8 <-элементы первой строки (минимальные суммы чисел N)
0 0 1 3 2 1 3 <- элементы второй строки (операция достижения минимальной суммы, например 1 - это -1, 2 - это /2, 3 - это /3 )
Также это значение могло получится операцией /2 из 8 - для данного примера превышает максимальное значение, поэтому пропускаем.
Также могло получится операцией /3 из 12 - для данного примера превышает максимальное значение, поэтому пропускаем.

Мне кажется дальше Вы уже все сами поняли, поэтому продолжать не буду.
Я привел один из вариантов решения с помощью ДП. Можно и другой вариант:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
        for(int i = 2; i <= n; i++)
        {
            mas[i][0]=mas[i-1][0]+i;// эти две строчки для варианта -1
            mas[i][1]=1;
            if(i%2==0 && mas[i/2][0]+i<mas[i][0])
            {
                mas[i][0]=mas[i/2][0]+i;
                mas[i][1]=2;
            }
            if(i%3==0 && mas[i/3][0]+i<mas[i][0])
            {
                mas[i][0]=mas[i/3][0]+i;
                mas[i][1]=3;
            }  
  
        }
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru