Размещено на http://www.allbest.ru/

2013

Оглавление

• Введение
• Понятие прогрессии
• Постановка задачи
• Определение самой длинной арифметической прогрессии
• Определение самой длинной геометрической прогрессии
• Формирование самой длинной прогрессии
• Дополнительные возможности
• Функциональная блок-схема
• Формирование последовательности
• Определение самой длинной арифметической прогрессии
• Поиск самой длинной геометрической прогрессии
• Формирование самой длинной прогрессии
• Полный текст программы
• Скриншоты
• Введение
• Условие задачи: в заданной целочисленной последовательности найти такую подпоследовательность, которая является арифметической или геометрической прогрессией. Поиск прогрессии будет осуществляться в среде Delphi.
• Для начала нужно задать последовательность. Это можно сделать различными способами: ввод с клавиатуры, чтение из файла, генерирование случайных чисел. В данной задаче последовательность будет задаваться случайным образом.
• Дальнейшей задачей является нахождение самой длинной прогрессии. Для этого нужно найти все возможные прогрессии, сравнить количества элементов всех прогрессий между собой и вывести самую длинную из них. То есть придется сравнить все числа между собой при различных разностях и знаменателях прогрессий. Причем нужно учесть, что первым элементом прогрессии может быть любой из элементов последовательности, что усложняет задачу. Для решения этой задачи будут использоваться программирование вложенных циклов, генератор случайных чисел, работа с динамическими массивами, работа с процедурами и т. д..

Понятие прогрессии

Под прогрессией понимают подмножество множества рациональных чисел, обладающих общей разностью (знаменателем) прогрессии. Разность (знаменатель) прогрессии - это показатель, показывающий, какую зависимость между собой имеют члены прогрессии.

Различают арифметические и геометрические прогрессии. Арифметическая прогрессия - это прогрессия, в которой каждый последующий член прогрессии отличается от предыдущего на значение, равное разности этой прогрессии. Геометрическая прогрессия - это прогрессия, в которой отношение любого члена этой прогрессии к предыдущему члену равно знаменателю прогрессии. Общие формулы для нахождения n-ного члена таких прогрессий выглядят так:

- для арифметической прогрессии,

где a₁ - первый член прогрессии, d - разность прогрессии;

- для геометрической прогрессии,

где b₁ - первый член прогрессии, q - знаменатель прогрессии.

Также можно находить сумму первых n членов таких прогрессий:

, для арифметической прогрессии;

, для геометрической прогрессии.

Постановка задачи

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

Для начала определим последовательность чисел. Количество элементов (n) последовательности будет задаваться с клавиатуры. После этого генерируется последовательность (P) элементы которой лежат на отрезке [-n ; n]. Итак, определена некоторая последовательность P.

Теперь можно приступить к поиску прогрессии.

Определение самой длинной арифметической прогрессии

Начнем с того, что выберем разность прогрессии. Он, фактически, лежит в пределах [-n ; n]. Пусть разностью прогрессии является некоторое число dx>0. Этой разности соответствует некоторая возрастающая прогрессия. Выберем другую разность прогрессии, равную -dx. Очевидно, что этой разности соответствует некоторая убывающая прогрессия, причем первый элемент этой прогрессии равен последнему элементу прогрессии, разность которой равна dx, а последний элемент этой прогрессии равен первому элементу прогрессии, разность которой равна dx. Следовательно, интервал изменения разности прогрессии можно сузить до [0 ; n]. Значение разности прогрессии, равное нулю, также отбросим, т. к. при поиске каждого последующего члена прогрессии мы будем приходить к одному и тому же элементу последовательности. Такая прогрессия будет обладать бесконечной длиной. Итак, разность прогрессии лежит в пределах [1 ; n]. Будем искать прогрессии при n различных разностях прогрессий. Будем считать, что мы выбрали некоторую разность прогрессии равную dx.

Далее нужно выбрать первый член прогрессии. В качестве первого члена прогрессии может служить любой из элементов последовательности. Нужно перепробовать все элементы P_i последовательности P, где . Примем один из элементов последовательности за первый член прогрессии и обозначим x.

Теперь нужно определить длину этой прогрессии. Пусть kol - длина прогрессии. Ее начальное значение равно 1, т. к. мы уже имеем первый элемент прогрессии x. Теперь, начиная с первого, будем сравнивать x c остальными элементами последовательности до тех пор, пока не найдется элемент, отличающийся от x на величину dx. Этот элемент будет являться вторым элементом прогрессии. То есть kol уже равен 2. Теперь x примет значение второго члена прогрессии. Далее будем сравнивать второй член прогрессии с остальными элементами последовательности, до тех пор, пока не найдется третий элемент прогрессии. Этот процесс будет продолжаться до тех пор, пока при одном и том же x не переберем все элементы последовательности. Когда сравним x_kol со всеми остальными элементами последовательности и среди них не окажется следующего члена прогрессии, то установившееся значение 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

Формирование последовательности.

Размещено на http://www.allbest.ru/

2013

procedure TForm1.posledovatelnost(var P: massiv);

var n,i:integer;

begin

randomize;

if strtoint(edit1.Text)<250 then

n:=strtoint(edit1.Text)

else

n:=250;

setlength(P,n);

for i:=0 to n-1 do begin

P[i]:=random(n+1)-random(n+1);

f1book1.NumberRC[3,i+2]:=P[i] end

end;

P - последовательность;

N - длина последовательности.

Определение самой длинной арифметической прогрессии

Размещено на http://www.allbest.ru/

2013

procedure TForm1.arithmetic_progression(var P: massiv;

var max_kol, max_num, max_dx: integer);

Var i,j,x,dx,kol:integer;

b:boolean;

Begin

for dx:=1 to high(P) do

for i:=0 to high(P) do begin

x:=P[i];

kol:=0;

repeat

j:=0;

repeat

if P[j]=x+dx then begin

inc(kol);

x:=x+dx;

b:=true end

else begin

b:=false;

inc(j) end;

until (b=true) or (j=high(P));

until j=high(P);

if kol>max_kol then begin

max_kol:=kol;

max_num:=i;

max_dx:=dx end end;

end;

P - последовательность;

Max_kol - длина самой длинной прогрессии;

Max_num - номер элемента последовательности, являющегося первым элементом самой длинной прогрессии;

Max_dx - разность самой длинной прогрессии;

I - номер элемента последовательности, принятого за первый элемент прогрессии; J - номер элемента последовательности, с которым сравнивается последний найденный член прогрессии; X - последний найденный член прогрессии; Dx - разность прогрессии; Kol - длина прогрессии; B - логическая переменная, которая сообщает о том, что найден следующий член прогрессии.

Поиск самой длинной геометрической прогрессии

Размещено на http://www.allbest.ru/

2013

procedure TForm1.geometric_progression(var P:massiv;

var max_kol, max_num, max_dx: integer);

Var i,j,x,dx,kol:integer;

b:boolean;

Begin

for dx:=-high(P) to high(P) do

for i:=0 to high(P) do

if P[i]<>0 then begin

x:=P[i];

kol:=1;

if (dx>1) or (dx<-1) then begin

repeat

j:=0;

repeat

if (P[j]=x*dx) and (j<>i) then begin

inc(kol);

x:=x*dx;

b:=true end

else begin

b:=false;

inc(j) end;

until (b=true) or (j=high(P));

until j=high(P);

if kol>max_kol then begin

max_kol:=kol;

max_num:=i;

max_dx:=dx end end end;

end;

P - последовательность; Max_kol - длина самой длинной прогрессии;

Max_num - номер элемента последовательности, являющегося первым элементом самой длинной прогрессии; Max_dx - разность самой длинной прогрессии; I - номер элемента последовательности, принятого за первый элемент прогрессии; J - номер элемента последовательности, с которым сравнивается последний найденный член прогрессии; X - последний найденный член прогрессии; Dx - разность прогрессии; Kol - длина прогрессии; B - логическая переменная, которая сообщает о том, что найден следующий член прогрессии.

Формирование самой длинной прогрессии.

Размещено на http://www.allbest.ru/

2013

procedure TForm1.formirovanie(var P, R: massiv;

var max_kol, max_num, max_dx, progression_type: integer);

var x,j:integer;

b:boolean;

begin

x:=P[max_num];

setlength(R,1);

R[0]:=x;

f1book1.NumberRC[6,2]:=R[0];

b:=false;

case progression_type of

1: begin

f1book1.TextRC[7,11]:='Разность'+inttostr(max_dx);

f1book1.TextRC[5,11]:='Арифметическая прогрессия';

repeat

j:=0;

repeat

if P[j]=x+max_dx then begin

x:=x+max_dx;

setlength(R,length(R)+1);

R[high(R)]:=x;

f1book1.NumberRC[6,length(R)+1]:=R[high(R)];

b:=true end

else begin

b:=false;

inc(j) end

until (b=true) or (j=high(P));

until j=high(P) end;

2: begin

f1book1.TextRC[7,11]:='Знаменатель'+inttostr(max_dx);

f1book1.TextRC[5,11]:='Геометрическая прогрессия.';

repeat

j:=0;

repeat

if (P[j]=x*max_dx) and (j<>max_num) then begin

x:=x*max_dx;

setlength(R,length(R)+1);

R[high(R)]:=x;

f1book1.NumberRC[6,length(R)+1]:=R[high(R)];

b:=true end

else begin

b:=false;

inc(j) end

until (b=true) or (j=high(P));

until j=high(P) end

end

end;

P - последовательность;

R - прогрессия;

Progression_type - переменная, определяющая тип прогрессии, которую нужно сформировать. Значение определяется в основной процедуре, в результате сравнения длин самой длинной арифметической и самой длинной геометрической прогрессий. Значению 1 соответствует арифметическая прогрессия, значению 2 соответствует геометрическая прогрессия.

Max_kol - длина самой длинной прогрессии;

Max_num - номер элемента последовательности, являющегося первым элементом самой длинной прогрессии;

Max_dx - разность самой длинной прогрессии;

J - номер элемента последовательности, с которым сравнивается последний найденный член прогрессии;

X - последний найденный член прогрессии;

B - логическая переменная, которая сообщает о том, что найден следующий член прогрессии.

Полный текст программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Menus, AxCtrls, OleCtrls, VCF1, StdCtrls, Math, OleCtnrs,

ExtCtrls, jpeg;

type

Massiv=array of integer;

TForm1 = class(TForm)

MainMenu1: TMainMenu;

Edit1: TEdit;

Label1: TLabel;

F1Book1: TF1Book;

Goooo1: TMenuItem;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

OleContainer1: TOleContainer;

Label2: TLabel;

Image1: TImage;

procedure arithmetic_progression(var P: massiv;

var max_kol, max_num, max_dx: integer);

procedure geometric_progression(var P: massiv;

var max_kol, max_num, max_dx: integer);

procedure formirovanie(var P, R :massiv;

var max_kol, max_num, max_dx, progression_type: integer);

procedure posledovatelnost(var P:massiv);

procedure N1Click(Sender: TObject);

procedure N2Click(Sender: TObject);

procedure N3Click(Sender: TObject);

procedure N4Click(Sender: TObject);

procedure N5Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

////////////////////////////////////////////////////////////////////////////////

{ Определение арифметической прогрессии.}

procedure TForm1.arithmetic_progression(var P: massiv;

var max_kol, max_num, max_dx: integer);

Var i,j,x,dx,kol:integer;

b:boolean;

Begin

for dx:=1 to high(P) do

for i:=0 to high(P) do begin

x:=P[i];

kol:=0;

repeat

j:=0;

repeat

if P[j]=x+dx then begin

inc(kol);

x:=x+dx;

b:=true end

else begin

b:=false;

inc(j) end;

until (b=true) or (j=high(P));

until j=high(P);

if kol>max_kol then begin

max_kol:=kol;

max_num:=i;

max_dx:=dx end end;

end;

////////////////////////////////////////////////////////////////////////////////

{Формирование самой длинной прогрессии.}

procedure TForm1.formirovanie(var P, R: massiv;

var max_kol, max_num, max_dx, progression_type: integer);

var x,j:integer;

b:boolean;

begin

x:=P[max_num];

setlength(R,1);

R[0]:=x;

f1book1.NumberRC[6,2]:=R[0];

b:=false;

case progression_type of

1: begin

f1book1.TextRC[7,11]:='Разность'+inttostr(max_dx);

f1book1.TextRC[5,11]:='Арифметическая прогрессия';

repeat

j:=0;

repeat

if P[j]=x+max_dx then begin

x:=x+max_dx;

setlength(R,length(R)+1);

R[high(R)]:=x;

f1book1.NumberRC[6,length(R)+1]:=R[high(R)];

b:=true end

else begin

b:=false;

inc(j) end

until (b=true) or (j=high(P));

until j=high(P) end;

2: begin

f1book1.TextRC[7,11]:='Знаменатель'+inttostr(max_dx);

f1book1.TextRC[5,11]:='Геометрическая прогрессия.';

repeat

j:=0;

repeat

if (P[j]=x*max_dx) and (j<>max_num) then begin

x:=x*max_dx;

setlength(R,length(R)+1);

R[high(R)]:=x;

f1book1.NumberRC[6,length(R)+1]:=R[high(R)];

b:=true end

else begin

b:=false;

inc(j) end

until (b=true) or (j=high(P));

until j=high(P) end

end

end;

////////////////////////////////////////////////////////////////////////////////

{Определение самой длинной геометрической прогрессии.}

procedure TForm1.geometric_progression(var P:massiv;

var max_kol, max_num, max_dx: integer);

Var i,j,x,dx,kol:integer;

b:boolean;

Begin

for dx:=-high(P) to high(P) do

for i:=0 to high(P) do

if P[i]<>0 then begin

x:=P[i];

kol:=1;

if (dx>1) or (dx<-1) then begin

repeat

j:=0;

repeat

if (P[j]=x*dx) and (j<>i) then begin

inc(kol);

x:=x*dx;

b:=true end

else begin

b:=false;

inc(j) end;

until (b=true) or (j=high(P));

until j=high(P);

if kol>max_kol then begin

max_kol:=kol;

max_num:=i;

max_dx:=dx end end end;

end;

////////////////////////////////////////////////////////////////////////////////

{Формирование самой длинной арифметической прогрессии.}

procedure TForm1.N1Click(Sender: TObject);

var P,R:massiv;

max_kol,max_num,max_dx,i,y,progression_type:integer;

Begin

for i:=1 to 2 do

f1book1.ClearRange(3*i,2,3*i,256,3);

max_kol:=0;

max_num:=0;

max_dx:=0;

Posledovatelnost(P);

arithmetic_progression(P,max_kol,max_num,max_dx);

progression_type:=1;

formirovanie(P,R,max_kol,max_num,max_dx,progression_type)

end;

////////////////////////////////////////////////////////////////////////////////

{Формирование самой длинной геометрической прогрессии.}

procedure TForm1.N2Click(Sender: TObject);

var P,R:massiv;

max_kol,max_num,max_dx,i,y,progression_type:integer;

Begin

for i:=1 to 2 do

f1book1.ClearRange(3*i,2,3*i,256,3);

max_kol:=0;

max_num:=0;

max_dx:=0;

Posledovatelnost(P);

geometric_progression(P,max_kol,max_num,max_dx);

progression_type:=2;

formirovanie(P,R,max_kol,max_num,max_dx,progression_type)

end;

////////////////////////////////////////////////////////////////////////////////

{Формирование самой длинной арифметической или геометрической, в зависимости от случая, прогрессии}

procedure TForm1.N3Click(Sender: TObject);

var P,R:massiv;

max_kol,max_num,max_dx,i,y,progression_type:integer;

Begin

for i:=1 to 2 do

f1book1.ClearRange(3*i,2,3*i,256,3);

max_kol:=0;

max_num:=0;

max_dx:=0;

posledovatelnost(P);

arithmetic_progression(P,max_kol,max_num,max_dx);

y:=max_kol;

geometric_progression(P,max_kol,max_num,max_dx);

if y<max_kol then

progression_type:=2

else

progression_type:=1;

formirovanie(P,R,max_kol,max_num,max_dx,progression_type)

end;

////////////////////////////////////////////////////////////////////////////////

{Очистка результатов.}

procedure TForm1.N4Click(Sender: TObject);

begin

f1book1.ClearRange(3,2,3,256,3);

f1book1.ClearRange(6,2,6,256,3);

f1book1.ClearRange(8,2,10,4,3);

edit1.Clear

end;

////////////////////////////////////////////////////////////////////////////////

{Закрытие программы.}

procedure TForm1.N5Click(Sender: TObject);

begin

form1.Close

end;

////////////////////////////////////////////////////////////////////////////////

{Формирование последовательности.}

procedure TForm1.posledovatelnost(var P: massiv);

var n,i:integer;

b:boolean;

begin

randomize;

if strtoint(edit1.Text)<250 then

n:=strtoint(edit1.Text)

else

n:=250;

setlength(P,n);

for i:=0 to n-1 do begin

P[i]:=random(n+1)-random(n+1);

f1book1.NumberRC[3,i+2]:=P[i] end

end;

////////////////////////////////////////////////////////////////////////////////

end.

Скриншоты

Основной вид программы.

Меню

Найдена арифметическая прогрессия

Найдена геометрическая прогрессия

Заключение

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

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

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

Список литературы

v Фаронов В.В. DELPHI. Программирование на языке высокого уровня. Учебник для вузов. СПб, Питер, 2003.

v Сухарев М. Delphi. Полное руководство. Включая версию 2010. СПб.: Наука и техника, 2010.

v Иванова Г.С. Технология программирования: Учебник для вузов. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002.

v Киммел П. Создание приложений в Delphi. М.: Издат. Дом «Вильямс», 2003.

v Далахвелидзе П.Г., Марков Е.П. Разработка Web-служб средствами Delphi. СПб, БХВ-Петербург, 2003.

Размещено на Allbest.ru