Подпоследовательность – арифметическая прогрессия

Опубликовано Mar 16, 2012 в Массивы и строки | 13 коммент.

, , , ,

Подпоследовательность – арифметическая прогрессия

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

Так задача ставилась изначально. Дальше пришло время, по задаче возникло обсуждение и были предложены решения. В результате этого стало очень наглядно видно, что происходит, когда условие задачи содержит неопределенность, которую  необходимо снимать, перед тем как приступать собственно к программированию.

Итак, какие вопросы уместны в данном случае?

1) Разность прогрессии может быть любым или ищем прогрессию максимальной длины с заданной разностью? От ответа, очевидно, зависит алгоритм.

2) Что должна вернуть функция в случае удачи? Имеются два здравых варианта:

  • индексы/итераторы на начало и конец найденной подпоследовательности (begin_pro и end_pro);
  • индекс/итератор на начало найденной подпоследовательности и количество элементов в ней – оба этих варианта присутствуют среди решений (begin_pro и nmax);
  • возможен еще логический выходной параметр с очевидным смыслом (нашли/не нашли).

3) Что должна вернуть функция в случае неудачи, когда в массиве нет подпоследовательности-прогрессии? И что, собственно, такое арифметическая прогрессия – два элемента или больше двух?

  • Разумным кажется рассматривать подпоследовательность больше, чем из двух элементов, как это справедливо замечено в комментариях.  
  • Если такая подпоследовательность отсутствует, то разумно вернуть сочетание выходных параметров из пункта 2), которое однозначно трактуется как то, что прогрессия не найдена.  Например, равные  значения begin_pro и end_pro, указывающие на последний элемент массива, или begin_pro  указывает на последний элемент, а nmax = 0, (1, 2). В вызывающей программе проверка на то, что прогрессия не найдена, должна однозначно выполняться по значениям этих выходных параметров, без вовлечения в if самого массива, поэтому возврат индексов/итераторов за границами массива кажется не самым лучшим вариантом.

4) Что должна вернуть функция, если подпоследовательностей, удовлетворяющих условию больше, чем одна? Например, данные о самой первой или самой последней такой последовательности. Развитием этого сюжета является построение динамической структуры данных, для возврата всех правильных вариантов ответа.

 


Автор публикации:

13 Коммент. : “Подпоследовательность – арифметическая прогрессия”

  1. Anton says:

    Вот решил,после упорной работы получилось.

    int MaxArithmProgression(vector<int> GivenArray, int &nmax)
    {
     int i = 0;
     int ncur = 1; int icur = 0;
     int imax =0; 
     
     
      while (i = GivenArray.size()-1) break;
       }
     
     
       if(ncur > nmax)
       {
        imax = icur;
        nmax = ncur;
       }
     
       if(i >= GivenArray.size()-1) break;
       i = i + 1;
      }
     
      return imax;
    }
    • Галина says:

      Что-то здесь у вас напутано. В программе явно не правильно расставлены скобки.

  2. Anton says:

    Извиняюсь, потерял часть программы.

    int MaxArithmProgression(vector<int> GivenArray, int &nmax)
    {
     int i = 0;
     int ncur = 1; int icur = 0;
     int imax =0; 
     
     
      while (i < GivenArray.size() - 2)
      { 
       ncur = 1;
     
       int d = GivenArray[i+1] - GivenArray[i];
       icur = i;
       while((GivenArray[i+1] - GivenArray[i] == d))
       {
     
        ncur++;
        ++i;
        if(i >= GivenArray.size()-1) break;
       }
     
     
       if(ncur > nmax)
       {
        imax = icur;
        nmax = ncur;
       }
     
       if(i >= GivenArray.size()-1) break;
       i = i + 1;
      }
     
      return imax;
    }
    }
  3. Не самый оптимальный вариант но тоже вариант:

     
    #include "stdafx.h"
     
    #include <iostream>
    #include <vector>
     
    /*
    Дан массив произвольной длины. Определить, с какого его элемента начинается
    подпоследовательность, которая будучи арифметической прогрессией,
    имеет максимальную длину.
    */
    #define STEP 3
    using namespace std;
     
    bool average_arithmetic(const int prev, const int forward, const int current)
    {
    return ((prev+forward)/2==current)?true:false;
    }
    int main()
    {
    	int a[20] = {1,2,3,4,5,6,7,8,9,10,3,1,2,3,4,9,8,1,2,3};
     
    	//int seed __attribute__((unused)) =1;
    	int cnt=2;
    	vector<int> cnts;
    	bool flag=false;
    	for(int i=1; i<20; i++)
    	{
    		if(average_arithmetic(a[i-1],a[i+1],a[i]))
    		{
    			cnt++;
    			flag=true;
    		}
     
    		else
    		{
    			if(flag){
    				cnts.push_back(cnt);
    				cnt = 2;
    			}
    			flag=false;
     
    		}
    	}
    	for(vector<int>::iterator i = cnts.begin(); i!=cnts.end(); i++)
    		cout<<*i<<endl;
     
    	return 0;
    }
    • Галина says:

      Программу исправлял модератор – пытались найти “съеденный код” после исправления ошибки парсера кода на сайте. Вопрос к автору – правильно восстановили?

      Ответом для данного случая должен быть, очевидно, массив 1,2,3,4,5,6,7,8,9,10 . Данный код его не выдает.

      Общие замечания по стилю реализации:

      Ни в коем случае не должно быть “магических чисел” – в данном случае размерность конкретного массива – число 20- в цикле. Лучше всего – подобные задачи решать на полностью динамических массивах. Если пока трудно – то делайте размерность константой, задавая ее а ОДНОМ МЕСТЕ.

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

  4. Вот мой вариант:

    typedef vector<int> int_vec;
    typedef int_vec::iterator int_iter;
     
     
    void GetMaxPro(int_vec& vec,int d,int_iter& begin_pro,int_iter& end_pro)
    {
    int_iter end(vec.end());
    int_iter prev(vec.begin());
    int_iter begin_pro_tmp=end;
    int_iter end_pro_tmp=end;
    begin_pro=end;
    end_pro=end;
     
    if(vec.empty()||vec.size()<2)return;
     
    bool in_pro=false;
     
    	for(int_iter next=prev+1;next<end;++prev,++next)
    	{
          if((*next-d)==*prev)   
    	  {
    			if(!in_pro)
    			{
    			 begin_pro_tmp=prev;
    			 end_pro_tmp=next;
    			 in_pro=true;
    			}
    			else end_pro_tmp=next;
    	  }
    	  else	  if(in_pro)
    			  {
    				in_pro=false;
    				if((end_pro_tmp-begin_pro_tmp)>(end_pro-begin_pro))
    				{
    				 begin_pro=begin_pro_tmp;
    				 end_pro=end_pro_tmp;
    				}
    	          }
    	}
     
    	if(in_pro && (end_pro_tmp-begin_pro_tmp)>(end_pro-begin_pro))
    	{
    	  begin_pro=begin_pro_tmp;
    	  end_pro=end_pro_tmp;
    	}
     
    }
    • Галина says:

      Вот код для тестовых запусков для этой программы. Есть проблемы.

      int a[20] = {1,2,3,4,5,6,7,8,9,10,3,1,2,3,4,9,8,1,2,3};
      	vector<int> GivenArr;
      	for(int i=0; i<20; ++i) GivenArr.push_back(a[i]);
       
      	int_iter begin_pro; int_iter end_pro;
       
      	int d = 1; // все хорошо
       
      	/* если искать прогрессию с разностью = 2, 
              в массиве, где ее нет, - все плохо
      	int d = 2; 
      	*/
      	GetMaxPro(GivenArr, d, begin_pro, end_pro);
       
      	for(int_iter it = begin_pro; it<=end_pro; ++it)
      	{
      		cout << *it << endl;
      	}

      И по условию нужно искать прогрессию максимальной длины с любой разностью, а не с заданным. Поэтому разность должна быть выходным параметром.

      • Не “все плохо” если учесть, что обычно функции поиска при отрицательном результате возвращают итераторы за конец контейнера. Перед использованием эти итераторы всегда нужно проверять на корректность.
        Во вторых, при заданном d находится последовательность даже из двух элементов. Однозначно определить прогрессию,не зная ее шага, можно на основании трех элементов. Т.е. если в массиве не найдется последовательности из трех чисел, то прогрессией можно считать любые два соседние элемента, а это уже неопределенность(хорошо это или не очень?).
        Если необходимо также найти шаг прогрессии, то можно сделать так:

        void GetMaxPro(int_vec& vec,int& d,int_iter& begin_pro,int_iter& end_pro)
        {
        int_iter end(vec.end());
        int_iter prev(vec.begin());
        int_iter begin_pro_tmp=end;
        int_iter end_pro_tmp=end;
        begin_pro=end;
        end_pro=end;
         
        if(vec.empty()||vec.size()<2)return;
         
        bool in_pro=false;
        d=vec[1]-vec[0];
        	for(int_iter next=prev+1;next<end;++prev,++next)
        	{
              if((*next-d)==*prev)   
        	  {
        			if(!in_pro)
        			{
        			 begin_pro_tmp=prev;
        			 end_pro_tmp=next;
        			 in_pro=true;
        			}
        			else end_pro_tmp=next;
        	  }
        	  else	  if(in_pro)
        			  {
        				in_pro=false;
        				if((end_pro_tmp-begin_pro_tmp)>(end_pro-begin_pro))
        				{
        				 begin_pro=begin_pro_tmp;
        				 end_pro=end_pro_tmp;
        				}
        	          }
        	}
         
        	if(in_pro && (end_pro_tmp-begin_pro_tmp)>(end_pro-begin_pro))
        	{
        	  begin_pro=begin_pro_tmp;
        	  end_pro=end_pro_tmp;
        	}
         
        }
        • Галина says:

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

          Я добавлю вопросы, которые стоит задать перед началом реализации, в сам пост.

          • Если я не ошибаюсь, знаменатель – у геометрической прогрессии, а по условию задачи ищем арифметическую прогрессию, у которой есть разность.

          • Галина says:

            Да, конечно, у арифметической прогрессии – разность. Спасибо, исправили.

          • begemot says:

            Вот моя реализация.
            Возвращаются итераторы на начало и конец прогрессии максимальной длины с произвольной разностью. В случае если прогрессия длиной более 2 элементов не найдена, возвращаются итераторы на начало массива. Впрочем, это легко исправить при наличии особенного требования к этому моменту.

            void GetArithmeticProgr(vector<int> &ArrayVec,vector<int>::const_iterator &itBeginProgr,vector<int>::const_iterator &itEndProgr,int &d)
            {
            	vector<int>::const_iterator it,itTmpFirst,itTmpLast;
            	int nMaxCount=0, nCurrCount = 0, tmpD = 0,LastD=0;
             
            	itBeginProgr = itEndProgr = itTmpFirst = itTmpLast = ArrayVec.begin();
            	d=0;
             
            	for(it = ArrayVec.begin(); it<ArrayVec.end(); it++)
            	{
            		if(it == ArrayVec.begin())
            		{
            			nCurrCount++;
            			continue;
            		}
            		tmpD = *it-*(it-1);
             
            		if (nCurrCount==1)
            		{
            			itTmpFirst	= it-1;
            			LastD		= tmpD;
            		}
            		if (tmpD == LastD)
            		{
            			itTmpLast = it;
            			nCurrCount++;
            			if ((nCurrCount>nMaxCount) &&
            				(nCurrCount>2))
            			{
            				nMaxCount		= nCurrCount;
            				itBeginProgr	= itTmpFirst;
            				itEndProgr		= itTmpLast;
            				d				= LastD;
            			}
            		}
            		if (tmpD != LastD)
            		{
            			nCurrCount	= 2;
            			itTmpFirst	= it-1;
            			itTmpLast	= it;
            			LastD		= tmpD;
            		}
            	}
             
            }
          • Галина says:

            Работоспособно.

Оставить комментарий

Ваш адрес email не будет опубликован.


*