On-line: гостей 0. Всего: 0 [подробнее..]
Программисты всех стран, объединяйтесь!

АвторСообщение



ссылка на сообщение  Отправлено: 21.07.18 16:39. Заголовок: Рекурсивная функция, определяющая, является ли один массив подпоследовательностью другого массива.


Задача на рекурсию, постановку которой можно найти в следующем вопросе на Stackoverflow recursive function - subsequence

Например, если имеется два массива

 
int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int a2[] = { 2, 4, 6, 8 };


то требуется рекурсивно определить, является ли массив a2 некоторой подпоследовательностью элементов массива a1.

В исходном вопросе на Stackoverflow оба массива отсортированы. Поэтому легко определить является ли второй массив подпоследовательностью первого массива, использовав стандартный алгоритм std::includes.

Например,

 
#include <iostream>
#include <iomanip>
#include <iterator>
#include <algorithm>

int main()
{
int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int a2[] = { 2, 4, 6, 8 };

std::cout << std::boolalpha << std::includes( std::begin( a1 ), std::end( a1 ), std::begin( a2 ), std::end( a2 ) ) << '\n';

a2[0] = 4; // a2 is { 4, 4, 6, 8 }

std::cout << std::boolalpha << std::includes( std::begin( a1 ), std::end( a1 ), std::begin( a2 ), std::end( a2 ) ) << '\n';
}


Вывод этой демонстрационной программы будет следующим

 
true
false


Поэтому несложно написать соответствующую рекурсивную функцию, взяв за основу реализацию данного алгоритма std::includes.

Однако, если рассматривать общий случай, когда массивы не обязательно являются упорядоченными, то такой подход окажется неверным.

Сначала определим, каково базовое условие выхода из рекурсии.

Очевидно, что рекурсию следует прекратить либо когда длина последовательно рассматриваемого под-массива массива a2 равна 0, либо когда длина последовательно рассматриваемого под-массива a1 меньше длины под-массива a2.. То есть когда либо исчерпаны все последовательно рассматриваемые элементы массива a2, либо когда текущий размер последовательно рассматриваемого под-массива a1 меньше размера последовательно рассматриваемого под-массива a2..

Соответствующая рекурсивная функция может выглядеть так, как это показано в приведенной ниже демонстрационной программе.

 
#include <iostream>
#include <iomanip>
#include <iterator>

template <typename T>
bool isSubset( const T a1[], size_t n1, const T a2[], size_t n2 )
{
return ( n2 == 0 ) ||
( not ( n1 < n2 ) && isSubset( a1 + 1, n1 - 1, a2 + ( *a1 == *a2 ), n2 - ( *a1 == *a2 ) ) );
}

int main()
{
int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int a2[] = { 2, 4, 6, 8 };

std::cout << std::boolalpha << isSubset( a1, std::size( a1 ), a2, std::size( a2 ) ) << '\n';

a2[0] = 4; // a2 is { 4, 4, 6, 8 }

std::cout << std::boolalpha << isSubset( a1, std::size( a1 ), a2, std::size( a2 ) ) << '\n';
}


Вывод программы на консоль, как и следовало ожидать

 
true
false


Спасибо: 0 
ПрофильЦитата Ответить
Новых ответов нет


Ответ:
1 2 3 4 5 6 7 8 9
большой шрифт малый шрифт надстрочный подстрочный заголовок большой заголовок видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки моноширинный шрифт моноширинный шрифт горизонтальная линия отступ точка LI бегущая строка оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 11
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет