рекурсивная функция — подпоследовательность
Я пытаюсь получить рекурсивную функцию, которая должна сравнить два массива int и сказать, что массив array2 является подпоследовательностью array1.
Моя проблема сейчас в том, что я не знаю, когда устанавливать возвращаемое значение рекурсивной функции bool.
Я рад за любую помощь.
int array1 [] = {1 ,2 ,3 ,4 ,5 ,6,7,8,9,10};
int array2 [] = {2,4,6,8};
int l1 = 10;
int l2 = 4;bool isSubset ( int p1 , int p2) {
while (p1 <= l1) {
if (array1[p1] == array2[p2]) {
isSubset(p1 + 1, p2 + 1);
} else {
isSubset(p1 + 1, p2);
}
}
}int main (void) {
if ( isSubset(0,0))
cout << "yes" << endl ;
else
cout << " no " << endl ;
return 0;
}
Решение
Вернуть true если вы нашли все предметы array2 (то есть, если p2 == l2). Если вы достигли конца array1, но есть еще некоторые предметы array2 что вы еще не нашли, возвращайтесь false,
В противном случае соберите все результаты рекурсивных вызовов isSubset и если есть хотя бы один true, вернуть true,
Код:
bool isSubset ( int p1 , int p2) {
if(p2 >= l2) return true; // we have found all array2's items
if(p1 >= l1) return false;
bool result = false;
while (p1 < l1 && !result) { // whether we have found the subsequence - break the loop
if (array1[p1] == array2[p2]) {
result |= isSubset(p1 + 1, p2 + 1);
} else {
result |= isSubset(p1 + 1, p2);
}
++p1;
}
return result;
}
И вам здесь не нужен цикл while, это тоже будет работать:
bool isSubset ( int p1 , int p2) {
if(p2 >= l2) return true; // we have found all array2's items
if(p1 >= l1) return false;
if(array1[p1] == array2[p2]){
return isSubset(p1 + 1, p2 + 1);
}else{
return isSubset(p1 + 1, p2);
}
}
Или даже короче
bool isSubset ( int p1 , int p2) {
if(p2 >= l2) return true; // we have found all array2's items
if(p1 >= l1) return false;
return isSubset(p1 + 1 , p2 + (array1[p1] == array2[p2]));
}
постскриптум isSubset в этом случае это плохое имя, потому что этот алгоритм чувствителен к порядку.
Другие решения
Других решений пока нет …