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

Поиск последовательности элементов максимальной длины в массиве - C++

Восстановить пароль Регистрация
 
Alkcatraz
 Аватар для Alkcatraz
0 / 0 / 0
Регистрация: 24.11.2012
Сообщений: 63
06.01.2013, 17:52     Поиск последовательности элементов максимальной длины в массиве #1
Помогите пожалуйста написать программу, вот условия программы...Даны два массива. Напишите программу, которая находит такую последовательность элементов максимальной длины, которая содержится и в первом, и во втором массивах.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.01.2013, 17:52     Поиск последовательности элементов максимальной длины в массиве
Посмотрите здесь:

Найти отрезок максимальной длины в массиве А C++
Поиск максимальной последовательности в другой последовательности C++
Выполнить в двумерном массиве поиск столбца с максимальной суммой элементов C++
C++ В массиве найти отрезок максимальной длины, в котором первое число равно последнему, второе - предпоследнему и т.д. Напечатать характеристики этого от
Найти первую последовательность максимальной длины в массиве C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
miriganua
129 / 100 / 4
Регистрация: 05.02.2012
Сообщений: 241
06.01.2013, 19:15     Поиск последовательности элементов максимальной длины в массиве #2
Не уверен, что это польностью правильно. Но на моем примере вроде работает.
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
#include <iostream>
 
using std::cout;
using std::cin;
 
int determineLengthOfSequence(int size1, int* array1, int indexOfStartOfSequenceForArray1, int size2, int* array2, int indexOfStartOfSequenceForArray2)
{
    int lengthOfSequence = 0;
    for (int i = indexOfStartOfSequenceForArray1, j = indexOfStartOfSequenceForArray2; i < size1 && j < size2; i++, j++)
    {
 
        if (array1[i] == array2[j])
        {
            lengthOfSequence++;
        }
        else
        {
            return lengthOfSequence;
        }
    }
    return lengthOfSequence;
}
 
int main(int argc, char* argv[])
{
    const int size1 = 10;
    int array1[size1] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
    const int size2 = 15;
    int array2[size2] = {9, 7, 5, 1, 2, 3, 4, 5, 6, 1, 5, 2, 8, 9, 0};
 
    int indexOfStartOfMaxSequenceForArray1 = 0;
    int indexOfStartOfMaxSequenceForArray2 = 0;;
    int lengthOfMaxSequence = 1;
    for (int i = 0; i < size1; i++)
    {
        for (int j = 0; j < size2; j++)
        {
            if (array1[i] == array2[j])
            {
                int temp = determineLengthOfSequence(size1, array1, i, size2, array2, j);
                temp > lengthOfMaxSequence ? lengthOfMaxSequence = temp, indexOfStartOfMaxSequenceForArray1 = i, indexOfStartOfMaxSequenceForArray2 = j : lengthOfMaxSequence = lengthOfMaxSequence;
            }
        }
    }
 
    for (int i = indexOfStartOfMaxSequenceForArray1; i < indexOfStartOfMaxSequenceForArray1 + lengthOfMaxSequence; i++)
    {
        cout << array1[i] << "  ";
    }
    cout << '\n';
 
    return 0;
}
Знаю выглядит ужасно. Строго не судите))
David Sylva
06.01.2013, 21:48
  #3

Не по теме:

Игорь Миронюк очень длинные названия для переменных.

Alkcatraz
 Аватар для Alkcatraz
0 / 0 / 0
Регистрация: 24.11.2012
Сообщений: 63
06.01.2013, 23:47  [ТС]     Поиск последовательности элементов максимальной длины в массиве #4
Цитата Сообщение от Игорь Миронюк Посмотреть сообщение
Не уверен, что это польностью правильно. Но на моем примере вроде работает.

Знаю выглядит ужасно. Строго не судите))
danke, а код попроще есть?
miriganua
129 / 100 / 4
Регистрация: 05.02.2012
Сообщений: 241
07.01.2013, 00:03     Поиск последовательности элементов максимальной длины в массиве #5
В принципе, алгоритм довольно прост. Просто у меня большие названия переменным даны, что б не перепутать ничего. Дай свои имена и код станет не таким ужасным. Если есть вопросы по алгоритму спрашивай?
David Sylva
 Аватар для David Sylva
1280 / 942 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
07.01.2013, 00:05     Поиск последовательности элементов максимальной длины в массиве #6
Игорь Миронюк, Вы меня конечно извините, то так делать нельзя это очень плохой стиль программирования(относительно имён).
miriganua
129 / 100 / 4
Регистрация: 05.02.2012
Сообщений: 241
07.01.2013, 00:08     Поиск последовательности элементов максимальной длины в массиве #7
Я не спорю. Самому не нравится. Просто писал и разбирался параллельно, поэтому и имена давал "говорящие".
Alkcatraz
 Аватар для Alkcatraz
0 / 0 / 0
Регистрация: 24.11.2012
Сообщений: 63
07.01.2013, 01:42  [ТС]     Поиск последовательности элементов максимальной длины в массиве #8
Цитата Сообщение от Игорь Миронюк Посмотреть сообщение
В принципе, алгоритм довольно прост. Просто у меня большие названия переменным даны, что б не перепутать ничего. Дай свои имена и код станет не таким ужасным. Если есть вопросы по алгоритму спрашивай?
я имею ввиду без функции determineLengthOfSequence.
так чтобы всё в 1-й main
4-й месяц Cи++ изучаю
miriganua
129 / 100 / 4
Регистрация: 05.02.2012
Сообщений: 241
07.01.2013, 02:32     Поиск последовательности элементов максимальной длины в массиве #9
Функцию убрал:
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
#include <iostream>
 
using std::cout;
 
int main(int argc, char* argv[])
{
    const int size1 = 10;
    int array1[size1] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
    const int size2 = 15;
    int array2[size2] = {9, 7, 5, 1, 2, 3, 4, 5, 5, 8, 5, 2, 8, 9, 0};
 
    int indexOfStartOfMaxSequenceForArray1 = 0;
    int indexOfStartOfMaxSequenceForArray2 = 0;;
    int lengthOfMaxSequence = 1;
    for (int i = 0; i < size1; i++)
    {
        for (int j = 0; j < size2; j++)
        {
            if (array1[i] == array2[j])
            {
                int lengthOfSequence = 0;
                for (int k = i, l = j; i < size1 && j < size2; k++, l++)
                {
 
                    if (array1[k] == array2[l])
                    {
                        lengthOfSequence++;
                    }
                    else
                    {
                        break;
                    }
                }
                lengthOfSequence > lengthOfMaxSequence ? lengthOfMaxSequence = lengthOfSequence, indexOfStartOfMaxSequenceForArray1 = i, indexOfStartOfMaxSequenceForArray2 = j : lengthOfMaxSequence = lengthOfMaxSequence;
            }
        }
    }
 
    for (int i = indexOfStartOfMaxSequenceForArray1; i < indexOfStartOfMaxSequenceForArray1 + lengthOfMaxSequence; i++)
    {
        cout << array1[i] << "  ";
    }
    cout << '\n';
 
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2013, 03:58     Поиск последовательности элементов максимальной длины в массиве
Еще ссылки по теме:

Поиск последовательности элементов в массиве C++
Поиск последовательности элементов в массиве C++
Найти серию максимальной длины в массиве, используя подпрограмму C++

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

Или воспользуйтесь поиском по форуму:
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
07.01.2013, 03:58     Поиск последовательности элементов максимальной длины в массиве #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
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <iterator>
#include <algorithm>
#include <array>
 
int main()
{
    std::array<int, 16> firstAr =  {7, 4, 9, 6, 7, 1, 2, 4, 5, 6, 1, 5, 2, 8, 9, 0};
    std::array<int, 11> secondAr = {         1, 2, 8, 4, 9, 6, 7, 1,       8, 9, 0};
 
    auto find_pos = firstAr.begin();  //позиция поиска
    auto find_mismatch = std::make_pair(firstAr.begin(), secondAr.begin()); //пара итератовов где элементы несходятся
    auto mynumber = std::make_pair(secondAr.begin(), secondAr.begin());     //пара двух итераторов на на нашу ищуюся последовательность элементов
    unsigned count = 0; //количество наибольших совпадений элементов
 
    for (auto it = secondAr.begin(); it != secondAr.end(); ++it)
    {
        while (find_pos != firstAr.end())
        {
            find_pos = std::find(find_mismatch.first, firstAr.end(), *it);  //найти позицию первого и остальных вхождений елемента *it массива secondAr в массиве firstAr
            if (find_pos != firstAr.end())
            {
                find_mismatch = std::mismatch(find_pos, firstAr.end(), it);  //найти первое несовпадение последовательностей элементов
                if (std::distance(it, find_mismatch.second) > count)
                {
                    mynumber = std::make_pair(it, find_mismatch.second);           //запомнить наибольшею последовательность совпадающих элементов
                    count = std::distance(it, find_mismatch.second);             //обновить количество наибольших совпадений элементов
                }
            }
        }
        find_mismatch.first = firstAr.begin();
        find_pos = firstAr.begin();
    }
 
    std::copy(mynumber.first, mynumber.second, std::ostream_iterator<int>(std::cout," "));
 
    std::cout<<"\n";
    system("pause");
    return 0;
}
Yandex
Объявления
07.01.2013, 03:58     Поиск последовательности элементов максимальной длины в массиве
Ответ Создать тему
Опции темы

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