Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
ЗакатСверхновой
0 / 0 / 0
Регистрация: 06.07.2017
Сообщений: 3
#1

Реализация обобщенного алгоритма

06.07.2017, 16:29. Просмотров 839. Ответов 5
Метки нет (Все метки)

Люди, помогите, пожалуйста. Нужно реализовать обобщенный алгоритм, который ищет в диапазоне источника последнюю подпоследовательность, совпадающую с заданной последовательностью, согласно условию, заданному двоичным предикатом. Сама суть задания вполне понятна, но как её реализовать - не знаю
Буду нереально благодарен, если поможете!!!
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.07.2017, 16:29
Ответы с готовыми решениями:

Реализация алгоритма
Смотрите, есть функция для рисования сегмента круга: pieslice(int x, int y,...

Реализация алгоритма
помогите пожалуйсто написать программу: 1. Реализовать алгоритм Insertion-Sort...

Реализация алгоритма RLE
Есть задачка, надо реализовать две функции "закодировать" и "раскодировать"...

Реализация алгоритма Йена на С++
помогите пожалуста реализовать алгоритм Йена есть алгоритм Дейкстры нужно его...

Реализация алгоритма Дейкстры
Кто может подсказать (или указать где найти) код алгоритма Дейкстры на С++?

5
GeFacle
Рэмбо комнатный
95 / 95 / 99
Регистрация: 05.03.2017
Сообщений: 505
Завершенные тесты: 4
06.07.2017, 17:15 #2
предоставьте пример работы программы, пожалуйста
0
ЗакатСверхновой
0 / 0 / 0
Регистрация: 06.07.2017
Сообщений: 3
06.07.2017, 17:54  [ТС] #3
Ну вот, к примеру:
даны деки
C++
1
2
deque<int> d1 = { 0, 13, 3, 14, 5, 6, 0, 1, 2, 3, 14, 5, 6, 8 };
deque<int> d2 = { 14, 5, 6 };
затем выполняется сам алгоритм
C++
1
it = pod_podsled_if(d1.begin(), d1.end(), d2);
которой вернет итератор на начало последней подпоследовательности d2. И тогда в результате
C++
1
for_each(it, d1.end(), [](Complex val) {cout << val << " ";});
на экране будет "14 5 6 8 ".

Добавлено через 5 минут
Вот, что у меня сейчас есть
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <class ForwardIter, class Type>
ForwardIter pod_podsled_if(ForwardIter first, ForwardIter last, Type val) {
    ForwardIter res = last;
    ForwardIter beg = last;
    while (first != last) {
        if (*first == *val.begin()) {
            ForwardIter beginN = val.begin();
            beg = first;
            while (*first == *beginN) {
                *first++; *beginN++;
                if (first == last || beginN == val.end())
                    break;
            }
            if (beginN == val.end())
                res = beg;
        }
        if (first == last)
            return first;
        *first++;
    }
    return beg;
}
Вроде как работает, но, по моему, это слишком "костыльный" вариант

Добавлено через 4 минуты
И в нём пока ещё нет условия, заданного двочиным предикатом.
0
Peoples
1333 / 826 / 747
Регистрация: 06.02.2016
Сообщений: 2,205
Записей в блоге: 17
Завершенные тесты: 4
06.07.2017, 18:47 #4
Можешь посмотреть на реализацию похожего алгоритма из STL
http://ru.cppreference.com/w/cpp/algorithm/search

Добавлено через 13 минут
http://www.cplusplus.com/reference/algorithm/find_end/
1
Геомеханик
785 / 592 / 937
Регистрация: 26.06.2015
Сообщений: 1,409
06.07.2017, 19:21 #5
Лучший ответ Сообщение было отмечено ЗакатСверхновой как решение

Решение

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
#include <iostream>
#include <iterator>
#include <deque>
 
template<typename T, typename Cmp>
T seq_end(T f1, T l1, T f2, T l2, Cmp cmp){
    if(f1 == l1 || f2 == l2)
        return l1;
 
    T a, b, t = l1;
    for(--l1, --l2; l1 != f1; --l1){
        a = l1;
        b = l2;
        while((a != f1) && (b != f2) && cmp(*a, *b)){
            --a;
            --b;
        }
        if((b == f2) && cmp(*a, *b))
            return a;
    }
    return t;
}
 
int main(void){
    std::deque<int> d1 = { 0, 13, 3, 14, 5, 6, 0, 1, 2, 3, 14, 5, 6, 8 };
    std::deque<int> d2 = { 14, 5, 6 };
 
    auto it = seq_end(d1.begin(), d1.end(), d2.begin(), d2.end(), 
                      [] (int a, int b){ return (a == b); });
    std::copy(it, d1.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cin.get();
    return 0;
}
0
ЗакатСверхновой
0 / 0 / 0
Регистрация: 06.07.2017
Сообщений: 3
06.07.2017, 19:36  [ТС] #6
Спасибо огромное!
0
06.07.2017, 19:36
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2017, 19:36

Реализация алгоритма Мандельброта
Знаю, этим уже давно никого не удивить, но я еще раз решил почтить память Бенуа...

Реализация LCS алгоритма на с++
Здравствуйте форумчане!! Помогите заблудшей душе.... Есть задачка ,...

Реализация алгоритма FOREL
Не буду слишком наглым и не буду просить готовое решение, но вопросы будут на...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

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