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

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

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

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

03.11.2012, 20:58. Просмотров 852. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2012, 20:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Динамическое программирование, задача "Уменьшение числа" (C++):

Задача "Движение по клеткам таблицы" (Динамическое программирование) - C++
Хотел узнать, может у кого-нибудь в архивах есть подобная задача, которую можно будет использовать как шаблон к моей. Есть таблица NxM,...

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

Даны три слова - "мама", "мыла", "раму". Задача - напечатать всевозможные варианты построения слов - C++
Я записал код, однако эту часть надо автоматизировать, поможете? КОД: } #include &lt;iostream&gt; using namespace std; int main()...

Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64" - C++
доброго времени суток. Необработанное исключение в &quot;0x76f015de&quot; в &quot;контрольная 1 задача 2.exe&quot;: 0xC0000005: Нарушение прав доступа при...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

Наследуемым классом для комплексного числа объявить класс "радиус-вектор", имеющий данные "длина" и "угол" - C++
кто то напишите пожалуйста, вот программа: наследуемым классом для комплексного числа объявить класс &quot;радиус-вектор&quot;, имеющий данные...

8
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
03.11.2012, 21:29 #2
можно как-то воспользоваться вашим контестером?
0
MsHassium
2 / 2 / 0
Регистрация: 04.03.2012
Сообщений: 21
03.11.2012, 21:31  [ТС] #3
http://acm.sgu.ru/univer, прошу.
0
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
03.11.2012, 21:32 #4
подразумевалось, что мне потребуется ссылка на конкретную задачу...
0
MsHassium
2 / 2 / 0
Регистрация: 04.03.2012
Сообщений: 21
03.11.2012, 21:47  [ТС] #5
Прошу прощения, не понял вопроса. http://acm.sgu.ru/univer/problem.php?contest=0&problem=282, если так не прокатит, то в архиве задач задача №282
0
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
03.11.2012, 21:55 #6
я под номером 282 обнаружил следующее http://acm.sgu.ru/problem.php?contest=0&problem=282 (Изоморфизм)
0
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
0
valeriikozlov
Эксперт С++
4670 / 2496 / 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];
        }
    }
1
MsHassium
2 / 2 / 0
Регистрация: 04.03.2012
Сообщений: 21
04.11.2012, 13:52  [ТС] #9
Огромное спасибо, все получилось.
0
04.11.2012, 13:52
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.11.2012, 13:52
Привет! Вот еще темы с ответами:

Через ООП: Дать для числа наименование: "рубль", "рубля", "рублей"; - C++
Помогите пожалуйста с задачей. Могу сделать ее просто, но надо через ООП и у меня не получается. Дано натуральное число N (N&lt;20),...

Найти ошибку в решении "Числа - палиндрома" (задача с 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++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

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


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

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

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