Не хватает ресурсов

← →
resut © (2004-09-14 11:51) [0]

Приветствую Вас, мастера. Возникла такая задача - есть массив (статический, 10 элементов), который состоит из НАЧАЛА и КОНЦА. Надо их поменять местами. Поясню на примере. Если исходно был массив

1 2 3 4 5 6 7 8 9 0

то должно получиться

7 8 9 0 1 2 3 4 5 6

Я знаю, что для этого надо сначала перевернуть НАЧАЛО, потом перевернуть КОНЕЦ, а потом перевернуть весь массив целиком. Поэтому возникла необходимость реализовать процедуру переворачивания массива или его части.
Вот тут меня поджидала проблема. Я решил действовать правильно, пошел в библиотеку, там оказалась книга Вирта, а в ней определение того, что есть массив. Смысл в том, что массив - это либо пустой массив, либо конкатенация более короткого массива с одним дополнительным элементом. Мне это определение понравилось и я решил при решении данной задачи руководствоваться именно им.
Из этого определения следует очевидное решение - для того, чтобы перевернуть массив или его часть надо перевернуть всю эту часть за исключением последнего элемента, а потом поменять их местами. Большая удача состояла в том, что задача поменять их местами - это по сути исходная задача. Т.е. получается очень несложная на первый взгляд рекурсия. Задача упрощается тем, что одна из этих частей состоит всего из одного элемента - ее можно даже не переворачивать! Короче, я обрадовался, что все оказывается так просто и написал такой код

var Ar:array[0..9] of integer;
procedure Swap(S,M,E:integer);

implementation

procedure Inverse(S,E:integer);
begin
if S > E then
begin
Inverse(S,E-1);
Swap(S,E-1,E);
end;
end;

procedure Swap(S,M,E:integer);
begin
Inverse(S,M);
Inverse(M+1,E);
Inverse(S,E);
end;

Проблема в том, что на доступном мне компьютере существенно не хватает ресурсов для выполнения этой задачи. Точнее - программа вроде бы работает минут десять, наверное даже почти все успевает сделать, но в самый неподходящий момент выдает Stack overflow.
В связи с этим у меня вопрос - может быть есть где-нибудь в интеренете бесплатные сервера, созданные для помощи в решении таких вопросов? Ну, чтобы туда отправить свою задачу - и там бы она решалась.

← →
Poirot © (2004-09-14 11:53) [1]

Избавься от рекурсивного вызова.. должно помочь.. он много ресурсов жрёт, но работает быстро:) решать тебе:)))

← →
Digitman © (2004-09-14 11:58) [2]

> массив - это либо пустой массив, либо конкатенация более
> короткого массива с одним дополнительным элементом

массив - это .. массив ?
расчудесное "определение" !

бред какой-то ...

> Stack overflow

ты попал в бесконечную рекурсию, при каждой очередной рекурсионной "итерации" стек уменьшается как минимум на 4 байта, а стек трэда - не резиновый, он имеет min и max пределы

← →
resut © (2004-09-14 12:01) [3]

Странно, что получается бесконечная рекурсия. Ведь все сделано вроде бы по науке. А определение действительно рекурсивное, в том его достоинство.

← →
Erik1 © (2004-09-14 12:06) [4]

А что мешает использовать цикл и второй масив?

← →
Digitman © (2004-09-14 12:09) [5]

> resut © (14.09.04 12:01) [3]

но массив-то не бесконечен ! всего-то 10 элементов в дан.примере ! следовательно, и глубина рекурсии конечна ... а если у тебя рекурсия получилась бесконечной, значит, ты допускаешь какую-то ошибку в алгоритме рекурс.вызова ... и эта ошибка как раз и вызывает упомянутую проблему

← →
Юрий Зотов © (2004-09-14 12:09) [6]

> resut © (14.09.04 12:01) [3]

<массив> ::= <пусто> | <массив> <элемент массива>

Это, можно сказать, классика (Вирт есть Вирт). Определение действительно рекурсивное, но не бесконечно рекурсивное.

В отличие от его реализации. :о)

← →
DiamondShark © (2004-09-14 12:26) [7]

> var Ar:array[0..9] of integer;
> procedure Swap(S,M,E:integer);
>
> implementation
>
> procedure Inverse(S,E:integer);
> begin
> if S > E then
> begin
> Inverse(S,E-1);
> Swap(S,E-1,E);
> end;
> end;
>
> procedure Swap(S,M,E:integer);
> begin
> Inverse(S,M);
> Inverse(M+1,E);
> Inverse(S,E);
> end;

А где в этом коде собственно операция с массивом?

← →
Рамиль © (2004-09-14 12:29) [8]

resut © (14.09.04 11:51)
if S > E then begin Inverse(S,E-1); Swap(S,E-1,E); end; end;
А как у тебя S может стать <= E ?

← →
resut © (2004-09-14 12:33) [9]

2 Рамиль © (14.09.04 12:29) [8]
При вызове Inverse E уменьшается на единицу. Когда-то он станет равным S.

А собственно операцию с массивом надо бедет дописать. Тут вы правы, этот момент я упустил из виду.

← →
Рамиль © (2004-09-14 12:40) [10]

resut © (14.09.04 12:33) [9]
Это.. Может я не правильно понял..
Но если хоть раз выполнится условие
S > E
то в дальнейшем при вызове
Inverse(S,E-1);
E будет уменьшаться и условие S > E будет всегда выполняться.
По моему ты не совсем понимаешь, что такое рекурсия..

← →
Alx2 © (2004-09-14 13:05) [11]

>resut © (14.09.04 11:51)

Вот три варианта ивертирования массива.
Два первых - рекурсивные.
Но рекурсию для этого дела использовать - из пушки по воробьям.
procedure TForm1.Button2Click(Sender: TObject); Type TArray = array [1..10] of integer; Var Arr : TArray; procedure Inverse1(idx, el : Integer); begin if idx<10 then Inverse(idx+1,Arr[idx+1]); Arr[11-idx] := el; end; procedure Swap(idx1,idx2 : integer); Var tmp : integer; begin tmp := Arr[idx1]; Arr[idx1] := Arr[idx2]; Arr[idx2] := tmp; end; procedure Inverse2(Start,Stop : Integer); begin if Start>=Stop then exit; Inverse2(Start+1,Stop-1); swap(Start,Stop); end; procedure Inverse3(Start,Stop : Integer); Var k : integer; begin for k := Start to (Start + Stop) div 2 do Swap(k,Stop-k+Start); end; Var k : Integer; begin for k := 1 to 10 do Arr[k] := k; Inverse3(1,10); end;

← →
Alx2 © (2004-09-14 13:06) [12]

Блин, сорри. Невнимательно пост прочел. Так что мой пост Alx2 © (14.09.04 13:05) [11] попал в молоко :(

← →
Alx2 © (2004-09-14 13:14) [13]

но если следовать приведенному в топике алгоритму, то так:
procedure Inverse4(Start,Stop : Integer); begin Inverse3(Start,(Start+Stop) div 2); Inverse3((Start+Stop) div 2 + 1,Stop); Inverse3(Start,Stop); end;

← →
resut © (2004-09-14 13:16) [14]

> Рамиль © (14.09.04 12:40) [10]

Извините, конечно
if S < E then
begin
...

А насчет бесконечной рекурсии - ее не должно быть, т.к. на определенной стадии вызовы Inverse прекратятся, т.к. это условие выполнено не будет. Я думаю, что дело все-таки в нехватке ресурсов у компьютера (PIII, ОЗУ256). Как все-таки с интернетом - есть ли где-нибудь сервер, способный решить данную задачу?

← →
Alx2 © (2004-09-14 13:18) [15]

>resut © (14.09.04 13:16) [14]

Издеваешься :)))

← →
resut © (2004-09-14 13:23) [16]

Да нет. Правда надо такую задачу решить.

← →
Рамиль © (2004-09-14 13:28) [17]

resut © (14.09.04 13:16) [14]
Даже если так.
Неужели трудно прогнать в отладчике?
Если S < E, то рекурсия не закончится!

← →
SergP. (2004-09-14 14:41) [18]

> Приветствую Вас, мастера. Возникла такая задача - есть массив
> (статический, 10 элементов), который состоит из НАЧАЛА и
> КОНЦА. Надо их поменять местами. Поясню на примере. Если
> исходно был массив
>
> 1 2 3 4 5 6 7 8 9 0
>
> то должно получиться
>
> 7 8 9 0 1 2 3 4 5 6
>
> Я знаю, что для этого надо сначала перевернуть НАЧАЛО, потом
> перевернуть КОНЕЦ, а потом перевернуть весь массив целиком.
> Поэтому возникла необходимость реализовать процедуру переворачивания
> массива или его части.

А не проще ли создать еще один массив и перенести начало и конец из исходного в новый двумя move"ами???

← →
SergP. (2004-09-14 14:44) [19]

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

← →
Vitaly © (2004-09-14 14:54) [20]

> Издеваешься :)))

Однозначно :). В "Потрепаться".

← →
resut © (2004-09-14 15:01) [21]

Я не хочу в Потрепатсья. Мы тут серьезные вещи обсуждаем.

А по поводу [18] и [19] - вы однозначно не правы, никакие move и дополнительное использование памяти для таких вещей не нужно. Надо выбирать самый оптимальный алгоритм.

← →
begin...end © (2004-09-14 15:06) [22]

Да. Мы тут обсуждаем серьёзные вещи.

Например, может ли рекурсия глубиной якобы порядка 10 шагов работать десять минут.

Вообще, может, конечно. Но в данном случае...

← →
Alx2 © (2004-09-14 15:06) [23]

>resut © (14.09.04 15:01) [21]
а что не нравится в посте Alx2 © (14.09.04 13:14) [13] ?

← →
resut © (2004-09-14 15:15) [24]

А [13] тоже переполнение вызовет.

Точно тебе говорю. Потом скажу почему так делать нельзя.

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

Ах, вы ещё тут :)
Адмиииииииииииин!

Ну так проблема-то все еще не решена.

resut © (14.09.04 15:32) [28]

Рамиль © (14.09.04 13:28) [17]
resut © (14.09.04 13:16) [14]
Даже если так.
Неужели трудно прогнать в отладчике?
Если S < E, то рекурсия не закончится!

Какие нафиг ресурсы?! У тебя ошибка в коде!!!

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

procedure SwapBytes(p:PByteArray; a,b:Integer); var t:Byte; begin t:=p[a]; p[a]:=p[b]; p[b]:=t; end; procedure SwapStartEnd(p:PByteArray; n,len:Integer); var i,r:Integer; begin if (n<=0) or (n>=len) then Exit; r:=len-n; if n>=r then begin for i:=0 to r-1 do SwapBytes(p,i,n+i); SwapStartEnd(@p[r],n-r,n); end else begin for i:=0 to n-1 do SwapBytes(p,i,n+i); SwapStartEnd(@p[n],n,r); end; end; procedure TForm1.Button2Click(Sender: TObject); var s:string; begin s:="1234567"; SwapStartEnd(@s[1],3,Length(s)); Caption:=s; end;

Login: resut E-mail: resut@mydomain.myzone Реальное имя: TUser Город: Москва Пол: Мужской Образование: высшее Увлечения / хобби self-inversion Интересное о себе

Вывод: у TUser"а хорошее настроение

← →
Master Kolyan (2004-09-14 17:03) [35]

>resut © (14.09.04 11:51)[0] >Stack overflow
Нафига в стек лезть - используй память самого массива.
Я думаю проблема не в ресурсах а используемых тобой функциях: запускать функцию из функции!... - причем каждая из них забивает стек, да тут все ясно, измени алгоритм он для больших массивов не пашет.

Не хватает ресурсов Найти похожие ветки