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

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

Восстановить пароль Регистрация
 
MsHassium
2 / 2 / 0
Регистрация: 04.03.2012
Сообщений: 21
03.11.2012, 20:58     Динамическое программирование, задача "Уменьшение числа" #1
Имеется натуральное число 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     Динамическое программирование, задача "Уменьшение числа"
Посмотрите здесь:

Дано натуральное число. Найти сумму последних "n" цифр "n" числа, не применяя переменых значений C++
C++ Уменьшение значений элементов матрицы(перегрузка операции "--")
C++ 2 Программы. На "целые числа и системы счисления" и на "метод деления отрезка пополам"
Задача "протри" числа C++
Два числа, действительное "a" и натуральное "n" вводятся с клавиатуры 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
4660 / 2486 / 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++ Найти ошибку в решении "Числа - палиндрома" (задача с acmp)
C++ Задача из Златопольского: "Найти числа с известным количеством делителей". Не могу найти ошибку
Задача "Движение по клеткам таблицы" (Динамическое программирование) C++

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

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

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