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

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

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

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

03.11.2012, 20:58. Просмотров 826. Ответов 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++
Хотел узнать, может у кого-нибудь в архивах есть подобная задача, которую можно будет использовать как шаблон к моей. Есть таблица NxM,...

Динамическое программирование игры "Ним" - C++
Игра Ним с одной кучей камней и с инвертированными правилами (взявший последний камень проигрывает), нисходящее и восходящее ДП.

Найти ошибку в решении "Числа - палиндрома" (задача с acmp) - C++
У меня WA на 4-ом тесте. #include &lt;stdio.h&gt; #include &lt;stdio.h&gt; #include &lt;math.h&gt; #include &lt;cstdio&gt; #include &lt;algorithm&gt; ...

Уменьшение значений элементов матрицы(перегрузка операции "--") - C++
Задача Перегрузите операцию &quot;--&quot; позволяющую уменьшать переменную типа матрица на 1. В результате каждылемент матрицы должен...

Задача "Номер числа Фибоначчи" - C++
Дано натуральное число A &gt; 1. Определите, каким по счету числом Фибоначчи оно является, то есть выведите такое число n, что φn=A. Если А не...

Задача "протри" числа - C++
Даны три вещественных числа. Возвести в квадрат те из них, значения которых неотрицательны. if x1&gt;=0 {x1=x1*x1} if x2&gt;=0 {x2=x2*x2} ...

Задача "Числа Фибоначчи" - C++
Последовательность Фибоначчи определяется так: φ0=0, φ1=1, ..., φn=φn-1+φn-2. По данному числу n определите n-е число Фибоначчи...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
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++
4669 / 2495 / 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     Динамическое программирование, задача "Уменьшение числа"
Еще ссылки по теме:

Два числа, действительное "a" и натуральное "n" вводятся с клавиатуры - C++
Два числа, действительное &quot;a&quot; и натуральное &quot;n&quot; (n&gt;=10) вводятся с клавиатуры, необходимо найти значение выражения : ...

Задача на динамическое программирование. - C++
Что не правильно? #include &lt;fstream&gt; #include &lt;iostream&gt; using namespace std; int main() {

Задача на динамическое программирование - C++
Требуется решить задачу на динамическое программирование. Условия:На планете Олимпия очень популярна такая головоломка. На столе...

Задача из Златопольского: "Найти числа с известным количеством делителей". Не могу найти ошибку - C++
Здравствуйте. Задача следующая: Найти все целые числа из промежутка от a до b, у которых количество делителей равно k. К примеру я взял...

Задача о НОП (динамическое программирование) - C++
Здравствуйте!!! Мне нужно решить задачу о нахождении наибольшей общей подстроки. Поискал в интернете, нашёл такой код на Pascal: var...


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

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

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