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

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

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

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

18.02.2012, 00:28. Просмотров 495. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.02.2012, 00:28     Уменьшение числа(динамика)
Посмотрите здесь:

О сигналах динамика ПК C++
C++ Beep() - музыка из динамика
C++ Динамика
C++ Динамика,С++,предметная область Аптека
Динамика, динамика и снова динамика C++
Динамика C++
C++ Динамическое программирование, задача "Уменьшение числа"
Динамика и статика (массивы) C++
C++ Уменьшение числа на единицу через каждые два шага
C++ Сначала увеличение числа, потом уменьшение
C++ Динамика в двумерном массиве
C++ Увеличение и уменьшение квадрата С++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 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;
            }  
  
        }
Yandex
Объявления
18.02.2012, 02:23     Уменьшение числа(динамика)
Ответ Создать тему
Опции темы

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