Отправлено: 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