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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.84
c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
#1

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

07.07.2011, 22:48. Просмотров 2376. Ответов 25
Метки нет (Все метки)

Помогите пожалуйста,кто может, со следующими задачами, так как в С++ слабо разбираюсь, а к понедельнику надо сдать...
1. Определить сколько в линейном массиве групп одинаковых идущих подряд элементов.
2. Даны длины двух сторон треугольника и один из его углов. Определить максимальный периметр треугольника, который можно построить из этих элементов.
3. Даны символьные строки. Определить общую подстроку максимальной длины.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.07.2011, 22:48
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Динамическое программирование (C++):

Динамическое программирование! - C++
#include <cstdio> #include <algorithm> using namespace std; int a, n, m; int main() { scanf(" %d %d", &n,...

Динамическое программирование - C++
Столкнулся с такой задачей. Есть 6 фигурок площадью 3. Нужно узнать, сколькими способами можно полностью замостить ими поле n на m,...

Динамическое программирование - C++
Задача: Есть n работников и n работ. Необходимо найти максимальную суммарную производительность. Каждый работник может выполнять только...

Динамическое программирование - C++
На расстоянии n шагов от магазина стоит А. Каждую минуту он выбирает куда сделать шаг: к магазину или в противоположном направлении. ...

Динамическое программирование - C++
народ помогите пожалуйста. есть задача Написать программу, позволяющую вычислить количество чисел, не содержащих нули, сумма цифр...

Динамическое программирование - C++
Есть такая задача: Дана схема стены, необходимо проверить можно ли построить данную стену заданным набором кирпичей. Кирпич высот 1, а...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 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;
}
2
c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
09.07.2011, 14:53  [ТС] #17
Спасибо , valeriikozlov! Всё отлично работает! Ещё бы вторую задачу...
0
valeriikozlov
Эксперт C++
4670 / 2496 / 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
1
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;
}
0
valeriikozlov
Эксперт C++
4670 / 2496 / 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;
}
проверяйте.
1
c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
10.07.2011, 00:24  [ТС] #21
Спасибо большое, valeriikozlov. В очередной раз выручили...
0
c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
14.07.2011, 13:23  [ТС] #22
valeriikozlov, извините за беспокойство, но не могли бы вы в задаче с нахождением подстроки прокомментировать код, т.е дать обозначения переменным,объяснить что делает каждый цикл. Просто для препода надо составить отчёт по программам с комментариями, а я не во всём разбираюсь.
Заранее спасибо!
0
CAHTEXHUK
Заблокирован
14.07.2011, 13:25 #23
летом не можете день выделить на изучение языка?
0
Nameless One
14.07.2011, 13:43
  #24

Не по теме:

c++\noob
обратный слеш надо экранировать, а то перевод строки получается

0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
14.07.2011, 17:26 #25
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
#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,// для хранения длины максимально совпадающей подстроки (изначально максимальное совпадение равно 0)
            i_st,// для хранения индекса начала совпадающей подстроки в первой строке (где в первой строке начинается искомая подстрока)
            tmp, // длинну очередной найденной подстроки храним в этой переменной 
            i, j;
        for(i=0;i<p1;i++)// в этом цикле перебираем первую 
                {
                        for(j=0; j<p2; j++)// в этом цикле перебираем вторую строчку
                        {
                                tmp=0;// изначально длину очередной подстроки считаем 0 
                                while(i+tmp<p1 && j+tmp<p2 && s1[i+tmp]==s2[j+tmp])// пока не закончилась первая и вторая строка и символы в первой и второй строчках совпадают
                                {
                                        tmp++;// увеличиваем длину подстроки на 1                                  
                                }
                                if(tmp>max)// если длина найденной подстроки больше чем найденные ранее 
                                {
                                        max=tmp;// в max  заносим длину найденной подстроки
                                        i_st=i; // в i_st заносим начало найденной подстроки в перво1 строке
                                }
                        }
                }
                if(max==0)
                        cout<<"Нет подстроки"<<endl;
                else
                {
                        for(i=0; i<max; i++)// в этом цикле выводим найденную подстроку на экран
                                cout<<s1[i_st+i];
                        cout<<endl;
                } 
        return 0;
}
1
c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
15.07.2011, 11:29  [ТС] #26
спасибо большое
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.07.2011, 11:29
Привет! Вот еще темы с ответами:

Динамическое программирование - C++
Не понимаю динамических структур, списков, работы с ними. Посоветуйте источник изучения. Что-то вроде того что написано здесь...

Динамическое программирование. - C++
Помогите, пожалуйста, составить алгоритм по одному из ниже представленных заданий, используя методы динамического программирования и жадных...

Динамическое программирование - C++
Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт У Пети есть полоска бумаги, разделенная на N клеток. Он хочет...

ДП Динамическое программирование - C++
ограничение времени на тест: 0.5 сек. ограничение памяти на тест: 65536 KB. Рассмотрим все строки длины N, состоящие только из букв...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
15.07.2011, 11:29
Ответ Создать тему
Опции темы

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