Форум: "Основная";
Текущий архив: 2004.10.03;
Скачать: [xml.tar.bz2];
ВнизНе хватает ресурсов Найти похожие ветки
← →
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] тоже переполнение вызовет.
← →
Alx2 © (2004-09-14 15:16) [25]>resut © (14.09.04 15:15) [24]
С чего ты это взял? :)))
Тем более, без предварительной проверки я код не высылаю.
← →
resut © (2004-09-14 15:22) [26]Точно тебе говорю. Потом скажу почему так делать нельзя.
← →
Alx2 © (2004-09-14 15:24) [27]>resut © (14.09.04 15:22) [26]
Точно то, что ты стебешься.
← →
resut © (2004-09-14 15:32) [28]Нет. Я просто пытаюсь решить возникшую проблему. Думал, может кто-нибудь поможет. Но, наверное, задача быстрого и нетребовательного к ресурсам переворачивания массива слишком специфическая, и с ней мало кто сталкивался.
← →
Vitaly © (2004-09-14 15:51) [29]Ах, вы ещё тут :)
Адмиииииииииииин!
← →
TUser © (2004-09-14 15:52) [30]Ну так проблема-то все еще не решена.
← →
Рамиль © (2004-09-14 15:54) [31]resut © (14.09.04 15:32) [28]
Рамиль © (14.09.04 13:28) [17]
resut © (14.09.04 13:16) [14]
Даже если так.
Неужели трудно прогнать в отладчике?
Если S < E, то рекурсия не закончится!
Какие нафиг ресурсы?! У тебя ошибка в коде!!!
← →
MBo © (2004-09-14 15:54) [32]Быстрый метод "переворачивания" как раз делается с использованием дополнительной памяти - копирование двух последовательных непрерывных кусков памяти несравненно быстрее множества скачков туда-сюда. Рекурсивный метод "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;
← →
Vitaly © (2004-09-14 16:26) [33]
Login: resut
E-mail: resut@mydomain.myzone
Реальное имя: TUser
Город: Москва
Пол: Мужской
Образование: высшее
Увлечения / хобби
self-inversion
Интересное о себе
Вывод: у TUser"а хорошее настроение
← →
MBo © (2004-09-14 16:47) [34]>Vitaly © (14.09.04 16:26) [33]
:))
← →
Master Kolyan (2004-09-14 17:03) [35]>resut © (14.09.04 11:51)[0] >Stack overflow
Нафига в стек лезть - используй память самого массива.
Я думаю проблема не в ресурсах а используемых тобой функциях: запускать функцию из функции!... - причем каждая из них забивает стек, да тут все ясно, измени алгоритм он для больших массивов не пашет.
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2004.10.03;
Скачать: [xml.tar.bz2];
Память: 0.54 MB
Время: 0.044 c