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

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

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

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

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

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

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

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

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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
07.07.2011, 23:31  [ТС]     Динамическое программирование #3
Спасибо большое , Daemon025 !
Jupiter
Каратель
Эксперт С++
6553 / 3973 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
07.07.2011, 23:33     Динамическое программирование #4
http://ru.wikipedia.org/wiki/Наибольшая_общая_подстрока
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
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
08.07.2011, 00:21  [ТС]     Динамическое программирование #6
Спасибо, Jleloush , мне тоже для двух строк(забыл указать) но это похоже не то...Мне нужно по такому образцу:
Например: 1-ая строка SUBSEQUENCE
2-ая строка SUBEUENCS
Чтобы вывело: UENC , т.е наибольшую общую подстроку. Только как это проще сделать? Читал в википедии - там слишком сложно, может как-нибудь попроще можно...
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.07.2011, 06:31     Динамическое программирование #7
Цитата Сообщение от c++\noob Посмотреть сообщение
Помогите пожалуйста,кто может, со следующими задачами, так как в С++ слабо разбираюсь, а к понедельнику надо сдать...
1. Определить сколько в линейном массиве групп одинаковых идущих подряд элементов.
2. Даны длины двух сторон треугольника и один из его углов. Определить максимальный периметр треугольника, который можно построить из этих элементов.
3. Даны символьные строки. Определить общую подстроку максимальной длины.
А при чем здесь ДП? Разве что в третьей задаче...
c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
08.07.2011, 11:39  [ТС]     Динамическое программирование #8
Как бы мы в универе щас занимаемся ДП, т.е разбивание задач на подзадачи, решение их как можно более оптимальным способом, используя минимальное число циклов и т.д. А ДП тут при том, что все данные задачи нужно таким же образом решить , т.е наиболее эффективным способом и с минимумом затрат...
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.07.2011, 12:09     Динамическое программирование #9
Цитата Сообщение от 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
-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
Эксперт С++
2846 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
08.07.2011, 21:32     Динамическое программирование #13
Цитата Сообщение от c++\noob Посмотреть сообщение
В википедии к 3-ей задаче нашёл псевдокод
Ну какой же это псевдокод ? Это обычная функция написана на чистом С++.

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

Добавлено через 5 минут
Цитата Сообщение от asics Посмотреть сообщение
STL входит в стандартную библиотеку С++.
Я понимаю, только нужно реализовать как-нибудь проще,например с библиотекой iostream...Я как бы на первом курсе и <vector> мы ещё не изучали...
Например, запрашивает ввести 1-ую строку, затем 2-ую, а далее идёт поиск наибольшей общей подстроки...и в конце выводит, к примеру:"Наибольшая общая подстрока: ... "
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2011, 05:14     Динамическое программирование
Еще ссылки по теме:

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

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

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

Динамическое программирование - C++
Помогите решить задачу! Я что-то особо не соображу... 1.Написать программу, реализующую действия: а. сформировать ленточную матрицу...

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


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

Или воспользуйтесь поиском по форуму:
pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
09.07.2011, 05:14     Динамическое программирование #15
с вектором куда уж проще то.
Yandex
Объявления
09.07.2011, 05:14     Динамическое программирование
Ответ Создать тему
Опции темы

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