Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Основная";
Текущий архив: 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
8-1088850562
Dominus
2004-07-03 14:29
2004.10.03
Redo в Memo


1-1095244178
Ms.Dunkul
2004-09-15 14:29
2004.10.03
таскание формы 2


6-1088755314
LEONardo
2004-07-02 12:01
2004.10.03
TclientSocket в приложении, не имеющей ни одной формы


8-1088939465
Alex C
2004-07-04 15:11
2004.10.03
видео


1-1095409645
TUser
2004-09-17 12:27
2004.10.03
Delphi < --- > CB





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский