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

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!