Определение самой длинной арифметической прогрессии
Оглавление
Введение
Понятие
прогрессии
Постановка
задачи
Определение
самой длинной арифметической прогрессии
Определение
самой длинной геометрической прогрессии
Формирование
самой длинной прогрессии
Дополнительные
возможности
Функциональная
блок-схема
Формирование
последовательности
Определение
самой длинной арифметической прогрессии
Поиск самой
длинной геометрической прогрессии
Формирование
самой длинной прогрессии
Полный текст
программы
Скриншоты
Введение
Условие задачи: в заданной целочисленной последовательности найти такую
подпоследовательность, которая является арифметической или геометрической
прогрессией. Поиск прогрессии будет осуществляться в среде Delphi.
Для начала нужно задать последовательность. Это можно сделать различными
способами: ввод с клавиатуры, чтение из файла, генерирование случайных чисел. В
данной задаче последовательность будет задаваться случайным образом.
Дальнейшей задачей является нахождение самой длинной прогрессии. Для
этого нужно найти все возможные прогрессии, сравнить количества элементов всех
прогрессий между собой и вывести самую длинную из них. То есть придется
сравнить все числа между собой при различных разностях и знаменателях
прогрессий. Причем нужно учесть, что первым элементом прогрессии может быть
любой из элементов последовательности, что усложняет задачу. Для решения этой
задачи будут использоваться программирование вложенных циклов, генератор
случайных чисел, работа с динамическими массивами, работа с процедурами и т.
д..
Понятие прогрессии
Под прогрессией понимают подмножество множества рациональных чисел,
обладающих общей разностью (знаменателем) прогрессии. Разность (знаменатель)
прогрессии - это показатель, показывающий, какую зависимость между собой имеют
члены прогрессии.
Различают арифметические и геометрические прогрессии. Арифметическая
прогрессия - это прогрессия, в которой каждый последующий член прогрессии
отличается от предыдущего на значение, равное разности этой прогрессии.
Геометрическая прогрессия - это прогрессия, в которой отношение любого члена
этой прогрессии к предыдущему члену равно знаменателю прогрессии. Общие формулы
для нахождения n-ного члена таких
прогрессий выглядят так:
- для
арифметической прогрессии,
где
a1 - первый
член прогрессии, d - разность прогрессии;
- для
геометрической прогрессии,
где
b1 - первый
член прогрессии, q - знаменатель прогрессии.
Также
можно находить сумму первых n членов таких прогрессий:
, для
арифметической прогрессии;
, для
геометрической прогрессии.
Постановка задачи
Итак, рассмотрим конкретную задачу. Дана последовательность
хаотично-расположенных натуральных чисел. Из этой последовательности требуется
выделить самую длинную прогрессию, независимо от того, арифметическая она или
геометрическая.
Для начала определим последовательность чисел. Количество элементов (n) последовательности будет задаваться
с клавиатуры. После этого генерируется последовательность (P) элементы которой лежат на отрезке
[-n ; n]. Итак, определена некоторая последовательность P.
Теперь можно приступить к поиску прогрессии.
Определение самой длинной
арифметической прогрессии
Начнем с того, что выберем разность прогрессии. Он, фактически, лежит в
пределах [-n ; n]. Пусть разностью прогрессии является некоторое число dx>0. Этой разности соответствует
некоторая возрастающая прогрессия. Выберем другую разность прогрессии, равную -dx. Очевидно, что этой разности
соответствует некоторая убывающая прогрессия, причем первый элемент этой
прогрессии равен последнему элементу прогрессии, разность которой равна dx, а последний элемент этой прогрессии
равен первому элементу прогрессии, разность которой равна dx. Следовательно, интервал изменения
разности прогрессии можно сузить до [0 ; n]. Значение разности прогрессии, равное нулю, также отбросим,
т. к. при поиске каждого последующего члена прогрессии мы будем приходить к
одному и тому же элементу последовательности. Такая прогрессия будет обладать
бесконечной длиной. Итак, разность прогрессии лежит в пределах [1 ; n]. Будем искать прогрессии при n различных разностях прогрессий.
Будем считать, что мы выбрали некоторую разность прогрессии равную dx.
Далее
нужно выбрать первый член прогрессии. В качестве первого члена прогрессии может
служить любой из элементов последовательности. Нужно перепробовать все элементы
Pi последовательности P, где 
. Примем
один из элементов последовательности за первый член прогрессии и обозначим x.
Теперь
нужно определить длину этой прогрессии. Пусть kol - длина
прогрессии. Ее начальное значение равно 1, т. к. мы уже имеем первый элемент
прогрессии x. Теперь, начиная с первого, будем сравнивать x c остальными элементами последовательности до тех пор,
пока не найдется элемент, отличающийся от x на величину dx. Этот
элемент будет являться вторым элементом прогрессии. То есть kol уже равен 2.
Теперь x примет значение второго члена прогрессии. Далее будем
сравнивать второй член прогрессии с остальными элементами последовательности,
до тех пор, пока не найдется третий элемент прогрессии. Этот процесс будет
продолжаться до тех пор, пока при одном и том же x не переберем
все элементы последовательности. Когда сравним xkol
со всеми остальными элементами последовательности и среди них не окажется
следующего члена прогрессии, то установившееся значение kol
будет длиной этой прогрессии.
Введем
еще одну переменные max_kol (длина самой длинной прогрессии), max_num
(номер, соответствующий элементу последовательности, выбранного за первый
элемент самой длинной прогрессии), max_dx (разность
самой длинной прогрессии). Присвоим значения: max_kol:=kol, max_num:=i, max_dx:=dx.
Примем
за первый член прогрессии следующий элемент последовательности и проделаем все
действия описанные выше. Получим новое значение kol. Если оно
больше чем max_kol, то max_kol:=kol, max_num:=i, max_dx:=dx.
Нужно
проделать все это, пока в качестве первого члена прогрессии не выступит каждый
элемент последовательности. Затем нужно поменять dx и повторять
все, пока не переберем все значения dx. В конце получаем значение
длины самой длинной арифметической прогрессии. Присвоим это значение переменной
y, т. к. при поиске самой длинной геометрической
прогрессии, величина max_kol примет значение длины самой длинной геометрической
прогрессии, а для дальнейшего сравнения этих длин, нужно сохранить значение
длины самой длинной арифметической прогрессии.
Определение самой длинной
геометрической прогрессии
Определение
самой длинной геометрической прогрессии осуществляется аналогично поиску самой
длинной арифметической прогрессии. Выберем пределы, в которых будет меняться
знаменатель. Итак dx лежит в пределах [-n ; n].
Если dx=0, то, начиная со второго члена прогрессии, все члены
прогрессии будут нулевыми. Если dx=1, то членами прогрессии будет являться один и тот же
элемент. Если dx=-1, то членами прогрессии будут являться два,
чередующихся между собой, элемента последовательности, отличающиеся лишь
знаком. Эти прогрессии будут бесконечными. Таким образом, 
.
Дальнейший
поиск геометрической прогрессии будет таким же, как и поиск арифметической
прогрессии. Будем сравнивать длины всех геометрических прогрессий, с длиной
самой длинной арифметической прогрессии. Если найдется такая геометрическая
прогрессия, длина которой больше, чем длина самой длинной арифметической
прогрессии, то переменные max_kol, max_num, max_dx примут новые значения. Единственное, чем отличается
поиск, это то, что каждый последующий элемент должен отличаться от предыдущего
во столько раз, чему равен знаменатель прогрессии.
Формирование самой длинной прогрессии
Итак, мы имеем длину самой длинной прогрессии, ее первый элемент, и ее
разность или знаменатель (в зависимости от того, какая прогрессия). Также у нас
есть переменная y которая приняла
значение длины самой длинной арифметической прогрессии. Сравнив y и max_kol
узнаем, какая прогрессия найдена.Пусть первым элементом массива, в который
будет записываться прогрессия будет элемент под номером max_num.
Теперь надо сравнивать элемент под номером последовательности max_num со всеми остальными элементами последовательности.
Если некоторый элемент отличается от него на величину max_dx,
или в max_dx раз, в зависимости от случая, то записываем этот элемент в
массив. Далее будем сравнивать второй член прогрессии со всеми остальными
элементами последовательности, затем третий и так далее. Формирование
прогрессии закончится, когда ,будем сравнивать n-ный член прогрессии с элементами последовательности, и среди
них не найдется следующего члена прогрессии. На этом прогрессия прерывается.
Дополнительные возможности
Дополнительными возможностями будет являться то, что можно будет вывести
самую длинную прогрессию определенного типа.
Для этого достаточно осуществить определение только арифметической, или
геометрической, прогрессии и затем сформировать ее. Не придется сравнивать
длины самых длинных прогрессий, а просто найти их по отдельности, что даже
упрощает задачу.
Функциональная блок-схема
последовательность прогрессия программа delphi
Формирование последовательности.
procedure TForm1.posledovatelnost(var P:
massiv);n,i:integer;;strtoint(edit1.Text)<250
then:=strtoint(edit1.Text):=250;(P,n);i:=0 to n-1 do begin[i]:=random(n+1)-random(n+1);book1.NumberRC[3,i+2]:=P[i]
end;
P -
последовательность;
N -
длина последовательности.
Определение самой длинной
арифметической прогрессии
procedure TForm1.arithmetic_progression(var P: massiv;max_kol,
max_num, max_dx: integer);i,j,x,dx,kol:integer;:boolean;dx:=1 to high(P) doi:=0
to high(P) do begin:=P[i];:=0;:=0;P[j]=x+dx then begin(kol);:=x+dx;:=true
endbegin:=false;(j) end;(b=true) or (j=high(P));j=high(P);kol>max_kol then
begin_kol:=kol;_num:=i;_dx:=dx end end;;
P -
последовательность;
Max_kol - длина самой длинной прогрессии;
Max_num - номер элемента последовательности,
являющегося первым элементом самой длинной прогрессии;
Max_dx - разность самой длинной прогрессии;
I -
номер элемента последовательности, принятого за первый элемент прогрессии; J - номер элемента последовательности,
с которым сравнивается последний найденный член прогрессии; X - последний найденный член
прогрессии; Dx - разность прогрессии; Kol - длина прогрессии; B - логическая переменная, которая
сообщает о том, что найден следующий член прогрессии.
Поиск
самой длинной геометрической прогрессии
procedure TForm1.geometric_progression(var P:massiv;max_kol,
max_num, max_dx: integer);i,j,x,dx,kol:integer;:boolean;dx:=-high(P) to high(P)
doi:=0 to high(P) doP[i]<>0 then begin:=P[i];:=1;(dx>1) or (dx<-1)
then begin:=0;(P[j]=x*dx) and (j<>i) then begin(kol);:=x*dx;:=true
endbegin:=false;(j) end;(b=true) or (j=high(P));j=high(P);kol>max_kol then
begin_kol:=kol;_num:=i;_dx:=dx end end end;;
P -
последовательность; Max_kol - длина самой длинной прогрессии;
Max_num - номер элемента последовательности,
являющегося первым элементом самой длинной прогрессии; Max_dx -
разность самой длинной прогрессии; I - номер элемента последовательности, принятого за первый элемент
прогрессии; J - номер элемента последовательности,
с которым сравнивается последний найденный член прогрессии; X - последний найденный член
прогрессии; Dx - разность прогрессии; Kol - длина прогрессии; B - логическая переменная, которая
сообщает о том, что найден следующий член прогрессии.
Формирование самой длинной
прогрессии.
procedure TForm1.formirovanie(var P, R: massiv;max_kol,
max_num, max_dx, progression_type:
integer);x,j:integer;:boolean;:=P[max_num];(R,1);[0]:=x;book1.NumberRC[6,2]:=R[0];:=false;progression_type
of
: beginbook1.TextRC[7,11]:=’Разность’+inttostr(max_dx);1book1.TextRC[5,11]:=’Арифметическая прогрессия’;
repeat
j:=0;
repeatP[j]=x+max_dx then
begin:=x+max_dx;(R,length(R)+1);[high(R)]:=x;book1.NumberRC[6,length(R)+1]:=R[high(R)];:=true
endbegin:=false;(j) end(b=true) or (j=high(P));j=high(P) end;
: beginbook1.TextRC[7,11]:=’Знаменатель’+inttostr(max_dx);1book1.TextRC[5,11]:=’Геометрическая прогрессия.’;
repeat:=0;(P[j]=x*max_dx) and (j<>max_num) then
begin:=x*max_dx;(R,length(R)+1);[high(R)]:=x;book1.NumberRC[6,length(R)+1]:=R[high(R)];:=true
endbegin:=false;(j) end(b=true) or (j=high(P));j=high(P) end;
R -
прогрессия;
Progression_type - переменная, определяющая тип
прогрессии, которую нужно сформировать. Значение определяется в основной
процедуре, в результате сравнения длин самой длинной арифметической и самой
длинной геометрической прогрессий. Значению 1 соответствует арифметическая
прогрессия, значению 2 соответствует геометрическая прогрессия.
Max_kol - длина самой длинной прогрессии;
Max_num - номер элемента последовательности,
являющегося первым элементом самой длинной прогрессии;
Max_dx - разность самой длинной прогрессии;
J -
номер элемента последовательности, с которым сравнивается последний найденный
член прогрессии;
X -
последний найденный член прогрессии;
B -
логическая переменная, которая сообщает о том, что найден следующий член
прогрессии.
Полный текст программы
unit Unit1;
interface, Messages, SysUtils, Variants, Classes, Graphics,
Controls, Forms,, Menus, AxCtrls, OleCtrls, VCF1, StdCtrls, Math, OleCtnrs,,
jpeg;=array of integer;= class(TForm): TMainMenu;: TEdit;: TLabel;Book1:
TF1Book;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;:
TMenuItem;: TOleContainer;: TLabel;: TImage;arithmetic_progression(var P:
massiv;max_kol, max_num, max_dx: integer);geometric_progression(var P:
massiv;max_kol, max_num, max_dx: integer);formirovanie(var P, R
:massiv;max_kol, max_num, max_dx, progression_type:
integer);posledovatelnost(var P:massiv);N1Click(Sender:
TObject);N2Click(Sender: TObject);N3Click(Sender: TObject);N4Click(Sender:
TObject);N5Click(Sender: TObject);
{ Private declarations }
{ Public declarations };: TForm1;
{$R *.dfm}
////////////////////////////////////////////////////////////////////////////////
{ Определение арифметической прогрессии.}
procedure TForm1.arithmetic_progression(var P: massiv;max_kol,
max_num, max_dx: integer);i,j,x,dx,kol:integer;:boolean;dx:=1 to high(P) doi:=0
to high(P) do begin:=P[i];:=0;:=0;P[j]=x+dx then begin(kol);:=x+dx;:=true
endbegin:=false;(j) end;(b=true) or (j=high(P));j=high(P);kol>max_kol then
begin_kol:=kol;_num:=i;_dx:=dx end end;;
////////////////////////////////////////////////////////////////////////////////
{Формирование самой длинной прогрессии.}
procedure TForm1.formirovanie(var P, R: massiv;max_kol,
max_num, max_dx, progression_type: integer);x,j:integer;:boolean;:=P[max_num];(R,1);[0]:=x;book1.NumberRC[6,2]:=R[0];:=false;progression_type
of
: beginbook1.TextRC[7,11]:=’Разность’+inttostr(max_dx);1book1.TextRC[5,11]:=’Арифметическая прогрессия’;
repeat
j:=0;
repeatP[j]=x+max_dx then begin:=x+max_dx;(R,length(R)+1);[high(R)]:=x;book1.NumberRC[6,length(R)+1]:=R[high(R)];:=true
endbegin:=false;(j) end(b=true) or (j=high(P));j=high(P) end;
: beginbook1.TextRC[7,11]:=’Знаменатель’+inttostr(max_dx);1book1.TextRC[5,11]:=’Геометрическая прогрессия.’;
repeat:=0;(P[j]=x*max_dx) and (j<>max_num) then
begin:=x*max_dx;(R,length(R)+1);[high(R)]:=x;book1.NumberRC[6,length(R)+1]:=R[high(R)];:=true
endbegin:=false;(j) end(b=true) or (j=high(P));j=high(P) end;
////////////////////////////////////////////////////////////////////////////////
{Определение самой длинной геометрической прогрессии.}
procedure TForm1.geometric_progression(var P:massiv;max_kol,
max_num, max_dx: integer);i,j,x,dx,kol:integer;:boolean;dx:=-high(P) to high(P)
doi:=0 to high(P) doP[i]<>0 then begin:=P[i];:=1;(dx>1) or (dx<-1)
then begin:=0;(P[j]=x*dx) and (j<>i) then begin(kol);:=x*dx;:=true
endbegin:=false;(j) end;(b=true) or (j=high(P));j=high(P);kol>max_kol then
begin_kol:=kol;_num:=i;_dx:=dx end end end;;
////////////////////////////////////////////////////////////////////////////////
{Формирование самой длинной арифметической прогрессии.}
procedure TForm1.N1Click(Sender:
TObject);P,R:massiv;_kol,max_num,max_dx,i,y,progression_type:integer;i:=1 to 2
dobook1.ClearRange(3*i,2,3*i,256,3);_kol:=0;_num:=0;_dx:=0;(P);_progression(P,max_kol,max_num,max_dx);_type:=1;(P,R,max_kol,max_num,max_dx,progression_type);
////////////////////////////////////////////////////////////////////////////////
{Формирование самой длинной геометрической прогрессии.}
procedure TForm1.N2Click(Sender:
TObject);P,R:massiv;_kol,max_num,max_dx,i,y,progression_type:integer;i:=1 to 2
dobook1.ClearRange(3*i,2,3*i,256,3);_kol:=0;_num:=0;_dx:=0;(P);_progression(P,max_kol,max_num,max_dx);_type:=2;(P,R,max_kol,max_num,max_dx,progression_type);
////////////////////////////////////////////////////////////////////////////////
{Формирование самой длинной арифметической или геометрической, в
зависимости от случая, прогрессии}
procedure TForm1.N3Click(Sender:
TObject);P,R:massiv;_kol,max_num,max_dx,i,y,progression_type:integer;i:=1 to 2
dobook1.ClearRange(3*i,2,3*i,256,3);_kol:=0;_num:=0;_dx:=0;(P);_progression(P,max_kol,max_num,max_dx);:=max_kol;_progression(P,max_kol,max_num,max_dx);y<max_kol
then_type:=2_type:=1;(P,R,max_kol,max_num,max_dx,progression_type);
////////////////////////////////////////////////////////////////////////////////
{Очистка результатов.}TForm1.N4Click(Sender:
TObject);book1.ClearRange(3,2,3,256,3);book1.ClearRange(6,2,6,256,3);book1.ClearRange(8,2,10,4,3);.Clear;
////////////////////////////////////////////////////////////////////////////////
{Закрытие программы.}TForm1.N5Click(Sender: TObject);
form1.Close
end;
////////////////////////////////////////////////////////////////////////////////
{Формирование последовательности.}
procedure TForm1.posledovatelnost(var P:
massiv);n,i:integer;:boolean;;strtoint(edit1.Text)<250
then:=strtoint(edit1.Text):=250;(P,n);i:=0 to n-1 do
begin[i]:=random(n+1)-random(n+1);book1.NumberRC[3,i+2]:=P[i] end
end;
////////////////////////////////////////////////////////////////////////////////.
Скриншоты
Основной вид программы.
Меню
Найдена арифметическая прогрессия
Найдена геометрическая прогрессия
Заключение
Проделав весь этот долгий путь, мы пришли к тому, что можем выделить из
любой последовательности самую длинную арифметическую прогрессию, самую длинную
геометрическую прогрессию и самую длинную прогрессию из всех арифметических и
геометрических прогрессий.
Можно было бы предложить несколько иной способ выполнения поставленной
задачи: сформировать самые длинные арифметическую и геометрическую прогрессию,
сравнить их между собой и вывести самую длинную из них. Но, в целях того, чтобы
не находить лишнее а программе, был использован предложенный выше подход.
Таким образом, можно считать что с поставленной задачей мы справились
полностью.
Список
литературы
v Фаронов
В.В. DELPHI. Программирование на языке высокого
уровня. Учебник для вузов. СПб, Питер, 2003.
v Сухарев М.
Delphi. Полное руководство. Включая версию
2010. СПб.: Наука и техника, 2010.
v Иванова
Г.С. Технология программирования: Учебник для вузов. - М.: Изд-во МГТУ им. Н.Э.
Баумана, 2002.
v Киммел П.
Создание приложений в Delphi.
М.: Издат. Дом «Вильямс», 2003.
v Далахвелидзе
П.Г., Марков Е.П. Разработка Web-служб
средствами Delphi. СПб, БХВ-Петербург, 2003.