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

Как переделать под динамическое программирование? - C++

Восстановить пароль Регистрация
 
Чорний кот
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 20
16.12.2013, 09:46     Как переделать под динамическое программирование? #1
Есть одномерный массив длиной N, заполненный числами от -10 до 10. Найти максимальную сумму, если можно брать следующий элемент, или через один.
Условие сделать рекурсию и сократить количество вызовов с помощью динамического программирования.
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
#include <iostream>
#include <cstdlib>
using namespace std;
int f(int m[], int n, int i = 0, int sum = 0)
{
int a = -20, b = -20;
if (i + 2 < n)
{
a = f( m, n, i + 2, sum + m[i + 2]);
}
if (i + 1 < n){
b = f( m, n, i + 1, sum + m[i + 1]);
}
else return sum;
if (a < b)return b;
else return a;
 
}
int main()
{
int N=0;
cout << "Razmer masuva: "<<endl;
cin >> N;
int let[50];
cout << "Masuv :";
for (int u = 0; u < N; u++)
{
let[u] = rand() %20-10;
cout<<let[u]<<"  ";
};
cout << "maximal'naya summa:" << f(let, N) << endl;
system("PAUSE");
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.12.2013, 09:46     Как переделать под динамическое программирование?
Посмотрите здесь:

C++ Динамическое программирование
C++ динамическое программирование
C++ ДП Динамическое программирование
C++ Как работает динамическое выделение памяти под объект?
C++ Динамическое программирование
C++ Динамическое программирование!
Как переделать под себя интерфейс редактора Emacs? C++
Как правильно переделать программу с двумерным массивом под работу с указателями? C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Чорний кот
0 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 20
18.12.2013, 21:24  [ТС]     Как переделать под динамическое программирование? #2
Правельный ответ если кому надо!!!!
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
#include <iostream>
#include <cstdlib>
using namespace std;
 
int tmp[50];
 
int f(int m[], int n)
{
    if (n == 0) return m[0];
    if (n == 1) return m[0] + m[1];
    if (tmp[n] != 0) return tmp[n];
    int S1 = f(m, n - 2);
    int S2 = f(m, n - 1);
    int result = ((S1 < S2) ? S2 : S1 )+ m[n];
    tmp[n] = result;
    return result;
}
 
int main()
{
    int N=0;
    cout << "Rozmir masuvu: "<<endl;
    cin >> N;
    for (int t = 0; t < 50; t++)
    {
        tmp[t] = 0;
    }
    int let[50];
    cout << "Masuv :";
    for (int u = 0; u < N; u++)
    {
        let[u] = rand() %20-10;
        cout<< let[u]<<"  ";
    }
    cout << "maximal'na summa:" << f(let, N-1) << endl;
    system("PAUSE");
    return 0;
}
Yandex
Объявления
18.12.2013, 21:24     Как переделать под динамическое программирование?
Ответ Создать тему
Опции темы

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