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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Открыть заданный текстовый файл, найти в нем и вывести на экран самую длинную строку http://www.cyberforum.ru/cpp-beginners/thread687844.html
Открыть заданный текстовый файл, найти в нем и вывести на экран самую длинную строку. Имя файла должно передаваться в программу в виде аргументов командной строки. вот код //--------------------------------------------------------------------------- //--------------------------------------------------------------------------- #include <stdio.h> #include <stdlib.h> #include <string.h>...
C++ Программирование для телефонов или смартфонов Привет, меня интересует вопрос на какие из этих платформ можно писать приложение на visual studio 1.Android 2.IOS 3.Symbian И все. И еще по подробней как писать под ios если не на vs http://www.cyberforum.ru/cpp-beginners/thread687817.html
Обработать строки, пользуясь указателями C++
Помогите решить, заранее спасибо: Вводится строка в символьный массив размером 80. Задание: Рядом с заданным пользователем символом записать такой же. Запрещается использовать дополнительные массивы и блоки. Например: Введенная строка - корова Введенный символ - О После обработки должно получится коороова
Компилятор для новичка C++
будь ласка, дайте (порекомендуйте) компилятор, которым пользуетесь, для новичка, у меня установлен: rad studio, vs studio 2012, vs studio 2010, vs studio, 2008 Turbo C.
C++ Почему не определяются cout, cin, endl, system? http://www.cyberforum.ru/cpp-beginners/thread687764.html
int i,n,k1,k2; float min,s=0; cout<<" n="; cin>>n; float* a=new float ; cout<<" Enter elements: "; for(i=0;i<n;i++) cin>>a; min=a; for(i=1;i<n;i++) if(min>a) min=a;
C++ Вычислить сумму элементов массива, расположенных между первым и последним положительными элементами #include <stdio.h> #include <conio.h> #include <stdlib.h> int main() { int i,j, n; int numMaxFirst, count=0, summ=0; int *arr; printf("Enter numbers: "); // вводим количество элементов подробнее

Показать сообщение отдельно
MsHassium
2 / 2 / 0
Регистрация: 04.03.2012
Сообщений: 21

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

03.11.2012, 20:58. Просмотров 797. Ответов 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 23:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru