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

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

Войти
Регистрация
Восстановить пароль
 
MsHassium
2 / 2 / 0
Регистрация: 04.03.2012
Сообщений: 21
#1

Динамическое программирование, задача "Уменьшение числа" - C++

03.11.2012, 20:58. Просмотров 792. Ответов 8
Метки нет (Все метки)

Имеется натуральное число N (1 <= N <= 106). За один ход с ним можно произвести следующие действия:
Вычесть единицу
Разделить на два
Разделить на три
При этом стоимость каждой операции - текущее значение N. Стоимость преобразования - суммарная стоимость всех операций в преобразовании. Вам необходимо с помощью последовательностей указанных операций преобразовать число N в единицу таким образом, чтобы стоимость преобразования была наименьшей.

Входные данные
Число N.

Выходные данные
Выведите на первой строке искомую наименьшую стоимость. Во второй строке должна содержаться последовательность операций. Если было произведено деление на 2 или на 3, выведите /2 (или /3). Если же было вычитание, выведите -1. Все операции выводите разделяя пробелом. Если оптимальных ответов несколько, выведите любой.

Пример

Ввод
5

Вывод
11
-1 /2 -1
Я написал код, который выдает все в правильном виде, но в нашем университетском контестере проходит 33 теста из 50, остальные тесты пишет НЕПРАВИЛЬНЫЙ ОТВЕТ, подскажите какие случаи я не рассмотрел.
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <string>
using namespace std;
int min(int a,int b)
{
    if (a<b)
        return a;
    else
        return b;
}
int main()
{
    freopen ("input.txt","r",stdin);
    freopen ("output.txt","w",stdout);
    int n,temp;
    cin>>n;
    int *mas=new int [n];
    int **z=new int *[n+1];
    mas[0]=0;
    mas[1]=0;
    if(n==0||n==1)
    {
        cout<<0;
        return 0;
    }
    for(int i=2;i<=n;i++)
    {
        int t=1;
        if((i>=2&&i%2==0)&&(i>=3&&i%3==0))
        {
            mas[i]=min(i+mas[i/2],i+mas[i/3]);
            continue;
        }
        if(i>=2&&i%2==0)
        {
            mas[i]=i+mas[i/2];
            continue;
        }
        if(i>=3&&i%3==0)
        {
            mas[i]=i+mas[i/3];
            continue;
        }
        if(i>1)
        {
            mas[i]=i+mas[i-1];
        }
    }
    cout<<mas[n];
    cout<<endl;
    temp=n;
    while(temp>1)
    {
        if((temp%3==0)&&(temp%2==0))
        {
            if(mas[temp/2]<=mas[temp/3])
            {
                cout<<"/2"<<" ";
                temp/=2;
            }
            else
            {
                cout<<"/3"<<" ";
                temp/=3;
            }
            continue;
        }
        if(temp%3==0)
        {
            if(mas[temp/3]<=mas[temp-1])
            {
                cout<<"/3"<<" ";
                temp/=3;
            }
            else
            {
                cout<<"-1"<<" ";
                temp-=1;
            }
            continue;
        }
 
        if(temp%2==0)
        {
            if(mas[temp/2]<=mas[temp-1])
            {
                cout<<"/2"<<" ";
                temp/=2;
 
            }
            else
            {
                cout<<"-1"<<" ";
                temp-=1;
            }
            continue;
        }
        if(temp>1)
        {
            cout<<"-1"<<" ";
            temp--;
            continue;
        }
    }
        
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2012, 20:58     Динамическое программирование, задача "Уменьшение числа"
Посмотрите здесь:

C++ Уменьшение значений элементов матрицы(перегрузка операции "--")
C++ Динамическое программирование игры "Ним"
Задача на динамическое программирование. C++
Задача "протри" числа C++
Два числа, действительное "a" и натуральное "n" вводятся с клавиатуры C++
C++ Найти ошибку в решении "Числа - палиндрома" (задача с acmp)
Задача о НОП (динамическое программирование) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
03.11.2012, 21:29     Динамическое программирование, задача "Уменьшение числа" #2
можно как-то воспользоваться вашим контестером?
MsHassium
2 / 2 / 0
Регистрация: 04.03.2012
Сообщений: 21
03.11.2012, 21:31  [ТС]     Динамическое программирование, задача "Уменьшение числа" #3
http://acm.sgu.ru/univer, прошу.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
03.11.2012, 21:32     Динамическое программирование, задача "Уменьшение числа" #4
подразумевалось, что мне потребуется ссылка на конкретную задачу...
MsHassium
2 / 2 / 0
Регистрация: 04.03.2012
Сообщений: 21
03.11.2012, 21:47  [ТС]     Динамическое программирование, задача "Уменьшение числа" #5
Прошу прощения, не понял вопроса. http://acm.sgu.ru/univer/problem.php...=0&problem=282, если так не прокатит, то в архиве задач задача №282
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
03.11.2012, 21:55     Динамическое программирование, задача "Уменьшение числа" #6
я под номером 282 обнаружил следующее http://acm.sgu.ru/problem.php?contest=0&problem=282 (Изоморфизм)
MsHassium
2 / 2 / 0
Регистрация: 04.03.2012
Сообщений: 21
03.11.2012, 22:05  [ТС]     Динамическое программирование, задача "Уменьшение числа" #7
Цитата Сообщение от salam Посмотреть сообщение
я под номером 282 обнаружил следующее http://acm.sgu.ru/problem.php?contest=0&problem=282 (Изоморфизм)
вы смотрите на сайте ацм, а нужно acm.ru/univer
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.11.2012, 12:48     Динамическое программирование, задача "Уменьшение числа" #8
вот эту часть:
Цитата Сообщение от MsHassium Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
for(int i=2;i<=n;i++)
 {
 int t=1;
 if((i>=2&&i%2==0)&&(i>=3&&i%3==0))
 {
 mas[i]=min(i+mas[i/2],i+mas[i/3]);
 continue;
 }
 if(i>=2&&i%2==0)
 {
 mas[i]=i+mas[i/2];
 continue;
 }
 if(i>=3&&i%3==0)
 {
 mas[i]=i+mas[i/3];
 continue;
 }
 if(i>1)
 {
 mas[i]=i+mas[i-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
   for(int i=2;i<=n;i++)
    {
        int t=1;
        if((i>=2&&i%2==0)&&(i>=3&&i%3==0))
        {
            mas[i]=min(i+mas[i/2],i+mas[i/3]);
            continue;
        }
        if(i>=3&&i%3==0)
        {
            if(i+mas[i/3]<i+mas[i-1])
                mas[i]=i+mas[i/3];
            else
                mas[i]=i+mas[i-1];
            continue;
        }
        if(i>=2&&i%2==0)
        {
            if(i+mas[i/2]<i+mas[i-1])
                mas[i]=i+mas[i/2];
            else
                mas[i]=i+mas[i-1];
            continue;
        }
        if(i>1)
        {
            mas[i]=i+mas[i-1];
        }
    }
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.11.2012, 13:52     Динамическое программирование, задача "Уменьшение числа"
Еще ссылки по теме:

C++ Задача на динамическое программирование
C++ Задача из Златопольского: "Найти числа с известным количеством делителей". Не могу найти ошибку
Задача "Движение по клеткам таблицы" (Динамическое программирование) C++
Задача "Числа Фибоначчи" C++
C++ Задача "Номер числа Фибоначчи"

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

Или воспользуйтесь поиском по форуму:
MsHassium
2 / 2 / 0
Регистрация: 04.03.2012
Сообщений: 21
04.11.2012, 13:52  [ТС]     Динамическое программирование, задача "Уменьшение числа" #9
Огромное спасибо, все получилось.
Yandex
Объявления
04.11.2012, 13:52     Динамическое программирование, задача "Уменьшение числа"
Ответ Создать тему
Опции темы

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