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

Динамическое программирование - C++

Восстановить пароль Регистрация
 
Семан
1 / 1 / 0
Регистрация: 13.03.2012
Сообщений: 246
23.10.2013, 18:51     Динамическое программирование #1
народ помогите пожалуйста.
есть задача

Написать программу, позволяющую вычислить количество чисел, не содержащих нули, сумма цифр которых ровна заданному N
Пример
вход-3
выход-4
--------------------
вот принцип
сама 3
12(1+2=3)
21(2+1=3)
111(1+1+1=3)
--------------
как это решить динамическим способом? методом перебор я сделал, динамически не могу, помогите пожалуйста

Добавлено через 1 минуту
Вот код рабочий метода перебор
C++ (Qt)
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include "stdafx.h"
#include <string>
#include <queue>
#include <stack>
#include <tchar.h>
#include <windows.h>
#include <stdio.h>
#include <iostream> 
#include <conio.h>
using namespace std;
 
 
 
string IntToStr(int x)
{
    char buf[20];
    sprintf(buf,"%d",x);
    return buf;
}
 
int test (int num)
{
    string str;
    str = IntToStr(num);
    for(int i=0; i<str.size(); i++)
    {
        if (str[i]=='0')
        {return 0;}
    }
return 1;
}
 
 
int main()
{
    while(1)
    {
    int num2, num,temp;
    int n,v;
    int a=0;
    //int b=11;
    int b=1;
    int p=0;
    queue <int> q;
          
       int g = 1;
//int n = 0;
int i=1;
int h;
    stack<int> s;
      
 
temp=0;
 
    cin>>n;
    s.push(1);
 
    while(n!=i)
{
 
g = g*10;
g=g+1;
i++;
}
//cout<<g+1;
 
    for(int i=0;i<n;i++)
        q.push(1);
        //b*=n-1;
    b*=1;
    __int64 freq;
    __int64 begin;
    __int64 end;
 
 
 
    
    QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
    QueryPerformanceCounter ((PLARGE_INTEGER) &begin);  
        
    
        
            
        for(int i=0;i<n;i++)
            v=q.front();
    
    for(int i=1;i<g;i++)
    {
        num2=num=i;
            while(num!=0)
            {
                temp+=num%10;
 
                num=num/10;
            }
            if(temp==n)
                if(test(num2)==1)
                {
    
                    if('\n')
                    
                        {
                            a++;
 
                        }
         p=p+a;  a=0;
                }
                temp=0;
    }
 
    
 
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    cout<<"time "<<(double)(end - begin) /( double)freq<<endl;
    cout<<p+1;
        
    getch();
    system("cls");
    }
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.10.2013, 18:51     Динамическое программирование
Посмотрите здесь:

C++ Динамическое программирование
Динамическое программирование C++
C++ Динамическое программирование
C++ динамическое программирование
C++ Динамическое программирование
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
23.10.2013, 19:02     Динамическое программирование #2
что значит "динамически"?
Семан
1 / 1 / 0
Регистрация: 13.03.2012
Сообщений: 246
23.10.2013, 19:21  [ТС]     Динамическое программирование #3
Динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи.
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
23.10.2013, 20:53     Динамическое программирование #4
как-то так. используется рекурсия-это и есть разбиение большой задачи на малые. есть маленький минус. надо учитывать,что для цифр всегда есть вариант сама же цифра, то есть 3 имеет разложения 1+1+1, 2+1, 1+2, 3, а для чисел больших 10, таких вариантов нет.
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
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
int myfunc(int a)
{
    int temp = 0;
    if (a==0)
        return 1;
    if (a/10)
        for(int i = 1; i <= 9; ++i)
            cout<<i<<"+";
    else 
        for(int i = 1; i <= a; ++i)
            temp+=myfunc(a-i);
    return temp;
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    int a;
    cin>>a;
    cout<<myfunc(a)<<endl;
    system("pause");
    return 0;
}
Семан
1 / 1 / 0
Регистрация: 13.03.2012
Сообщений: 246
23.10.2013, 21:06  [ТС]     Динамическое программирование #5
нормально работает до n=9 дальше не работает так как надо, из за чего такое может быть?

Добавлено через 2 минуты
все исправил, спасибо большое))
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
23.10.2013, 21:14     Динамическое программирование #6
Семан, мне не с чем сверять больше,чем до 4, потому не знаю) а на сколько результат расходится?

Добавлено через 20 секунд
Семан, а в чем ошибка моего творения?

Добавлено через 1 минуту
ааа....да...я ее немного тестировал и не то удалил, простите
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.10.2013, 21:21     Динамическое программирование
Еще ссылки по теме:

C++ ДП Динамическое программирование
C++ Динамическое программирование
C++ Динамическое программирование

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

Или воспользуйтесь поиском по форуму:
Семан
1 / 1 / 0
Регистрация: 13.03.2012
Сообщений: 246
23.10.2013, 21:21  [ТС]     Динамическое программирование #7
Да нечего, спасибо вам большое все отлично) работает
Yandex
Объявления
23.10.2013, 21:21     Динамическое программирование
Ответ Создать тему
Опции темы

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