Условие:
В данной последовательности действительных чисел [latex]a_{1},…,a_{20}[/latex] выбрать возрастающую подпоследовательность наибольшей длинны.
Тесты:
| Число элементов в заданной последовательности | Заданная последовательность | Найденная подпоследовательность |
| 20 | 1 44 3 66 2 6 55 2 4 9 50 3 4 12 45 8 15 5 18 48 | 3 6 9 12 15 18 |
| 20 | 1 9 17 25 90 91 92 13 18 23 28 100 75 50 45 44 43 42 41 40 | 1 9 17 25 |
| 20 | 155 100 80 83 86 89 -60 -40 -20 0 20 40 60 33 33 33 0 0 0 0 | -60 -40 -20 0 20 40 60 |
Код:
|
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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 |
#include <stdio.h> #include <iostream> #include <map> #include <string> #include <vector> #include <deque> using namespace std; // вспомогательные типы typedef vector< double > tValues; typedef map< double, bool > tSortedValues; typedef vector< tValues > tSequences; // возвращает true, если первый вектор (wheer) содержит второй (what) bool containValues( tValues& where, tValues& what ) { if ( what.size() > 0 ) { for( int i = 0; i < where.size(); i++ ) { if ( where[ i ] == what[ 0 ] ) { int k = i + 1; int j = 1; for(; j < what.size() && k < where.size() && where[ k ] == what[ j ]; j++, k++ ); return ( j == what.size() ); } } } return false; } // вспомогательная функция печати последовательности void printSequence( tValues& seq ) { if ( seq.size() > 1 ) { double diff = seq[ 1 ] - seq[ 0 ]; cout << "sequence: size=" << seq.size() << ", diff=" << diff << ", values = { "; for( int i = 0; i < seq.size(); i++ ) { cout << seq[ i ] << " "; } cout << "}\n"; } else { cout << "NOT a sequence" << endl; } } int main(void) { int n; cin >> n; if ( n <= 0 ) { cout << "Input error: wrong length of the sequence" << endl; return 0; } tValues sourceValues; // вектор для входных значений, в которых мы будем искать последовательность for( int i = 0; i < n; i++ ) // ввод входных значений { double val; cin >> val; sourceValues.push_back( val ); } // нахождение всех возможные разностей между входными значениями tValues diffValues;// вектор для хранения всех возможные разностей между входными значениями for( int i = 0; i < sourceValues.size(); i++ ) { tSortedValues sortedValues; for( int j = 0; j < sourceValues.size(); j++ ) { if ( j != i ) { double diff = ( i < j ) ? sourceValues[ j ] - sourceValues[ i ] : sourceValues[ i ] - sourceValues[ j ] ; if ( diff > 0 ) { sortedValues[ diff ] = true; } } } for( tSortedValues::iterator it = sortedValues.begin(); it != sortedValues.end(); ++it ) { diffValues.push_back( it->first ); } } // главный цикл по входным значениям tSequences foundSequences;// вектор векторов, в котором будем помещать все найденные последовательности for( int srcValIdx = 0; srcValIdx < sourceValues.size(); srcValIdx++ ) { double seedVal = sourceValues[ srcValIdx ]; // начальное значение для старта поиска последовательности // цикл по вектору разности for( int diffValIdx = 0; diffValIdx < diffValues.size(); diffValIdx++ ) { double diffVal = diffValues[ diffValIdx ]; double lastVal; tValues candidateSeq; candidateSeq.push_back( seedVal ); // поиск последовательности влево от исходного значения lastVal = seedVal; for( int j = srcValIdx - 1; j >= 0; j-- ) { double prevVal = sourceValues[ j ]; if ( prevVal == lastVal - diffVal ) { candidateSeq.insert( candidateSeq.begin(), prevVal ); lastVal = prevVal; } } // поиск последовательности вправо от исходного значения lastVal = seedVal; for( int j = srcValIdx + 1; j < sourceValues.size(); j++ ) { double nextVal = sourceValues[ j ]; if ( nextVal == lastVal + diffVal ) { candidateSeq.push_back( nextVal ); lastVal = nextVal; } } if ( candidateSeq.size() > 2 ) // нейденную последовательность-кандидат помещаем в вектор найденных, если длинна больше двух { foundSequences.push_back( candidateSeq ); } } } // удаляем последовательности, которые включают в себя другие // Удалённые последовательности заменяются на пустышки for( int i = 0; i < foundSequences.size(); i++ ) { if ( ! foundSequences[ i ].empty() ) { for( int j = 0; j < foundSequences.size(); j++ ) { if ( i != j && foundSequences[ i ].size() >= foundSequences[ j ].size() && containValues( foundSequences[ i ], foundSequences[ j ] ) ) { foundSequences[ j ].clear(); } } } } // удаляем из вектора пустышки из прошлого шага { tSequences tmp; for( int i = 0; i < foundSequences.size(); i++ ) { if ( ! foundSequences[ i ].empty() ) { tmp.push_back( foundSequences[ i ] ); } } foundSequences = tmp; } // ищем максимальную последовательность среди найденных int maxSize = -1; int maxIndex = -1; for( int i = 0; i < foundSequences.size(); i++ ) { int size = foundSequences[ i ].size(); if ( size > maxSize ) { maxSize = size; maxIndex = i; } // printSequence( foundSequences[ i ] ); // debug } if ( maxIndex >= 0 ) { cout << "max size sequence:\n"; printSequence( foundSequences[ maxIndex ] ); } return 0; } |
План
План программы:
Задача нахождения искомой подпоследовательности решается путем выделения всех возможных возрастающих последовательностей, которые удастся обнаружить во входной последовательности. Для нахождения какой либо возрастающей последовательности необходимо убедиться, что все числа монотонно возрастают с одинаковым приращением. По — этому алгоритм решения задачи состоит из следующих шагов:
- Находим все возможные приращения, как все возможные разности между входными значениями
- Выполняем цикл по всем входным значениям, для каждого входного значения пытаемся найти остальные значения, имеющие монотонно возрастающее приращение. Это выполняется для каждого найденного приращения. Для этого организуется вложенный цикл по всем приращениям. Он состоит из двух подциклов – движение влево от начального значения – ищем предыдущие члены последовательности с меньшим приращением, и движение вправо – ищем следующие значения последовательности с большим приращением
- Найденные последовательности сохраняем для последующего выбора самой длинной. Последовательности короче трёх элементов, а также с отрицательным приращением(т.е. убывающие) – игнорируем
- Выполняем слияние найденных последовательностей, если они покрывают друг – друга
- Находим последовательность наибольшей длины
Программа реализована с использованием шаблонных классов стандартной библиотеки vector и map. Vector используется для хранения всех используемых последовательностей, включая разности. Map используется, как временный объект для сортировки и слияния приращений, которые в ходе поиска встречаются с часто повторяющимися значениями.
Программа тестировалась с учётом случаев когда могут встречаться убывающие последовательности, которые должны игнорироваться.
Входные данные
Программа позволяет работать не только с фиксированными 20-ю числами. Длинна входной последовательности задаётся. Ввод содржит первым элементом длину последовательности, а затем следуют числа самой последовательности.
Ссылка на ideone.com : http://ideone.com/kf13Zv
Ну, во-первых неправильно работает.
В первом тесте можно к Вашему результату добавить 48. Во втором — например, 90 91 92 100.
А во-вторых, мы изучали динамическое программирование на лекции рассматривали задачу нахождения длиннейшей общей подпоследовательности двух строк. Потом говорили о задаче нахождения длиннейшей алфавитной подпоследовательности символов строки. Остается один шаг до Вашей задачи.