Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
Niсe
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
#1

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

18.02.2012, 00:28. Просмотров 657. Ответов 1
Метки нет (Все метки)

Здравствуйте, помогите найти ошибку в коде для задачи - имеется натуральное число(1<=n<=10^6), к нему применимы операции -1 /2 и /3, при этом стоимость каждой операции - текущее значение N. Стоимость преобразования - суммарная стоимость всех операций в преобразовании. Вам необходимо с помощью последовательностей указанных операций преобразовать число N в единицу таким образом, чтобы стоимость преобразования была наименьшей.
Входные данные
Число N.
Выходные данные
Выведите на первой строке искомую наименьшую стоимость. Во второй строке должна содержаться последовательность операций. Если было произведено деление на 2 или на 3, выведите /2 (или /3). Если же было вычитание, выведите -1. Все операции выводите разделяя пробелом. Если оптимальных ответов несколько, выведите любой.
Пример
Ввод
5
Вывод
11
-1 /2 -1
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <string>
using namespace std;
int main()
{
    int n; cin>>n;
    int *mas = new int[n+1];
    string s;
    mas[1] = 0;
    for(int i = 2; i <= n; i++)
    {
        if(i%2==0)
            mas[i] = mas[i/2]+i;            
        else 
        {
            if (i%3==0) 
                mas[i] = mas[i/3]+i;
            else mas[i] = mas[i-1]+i;
        }
    }
    cout<<mas[n]<<endl;
    while (n>1)
    {
        if(s.size()) s+= " ";
        if (n%3==0) {n/=3; s+="/3";}
        else{
                if (n%2==0) {n/=2; s+="/2";}
                else {n-=1; s+="-1";}
            }
 
    }
    cout<<s;
    delete[] mas;
return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.02.2012, 00:28
Ответы с готовыми решениями:

Сначала увеличение числа, потом уменьшение
Добрый день! Подскажите пожалуйста, как можно сделать так, чтобы число сначала...

Уменьшение числа рекурсивных вызовов. Мемоизация
Как уменьшить число вызовов? Просто не могу понять что нужно запомнить и...

Динамика, динамика и снова динамика
Вот как сделать например, что бы динамический массив например int **pArray =...

Увеличение (уменьшение) числа в строковом формате на единицу
Здравствуйте! Не подскажите, пожалуйста, как правильно увеличивать или...

Уменьшение числа на единицу через каждые два шага
Здравствуйте. Нужна формула, при которой число уменьшается на единицу через...

1
valeriikozlov
Эксперт С++
4684 / 2510 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
18.02.2012, 02:23 #2
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;
            }  
  
        }
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.02.2012, 02:23

Динамическое программирование, задача "Уменьшение числа"
Имеется натуральное число N (1 &lt;= N &lt;= 106). За один ход с ним можно произвести...

Динамика
При вводе студента появляется одновременно фамилия и число. Как сделать так...

Динамика
Пожалуйста ребят, кому не трудно, сделайте. Очень вас прошу. Заранее огромное...


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

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

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