Самый нестандартный алгоритм

← →
VEG © (2003-12-22 02:33) [0]

Самый нестандартный алгоритм решения простой задачи - перевернуть содержимое строки (string).

← →
VEG © (2003-12-22 02:36) [1]

Дополнительное условие - нельзя использовать вспомогательные переменные.

← →
shluz © (2003-12-22 02:37) [2]

Удалено модератором
Примечание: Выражения выбираем

← →
XHelp © (2003-12-22 02:40) [3]

Мой вариант:
procedure TForm1.Button1Click(Sender: TObject);
var
i,t:integer;
s:string;
begin
s:=Edit1.Text;
for i:=1 to (Length(Edit1.Text) div 2) do begin
s[i]:=chr(ord(s[Length(Edit1.Text)+1-i])+ord(s[i]));
s[Length(Edit1.Text)+1-i]:=chr(ord(s[i])-ord(s[Length(Edit1.Text)+1-i]));
s[i]:=chr(ord(s[i])-ord(s[Length(Edit1.Text)+1-i]));
end;
Edit1.Text:=s;
end;

← →
VEG © (2003-12-22 02:42) [4]

>>[3] XHelp © (22.12.03 02:40)
>i,t:integer;
Это ведь вспомогательные переменные...

← →
VEG © (2003-12-22 02:43) [5]

Вот мой вариант:
function StrReverse(sInPut: string): string; var s: string; procedure swap(isn, ien: integer); begin if ien>isn then begin s[isn]:=chr(ord(s[isn]) xor ord(s[ien])); s[ien]:=chr(ord(s[isn]) xor ord(s[ien])); s[isn]:=chr(ord(s[isn]) xor ord(s[ien])); swap(isn+1, ien-1); end; end; begin s:=sInPut; swap(1, Length(s)); StrReverse:=s; end;

← →
XHelp © (2003-12-22 02:47) [6]

isn, ien: integer а это что? новогодний подарок что ли? :)

← →
VEG © (2003-12-22 02:50) [7]

>>XHelp © (22.12.03 02:47) [6]
>isn, ien: integer а это что? новогодний подарок что ли? :)
В чате я тебе говорил, что параметры в функциях можно использовать.

← →
shluz © (2003-12-22 02:52) [8]

> XHelp © (22.12.03 02:47) [6]
> isn, ien: integer а это что? новогодний подарок что ли?
> :)

:))

← →
XHelp © (2003-12-22 03:06) [9]

Хотелось настандартности и без переменных? Получите! :)
Только нормально действует для стринга до 118 символов...
s - глобальный стринг
На форму нужно кинуть 2 таймера (Timer1,Timer2) у обоих 1000 интервал, Timer1.enabled:=true, Timer2.enabled:=false;

procedure TForm1.Timer1Timer(Sender: TObject); begin if FormatDateTime("ss",now) = "00" then begin s:=Edit1.Text; Timer2.Enabled:=true; end; end;

procedure TForm1.Timer2Timer(Sender: TObject); begin s[StrToInt(FormatDateTime("ss",now))]:=chr(ord(s[Length(Edit1.Text)+1-StrToInt(FormatDateTime("ss",now))])+ord(s[StrToIn t(FormatDateTime("ss",now))])); s[Length(Edit1.Text)+1-StrToInt(FormatDateTime("ss",now))]:=chr(ord(s[StrToInt(FormatDateTime("ss",now))])-ord(s[Length( Edit1.Text)+1-StrToInt(FormatDateTime("ss",now))])); s[StrToInt(FormatDateTime("ss",now))]:=chr(ord(s[StrToInt(FormatDateTime("ss",now))])-ord(s[Length(Edit1.Text)+1-StrToIn t(FormatDateTime("ss",now))])); if StrToInt(FormatDateTime("ss",now))>=(Length(s) div 2) then begin Timer1.Enabled:=false; Timer2.Enabled:=false; Edit1.Text:=s; end; end;

Кто скажет что это не нестандартно? :)

← →
SergP © (2003-12-22 03:07) [10]

> VEG © (22.12.03 02:50) [7]
> >>XHelp © (22.12.03 02:47) [6]
> >isn, ien: integer а это что? новогодний подарок что ли?
> :)
> В чате я тебе говорил, что параметры в функциях можно использовать.

А эти твои параметры в функциях - разве не дополнительные переменные? :-)))

← →
int © (2003-12-22 03:11) [11]

мдя.... ещё бы с часами сравнивал .... =)

← →
kaif © (2003-12-22 10:27) [12]

рекурсивная функция, переставляющая p-ый символ с симметричным ему, использующая в качестве буфера последний символ в строке.

procedure _ReverseStr(var s: string; p: integer); begin if p < length(s) then begin s[length(s)] := s[p]; s[p] := s[length(s)- p]; s[length(s) - p] = s[length(s)]; ReverseStr(s, p + 1); end; end; function ReverseStr(const s: string) begin SetLength(s, length(s) + 1); //добавляем 1 дополнительный символ _ReverseStr(s, 1); //вызываем рекурсивную функцию SetLength(s, length(s) - 1); //удаляем 1 дополнительный символ end;
Ни одной новой переменной.
Код не отлаживал, так что извините, может, там есть ошибки...

← →
kaif © (2003-12-22 10:29) [13]

Точно, ошибся. Забыл вернуть значение функции:

function ReverseStr(const s: string) begin SetLength(s, length(s) + 1); //добавляем 1 дополнительный символ _ReverseStr(s, 1); //вызываем рекурсивную функцию SetLength(s, length(s) - 1); //удаляем 1 дополнительный символ Result := s;end;

← →
ИдиотЪ © (2003-12-22 10:31) [14]

вот вы скажите, а нафига это надо ?
мозги чтоли тренируете ?

← →
Евлампия (2003-12-22 10:37) [15]

function InvertString(const s: string): string;
begin
repeat
Result := Result + s[Length(s) - Length(Result)];
until Length(Result) = Length(s);
end;

Просто, не правда ли? :))

← →
kaif © (2003-12-22 10:41) [16]

2 ИдиотЪ © (22.12.03 10:31) [14]
Да черт его знает! Разве человек всегда может объяснить зачем он делает то или иное?
У меня в связи с этой задачей возник, например, интересный вопрос к настоящим Мастерам. Может быть лучше передавать s в процедуру не как string, а как массив? Чтобы память не реаллокировалась при каждом изменении содержимого строки. Или Delphi не реаллокирует память в случае, если длина строки не изменяется? Вот я, например, не знаю. И как будут подсчитываться ссылки на строку при рекурсивном вызове? Ведь компилятор, возможно, не знает, что нас устраивает изменение содержимого строки в очередном экземляре рекурсивного вызова с точки зрения всех остальных экземляров... И у нас может получиться в памяти Length(s) новых строк...
Иногда такие дурацкие задачи заставляют задуматься над более важными вещами...

← →
kaif © (2003-12-22 10:43) [17]

2 Евлампия (22.12.03 10:37) [15]
Гениально просто.

← →
Ega23 © (2003-12-22 10:46) [18]

http://corsair.stu.lipetsk.ru/~X-Meeting/people/programmers.html

Каждый раз умираю со смеху по новой.

← →
Ломброзо © (2003-12-22 10:47) [19]

kaif © (22.12.03 10:41) [16]
Так и делается. В функцию передаётся PChar (указатель на массив символов), а далее происходит только жонглирование положением пары указателей и обмен байтов, на которые эта пара указывает.

← →
Rouse_` (2003-12-22 10:56) [20]

Удалено модератором

← →
Sha © (2003-12-22 11:53) [21]

> VEG © (22.12.03 02:36) [1]
> Дополнительное условие - нельзя использовать вспомогательные переменные.

> VEG © (22.12.03 02:43) [5]
> Вот мой вариант:
> function StrReverse(sInPut: string): string;
> var
> s: string;

А s - это что, по-твоему?

← →
Sha © (2003-12-22 11:56) [22]

> XHelp © (22.12.03 03:06) [9]
> Хотелось настандартности и без переменных? Получите! :)
> Только нормально действует для стринга до 118 символов...
> s - глобальный стринг

Т.е. переменная?

← →
Sha © (2003-12-22 11:59) [23]

> kaif © (22.12.03 10:27) [12]
> рекурсивная функция, переставляющая p-ый символ с симметричным
> ему, использующая в качестве буфера последний символ в строке.
> procedure _ReverseStr(var s: string; p: integer);

Вспомогательные параметры/константы тоже использовать не хотелось бы.

← →
Sha © (2003-12-22 12:02) [24]

> Евлампия (22.12.03 10:37) [15]
> function InvertString(const s: string): string;
> begin
Result:="";
> repeat
> Result := Result + s[Length(s) - Length(Result)];
> until Length(Result) = Length(s);
> end;

Отлично.

← →
Евлампия (2003-12-22 12:03) [25]

> Sha ©

Вот, вот.
Я всегда повторяла, что женщины лучшие программисты.

← →
Евлампия (2003-12-22 12:04) [26]

> Sha © (22.12.03 12:02) [24]
> Result:="";

Это по умолчанию делается.

← →
Sha © (2003-12-22 12:05) [27]

Только While был бы лучще, ведь length(S) может быть нулем...

← →
Sha © (2003-12-22 12:07) [28]

> Евлампия (22.12.03 12:04) [26]
>> Sha © (22.12.03 12:02) [24]
>> Result:="";

> Это по умолчанию делается.

Я бы не утверждал так однозначно. В практике были примеры обратного.

← →
Евлампия (2003-12-22 12:08) [29]

> Sha © (22.12.03 12:05) [27]

Согласна.

function InvertString(const s: string): string; begin while Length(Result) < Length(s) do begin Result := Result + s[Length(s) - Length(Result)]; end end;

← →
Евлампия (2003-12-22 12:10) [30]

> Sha © (22.12.03 12:07) [28]

Ok.

← →
Sha © (2003-12-22 12:47) [31]

> Евлампия (22.12.03 12:10) [30]

Вот пример, который который показывает, что по умолчанию ничего не делатся.

procedure TForm1.Button1Click(Sender: TObject);
var
s: string;
begin
s:=InvertString(Edit1.Text); Edit2.Text:=s;
s:=InvertString(Edit1.Text+"a"); Edit3.Text:=s;
end;

← →
ИдиотЪ © (2003-12-22 13:28) [32]

а использование Result - это не вспомогательно?
ну тогда я ниче не понимаю

← →
Sha © (2003-12-22 13:32) [33]

> ИдиотЪ © (22.12.03 13:28) [32]
> а использование Result - это не вспомогательно?
> ну тогда я ниче не понимаю

Как я понимаю, вспомогательная = дополнительная.

← →
ИдиотЪ © (2003-12-22 13:36) [34]

очень ситуация напоминает переодевание на одной ноге, когда другой уже ступить некуда )

← →
Ega23 © (2003-12-22 13:41) [35]

А самый нестандартный алгоритм = самый извращённый, или <> ?

← →
Sha © (2003-12-22 13:49) [36]

> Ega23 © (22.12.03 13:41) [35]
> А самый нестандартный алгоритм = самый извращённый, или <> ?

Думаю, самый нестандартный алгоритм = самый небыстрый

← →
Ega23 © (2003-12-22 13:50) [37]

> Sha © (22.12.03 13:49) [36]

Ну я, в принципе, так и думал.

← →
Knight © (2003-12-22 14:10) [38]

Получается, что самый простой вариант для string от Евлампии, выглядит так
function InvertString(const s: string): string; begin Result:=""; while Length(Result) < Length(s) do Result := Result + s[Length(s) - Length(Result)]; end;

← →
Sha © (2003-12-22 14:14) [39]

> Knight © (22.12.03 14:10) [38]

Да.

← →
Knight © (2003-12-22 15:14) [40]

Упростите, кто-нибудь это... желательно без TStrArr...
type TStrArr=Array of String; function Explode(Str:String):TStrArr; var i,k,Len:Integer; begin Result:=nil; Len:=Length(Str); if Len>0 then begin k:=1; for i:=2 to Len+1 do begin if (i=Len+1) or (Str[i]=Str[1]) then begin SetLength(Result,Length(Result)+1); Result[High(Result)]:=Copy(Str,k+1,i-k-1); k:=i; end; end; end; end; procedure TForm1.Button1Click(Sender: TObject); var A:TStrArr; i:Integer; begin Memo1.Clear; A:=Explode(false," Имеется переменная String как ее разбить на символы?"); for i:=0 to Length(A)-1 do Memo1.Lines.Append(A[i]); A:=nil; end;

← →
Sha © (2003-12-22 15:18) [41]

Сколько параметров у Explode?

← →
Knight © (2003-12-22 15:42) [42]

>> Sha © (22.12.03 15:18) [41]
> Сколько параметров у Explode?
Можно добавить символ разделителя (у меня он передаётся, как первый символ разбиваемой строки). Остальное не важно, лишь бы работало и без дополнительных типов.

← →
Sha © (2003-12-22 15:50) [43]

> Sha © (22.12.03 15:18) [41]
> Сколько параметров у Explode?

> Knight © (22.12.03 15:42) [42]
> Можно добавить символ разделителя

Похоже, обсуждение будет долгим... :)
Заведи свою ветку.

← →
clickmaker © (2003-12-22 15:54) [44]

SetLength(Result,Length(s));
for i := 1 to Length(s) do Result[(Length(s) - i) + 1] := s[i];

← →
Knight © (2003-12-22 16:17) [45]

>> Sha © (22.12.03 15:50) [43]
Не хотел, ну да ладно... сделал :)

← →
IceBeerg © (2003-12-22 18:25) [46]

Исчо вариант: (всесь кусок приводить небуду, только суть)

asm
...
push Stroka1[num] ...
...
pop Stroka2[num] ...
...
end;

← →
Sha © (2003-12-22 19:38) [47]

> IceBeerg © (22.12.03 18:25) [46]

А num - это переменная или константа?
Если переменная, то так низя,
а если константа, то сколько точно строчек в твоей программе?

>>[9] XHelp © (22.12.03 03:06)
:) Приз за оригинальность! Оригинальнее еще не видел!
>>[12] kaif © (22.12.03 10:27)
Дополнительный буффер для смены местами букв не обязателен. Смотри выше [3] XHelp © (22.12.03 02:40) и [5] VEG © (22.12.03 02:43) - там два метода. Через xor чуть медленнее, чем с буффером, через + медленнее где-то на 15%, чем с xor.
>>[15] Евлампия (22.12.03 10:37)
Конечно, оригинальные решения получились. Но алгоритм может реализовываться не в виже функции, а линейно прямо в основном коде, поэтому в result можно только возвращать можифицированную строку s.
>>All
Придумал самый извращенный метод. Вот генератор этого кода.
const STR_MAX_LENGTH=-2*1024*1024*1024;//2Gb var fOutput: TextFile; iFtd: longint; begin AssignFile(fOutput, "sreverse.inc"); try ReWrite(fOutput); WriteLn(fOutput, "function StrReverse(sInput: string): string;"); WriteLn(fOutput, "var"); WriteLn(fOutput, " s: string;"); WriteLn(fOutput, " begin"); WriteLn(fOutput, " s:=sInput;"); for iFtd:=1 to Abs(STR_MAX_LENGTH) do begin WriteLn(fOutput, " if length(s)-"+IntToStr(iFtd)+"+1>"+IntToStr(iFtd)+" then"); WriteLn(fOutput, " begin"); WriteLn(fOutput, " s["+IntToStr(iFtd)+"]:=chr(ord(s["+IntToStr(iFtd)+"]) xor ord(s[length(s)-"+IntToStr(iFtd)+"+1]));"); WriteLn(fOutput, " s[length(s)-"+IntToStr(iFtd)+"+1]:=chr(ord(s["+IntToStr(iFtd)+"]) xor ord(s[length(s)-"+IntToStr(iFtd)+"+1]));"); WriteLn(fOutput, " s["+IntToStr(iFtd)+"]:=chr(ord(s["+IntToStr(iFtd)+"]) xor ord(s[length(s)-"+IntToStr(iFtd)+"+1]));"); WriteLn(fOutput, " end;"); end; WriteLn(fOutput, " StrReverse:=s;"); WriteLn(fOutput, " end;"); finally CloseFile(fOutput) end; end;
Буду удивлен, если у кого-то хватит места на жестком диске под этот инклюд. Математические подсчеты подсказывают, что он будет весить порядка 500Gb ( 2Gb*211b+106b=494Gb). Хе-хе.

>VEG © (22.12.03 20:01) [48]
var fOutput: TextFile; iFtd: longint;

А как быть с запретом на дополнительные переменные?

>>Sha
Я привел код генерации функции. Саму функцию привести нет возможности... А в генерируемой функции нет никаких лишних переменных.

s:=AnsiReverseString(s);

Ничего невижу..
Ничего неслышу...
Ничего неговорю...

>VEG © (22.12.03 20:01) [48]
WriteLn(fOutput, "var"); WriteLn(fOutput, " s: string;");

Все-таки, как быть с запретом на дополнительные переменные?

procedure Reverse(var S: String); begin SetLength(S, Length(S) + 2); S[Length(S) - 1] := char(0); //S[Length(S)] - для обмена //S[Length(S) - 1] - для цикла while Integer(S[Length(S) - 1]) <= ((Length(S) - 1) div 2) do begin S[Length(S)] := S[Integer(S[Length(S) - 1])]; S[Integer(S[Length(S) - 1])] := S[Length(S) - 1 - Integer(S[Length(S) - 1])]; S[Length(S) - 1 - Integer(S[Length(S) - 1])] := S[Length(S)]; S[Length(S) - 1] := char(Integer(S[Length(S) - 1]) + 1); end; SetLength(S, Length(S) - 2); end;
Правда для коротких строк.

> Igorek © (23.12.03 13:13) [54]

Отлично.

Попробуй реализовать похожую идею для такого объявления
function Reverse(const s: string): string;
и для строк максимальной длины, допустимой компилятором.

> Sha © (23.12.03 13:28) [55]
> Попробуй реализовать похожую идею для такого объявления
> function Reverse(const s: string): string;
> и для строк максимальной длины, допустимой компилятором.

Во-первых такое обьявление не соответствует условию - Result - неявная переменная. Во-вторых уже есть решение от Евлампии.

А если все таки реализовать
procedure Reverse(var S: String);
для больших строк, то возникают нюансы:
- если строка максимально длинная, то ничего больше выкроить мы не сможем
- если нет, то должно оставаться место на символ для обмена и переменную цикла (под нее можно отвести несколько символов (log(256,Length(S))) и делать что-то типа 256^2*(s-2)+256*(s-1)+s ) - уже лень писать

> Igorek © (23.12.03 13:42) [56]

> Во-первых такое обьявление не соответствует условию - Result - неявная переменная

Но не дополнительная :)

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

Ничего выкраивать не надо, можно использовать поле длины строки.
Можно обойтись без символа обмена, как Евлампия.

В качестве иллюстрации, как тебе такой цикл:
while (pinteger(pchar(pointer(Result))[-4]))^>0 do dec((pinteger(pchar(pointer(Result))[-4]))^);

> Igorek © (23.12.03 13:42) [56]

Для случая procedure Reverse(var S: String);
в качестве переменной цикла можно использовать поле счетчика ссылок, а обмен выполнять xor-ом.

Оба полученных решения (и procedure, и function) будут во много раз быстрее решения Евлампии

> VEG © (23.12.03 17:38) [59]
STR_MAX_LENGTH=-2*1024*1024*1024;//2Gb var iFtd: longint; begin ... for iFtd:=1 to Abs(STR_MAX_LENGTH)

Сомнения берут насчет работоспособности цикла...

const STR_MAX_LENGTH=-2*1024*1024*1024;//2Gb var fOutput: TextFile; iFtd: int64 ;
Дальше по тексту...

Не надо переворачивать. За то при чтении можно читать с конца.

> VEG © (22.12.03 20:01) [48]

Еще одно замечание.

Размер твоей проги без ущерба для результата
можно уменьшить ровно в два раза, если сделать

STR_MAX_LENGTH = -1024*1024*1024;

> VEG © (22.12.03 20:01) [48]
> Igorek © (23.12.03 13:13) [54]

Напоследок.

procedure ForIgorek(var s: string); begin; UniqueString(s); if Length(s)>0 then begin; (pinteger(pchar(pointer(s))-8))^:=Length(s) shr 1; while (pinteger(pchar(pointer(s))-8))^>0 do begin; byte(pchar(pointer(s))[(pinteger(pchar(pointer(s))-8))^-1]):= byte(pchar(pointer(s))[(pinteger(pchar(pointer(s))-8))^-1]) xor byte(pchar(pointer(s))[Length(s)-(pinteger(pchar(pointer(s))-8))^]); byte(pchar(pointer(s))[Length(s)-(pinteger(pchar(pointer(s))-8))^]):= byte(pchar(pointer(s))[Length(s)-(pinteger(pchar(pointer(s))-8))^]) xor byte(pchar(pointer(s))[(pinteger(pchar(pointer(s))-8))^-1]); byte(pchar(pointer(s))[(pinteger(pchar(pointer(s))-8))^-1]):= byte(pchar(pointer(s))[(pinteger(pchar(pointer(s))-8))^-1]) xor byte(pchar(pointer(s))[Length(s)-(pinteger(pchar(pointer(s))-8))^]); dec((pinteger(pchar(pointer(s))-8))^); end; (pinteger(pchar(pointer(s))-8))^:=1; end; end;

> Sha © (24.12.03 01:00) [66]
> Напоследок.
>
> procedure ForIgorek(var s: string);
...

Да, серьезно ты занялся этим делом. Поди пол рабочего и пол домашнего дня угробил. :-)))

Самый нестандартный алгоритм Найти похожие ветки