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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.84
c++\noob
 Аватар для c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
07.07.2011, 22:48     Динамическое программирование #1
Помогите пожалуйста,кто может, со следующими задачами, так как в С++ слабо разбираюсь, а к понедельнику надо сдать...
1. Определить сколько в линейном массиве групп одинаковых идущих подряд элементов.
2. Даны длины двух сторон треугольника и один из его углов. Определить максимальный периметр треугольника, который можно построить из этих элементов.
3. Даны символьные строки. Определить общую подстроку максимальной длины.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.07.2011, 22:48     Динамическое программирование
Посмотрите здесь:

C++ Динамическое программирование
Динамическое программирование C++
C++ динамическое программирование
C++ Динамическое программирование
C++ ДП Динамическое программирование
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Daemon025
 Аватар для Daemon025
380 / 329 / 67
Регистрация: 06.12.2010
Сообщений: 900
07.07.2011, 23:05     Динамическое программирование #2
Цитата Сообщение от c++\noob Посмотреть сообщение
Определить сколько в линейном массиве групп одинаковых идущих подряд элементов.
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
#include <iostream>
#include <time.h>
#include <stdlib.h>
 
 
using namespace std;
 
int main()
{
    srand(time(NULL));
 
    int n;
    cout << "n= ";
    cin  >> n;
 
    int *arr = new int[n];
 
    cout << "Array: ";
    for (int i=0; i<n; i++)
    {
        arr[i] = rand() % 3;
        cout << arr[i] << " ";
    }
 
    int counter = 0;
    int index   = 0;
    while(index<n-1)
    {
        if (arr[index] == arr[index+1])
        {
            while(arr[index] == arr[index+1] && index<n-1)
                index++;
            counter++;
        }
        index++;
    }
 
    cout << "\nCount: " << counter;
 
    delete[] arr;
    cin.get();
    return 0;
}
c++\noob
 Аватар для c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
07.07.2011, 23:31  [ТС]     Динамическое программирование #3
Спасибо большое , Daemon025 !
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
07.07.2011, 23:33     Динамическое программирование #4
http://ru.wikipedia.org/wiki/Наибольшая_общая_подстрока
Jleloush
 Аватар для Jleloush
1 / 1 / 1
Регистрация: 16.01.2010
Сообщений: 26
07.07.2011, 23:56     Динамическое программирование #5
3. Даны символьные строки. Определить общую подстроку максимальной длины.
для двух строк
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
#include "iostream"
#include <Windows.h>
#include <string>
using namespace std;
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    char *s1,*s2;
    s1=new char[50];
    s2=new char[50];
    cout<<"Введи строку1: ";
    gets(s1);
    cout<<"Введи строку2: ";
    gets(s2);
    int p1=strlen(s1);
    int p2=strlen(s2);
    int max=0,temp=0;
    for(int i=0;i<p1;i++)
        for(int j=0;j<p2;j++)
            if(s1[i]==s2[j])
            {
            temp++;
            
            if(temp>max)
                {
                    max=temp;
                }
            }
    
    
    cout<<max<<endl;
    return 0;
}
c++\noob
 Аватар для c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
08.07.2011, 00:21  [ТС]     Динамическое программирование #6
Спасибо, Jleloush , мне тоже для двух строк(забыл указать) но это похоже не то...Мне нужно по такому образцу:
Например: 1-ая строка SUBSEQUENCE
2-ая строка SUBEUENCS
Чтобы вывело: UENC , т.е наибольшую общую подстроку. Только как это проще сделать? Читал в википедии - там слишком сложно, может как-нибудь попроще можно...
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.07.2011, 06:31     Динамическое программирование #7
Цитата Сообщение от c++\noob Посмотреть сообщение
Помогите пожалуйста,кто может, со следующими задачами, так как в С++ слабо разбираюсь, а к понедельнику надо сдать...
1. Определить сколько в линейном массиве групп одинаковых идущих подряд элементов.
2. Даны длины двух сторон треугольника и один из его углов. Определить максимальный периметр треугольника, который можно построить из этих элементов.
3. Даны символьные строки. Определить общую подстроку максимальной длины.
А при чем здесь ДП? Разве что в третьей задаче...
c++\noob
 Аватар для c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
08.07.2011, 11:39  [ТС]     Динамическое программирование #8
Как бы мы в универе щас занимаемся ДП, т.е разбивание задач на подзадачи, решение их как можно более оптимальным способом, используя минимальное число циклов и т.д. А ДП тут при том, что все данные задачи нужно таким же образом решить , т.е наиболее эффективным способом и с минимумом затрат...
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.07.2011, 12:09     Динамическое программирование #9
Цитата Сообщение от c++\noob Посмотреть сообщение
Как бы мы в универе щас занимаемся ДП, т.е разбивание задач на подзадачи, решение их как можно более оптимальным способом, используя минимальное число циклов и т.д. А ДП тут при том, что все данные задачи нужно таким же образом решить , т.е наиболее эффективным способом и с минимумом затрат...
Ну так из вышеперечисленных задач с помощью ДП можно решить только последнюю...
c++\noob
 Аватар для c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
08.07.2011, 12:12  [ТС]     Динамическое программирование #10
Ну так да...1-ая есть (спс Daemon) нужно ещё две...кто знает помогите плиз...
Gepar
08.07.2011, 12:16
  #11

Не по теме:

Простое любопытство: а чего это вы летом в универе учите с++ ? Я бы предположил что это какие курсы, но те кто ходят на такие доп. курсы обычно хотят выучить и пытаются разобраться во всём сами. У вас же ни строчки кода ваших попыток.

c++\noob
 Аватар для c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
08.07.2011, 21:25  [ТС]     Динамическое программирование #12
Летом у нас практика по программированию, сейчас мы изучаем ДП, препод нам толком ничего не объясняет - просто даёт задачу,а если что не понимаем наводит на мысль...А тут нам он дал индивидуальные задачи, поэтому я и прошу чтобы вы помогли или хотя бы идейку подкинули...

Добавлено через 8 часов 42 минуты
В википедии к 3-ей задаче нашёл псевдокод...Только как его теперь на c++ реализовать, с стандартными библиотеками, без всяких векторов и прочего..
Код:
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
void GetLargestCommonSubstring(string & result, const string & a, const string & b) 
{
    const int a_length = a.size();
    const int b_length = b.size();
 
    int max_length = 0;
    int result_index = 0;
 
    vector<int> solution(b_length + 1, 0);
 
    for(int i = a_length - 1; i >= 0; i--) 
    {
        const vector<int> prev_solution = solution;
        for(int j = b_length - 1; j >= 0; j--) 
        {
            if(a[i] != b[j])
                solution[j] = 0;
            else
            {
                const int length = 1 + prev_solution[j + 1];
                if (length > max_length)
                {
                    max_length = length;
                    result_index = i;
                }
 
                solution[j] = length;
            }
        }
    }
 
    result = a.substr(result_index, max_length);
}
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
08.07.2011, 21:32     Динамическое программирование #13
Цитата Сообщение от c++\noob Посмотреть сообщение
В википедии к 3-ей задаче нашёл псевдокод
Ну какой же это псевдокод ? Это обычная функция написана на чистом С++.

Добавлено через 1 минуту
Цитата Сообщение от c++\noob Посмотреть сообщение
с стандартными библиотеками, без всяких векторов и прочего..
STL входит в стандартную библиотеку С++.
c++\noob
 Аватар для c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
08.07.2011, 22:54  [ТС]     Динамическое программирование #14
Цитата Сообщение от asics Посмотреть сообщение
Ну какой же это псевдокод ? Это обычная функция написана на чистом С++.
Я слабо разбираюсь в этом деле так, что извините если ошибся

Добавлено через 5 минут
Цитата Сообщение от asics Посмотреть сообщение
STL входит в стандартную библиотеку С++.
Я понимаю, только нужно реализовать как-нибудь проще,например с библиотекой iostream...Я как бы на первом курсе и <vector> мы ещё не изучали...
Например, запрашивает ввести 1-ую строку, затем 2-ую, а далее идёт поиск наибольшей общей подстроки...и в конце выводит, к примеру:"Наибольшая общая подстрока: ... "
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
09.07.2011, 05:14     Динамическое программирование #15
с вектором куда уж проще то.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.07.2011, 08:18     Динамическое программирование #16
Немного подредактировал код Jleloush для 3-ей задачи. Проверяйте:
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
#include "iostream"
#include <Windows.h>
#include <string>
using namespace std;
 
int main()
{
        SetConsoleCP(1251);
        SetConsoleOutputCP(1251);
        char *s1,*s2;
        s1=new char[50];
        s2=new char[50];
        cout<<"Введи строку1: ";
        gets(s1);
        cout<<"Введи строку2: ";
        gets(s2);
        int p1=strlen(s1);
        int p2=strlen(s2);
        int max=0, i_st, tmp, i, j;
        for(i=0;i<p1;i++)
        {
            for(j=0; j<p2; j++)
            {
                tmp=0;
                while(i+tmp<p1 && j+tmp<p2 && s1[i+tmp]==s2[j+tmp])
                {
                    tmp++;                  
                }
                if(tmp>max)
                {
                    max=tmp;
                    i_st=i;
                }
            }
        }
        if(max==0)
            cout<<"Нет подстроки"<<endl;
        else
        {
            for(i=0; i<max; i++)
                cout<<s1[i_st+i];
            cout<<endl;
        } 
        return 0;
}
c++\noob
 Аватар для c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
09.07.2011, 14:53  [ТС]     Динамическое программирование #17
Спасибо , valeriikozlov! Всё отлично работает! Ещё бы вторую задачу...
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.07.2011, 15:55     Динамическое программирование #18
Цитата Сообщение от c++\noob Посмотреть сообщение
Ещё бы вторую задачу...
На самом деле 2-ая задача не такая уж и сложная.
У нас будет 3 варианта площадей:
- 1 вариант когда угол меду известными сторонами
- 2 варианта когда угол образован только одной из известных сторон и неизвестной стороной
Вот по этой ссылке найдете формулу вычисления площади треугольника по известным трем сторонам, а также формулу перевода градусов в радианы (эта формула Вам пригодится если ввод значения угла в градусах - т.к. тригонометрические формулы в с++ работают с радианами)
http://www.dpva.info/Guide/GuideMath...hSquireVolume/

Для нахождения стороны треугольника для первого варианта подойдет формула из теоремы косинусов:
http://ru.wikipedia.org/wiki/%D2%E5%...ED%F3%F1%EE%E2

Для нахождения стороны треугольника для второго варианта подойдет формула из теоремы синусов:
http://ru.wikipedia.org/wiki/%D0%A2%...81%D0%BE%D0%B2
c++\noob
 Аватар для c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
09.07.2011, 22:21  [ТС]     Динамическое программирование #19
Спасибо! Буду разбираться.

Добавлено через 6 часов 2 минуты
Я сделал двумя способами нахождение 3-ей стороны и периметра, но в условии задачи нужно определить максимальный периметр треугольника, который можно построить с этими элементами,вот тут проблемка...
Не подскажете что надо дописать?
Вот что у меня получилось:
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
#include <cmath>
#include <iostream>
#include <windows.h>
#define _USE_MATH_DEFINES
 
using namespace std;
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    int a,b,p=0;
    double c,gradA,gradB,radA,radB,P;
    do{
    cout<<"------------------------------------------------"<<endl;
    cout<<"Определение максимального периметра треугольника"<<endl;
    cout<<"------------------------------------------------"<<endl;
    cout<<"1 - По двум сторонам и углу между ними"<<endl;
    cout<<"2 - По двум сторонам и углу образованному с третьей стороной"<<endl;
    cout<<"------------------------------------------------------------"<<endl;
    cin>>p;
    switch(p)
    {
    case 1:   cout<<"Введите сторону AB: ";
              cin>>a;
              cout<<"Введите сторону BC: ";
              cin>>b;
              cout<<"Введите угол B: ";
              cin>>gradB;
              radB = gradB*M_PI/180;
              c = sqrt(a*a + b*b - 2*a*b*cos(radB));
              cout<<"Сторона AC: "<<c<<endl;
              P = a+b+c;
              cout<<"Периметр = "<<P<<endl;
              ;break;
              
    case 2:   cout<<"Введите сторону AB: ";
              cin>>a;
              cout<<"Введите сторону BC: ";
              cin>>b;
              cout<<"Введите угол A: ";
              cin>>gradA;
              radA = gradA*M_PI/180;
              double g = asin(a*sin(radA)/b);
              g = g*180/M_PI;
              c = b*sin(M_PI - radA - asin(a*sin(radA)/b))/sin(radA);
              cout<<"Сторона AC: "<<c<<endl;
              P = a+b+c;
              cout<<"Периметр = "<<P<<endl;
              ;break;
              
              
    }
    cout<<"Press 0 to Continue,1 - to Exit "<<endl;
    cin>>p;}
    while(p==0);  
    system("PAUSE");
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2011, 23:23     Динамическое программирование
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.07.2011, 23:23     Динамическое программирование #20
c++\noob, Вычисления вроде правильные. Хотя есть лишнее:
Цитата Сообщение от c++\noob Посмотреть сообщение
double g = asin(a*sin(radA)/b);
g = g*180/M_PI;
и переменные для длин сторон я бы сделал тоже double.
Но не в этом суть.
Для того что бы
Цитата Сообщение от c++\noob Посмотреть сообщение
определить максимальный периметр треугольника
нужно делать так: (проще даже код написать)
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
#include <cmath>
#include <iostream>
#include <windows.h>
#define _USE_MATH_DEFINES
 
using namespace std;
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
   double a, b, gradA, radA, max_P, c, tmp_P;
    cout<<"------------------------------------------------"<<endl;
    cout<<"Определение максимального периметра треугольника"<<endl;
    cout<<"------------------------------------------------"<<endl;
    cout<<"Введите 1-ую сторону: ";
    cin>>a;
    cout<<"Введите 2-ую сторону: ";
    cin>>b;
    cout<<"Введите угол: ";
    cin>>gradA;
    // 1-ый вариант
    radA = gradA*M_PI/180;
    c = sqrt(a*a + b*b - 2*a*b*cos(radA));
    max_P=a+b+c;    
    //2-ой вариант
    c = b*sin(M_PI - radA - asin(a*sin(radA)/b))/sin(radA);
    tmp_P=a+b+c;
    if(max_P<tmp_P)
        max_P=tmp_P;
    // 3-ий вариант
    c = a*sin(M_PI - radA - asin(b*sin(radA)/a))/sin(radA);
    tmp_P=a+b+c;
    if(max_P<tmp_P)
        max_P=tmp_P;
    cout<<"Максимальный периметр треугольника: "<<max_P<<endl;
    system("PAUSE");
    return 0;
}
проверяйте.
Yandex
Объявления
09.07.2011, 23:23     Динамическое программирование
Ответ Создать тему
Опции темы

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