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

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

Войти
Регистрация
Восстановить пароль
 
Niсe
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
#1

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

18.02.2012, 00:28. Просмотров 571. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Уменьшение числа(динамика) (C++):

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

Динамика, динамика и снова динамика - C++
Вот как сделать например, что бы динамический массив например int **pArray = new int*; for(int i = 0; i &lt; rows; i++) pArray =...

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

Динамическое программирование, задача "Уменьшение числа" - C++
Имеется натуральное число N (1 &lt;= N &lt;= 106). За один ход с ним можно произвести следующие действия: Вычесть единицу Разделить на два ...

Динамика - C++
При вводе студента появляется одновременно фамилия и число. Как сделать так чтобы поэтапно появлялось ? #include &lt;iostream&gt; ...

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

1
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 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
Привет! Вот еще темы с ответами:

О сигналах динамика ПК - C++
Есть ли другой вариант подачи определенного кол-ва звуковых сигналов динамиком компьютера? count=5; for (count; count !=0; count--) ...

Динамика и статика (массивы) - C++
1)Почему при статическом выделении памяти массив обязательно объявлять в функции main? 2)Почему его нельзя вернуть через return из...

Beep() - музыка из динамика - C++
Сидел на форуме и на толкнулся на функцию Beep(). Есть ли у кого нибудь исходники с музыкой из встроенных динамиков в ПК??=) Вот пример...

Динамика в двумерном массиве - C++
Всем привет. Подскажите, пожалуйста, реально ли реализовать такое. Есть заранее найденное n - не константа. Нужно, чтобы массив...


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

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

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