Эффективность алгоритма... А Ты сможешь лучше??

← →
Unknowing (2005-12-28 16:21) [0]

Уважаемые профессионалы!!! Учусь программировать, решаю типовые задачи, а ответить на мои вопросы некому :( Правильно ли составлена логика работы процедуры или можно эффективней??
Процедура возвращает:
- кол-во букв в самом большом слове строки
- в самом маленьком
- кол-во слов в строке.
Вот код:
Procedure Parse(Str: String; var Sl: Integer; var Max: Integer; var Min: Integer); var N : Integer; Ch_C, Ch : Integer; Flag : Boolean; begin N:=1; Sl:=0; Max:=0; Min:=0; Flag:=False; if Str<>"" then while N<>Length(Str)+1 do begin if (Str[N]<>" ") and (Flag=False) then begin Sl:=Sl+1; Flag:=True; Ch_C:=N; Ch:=0; while ((Ch_C<>Length(Str)+1) and (Str[Ch_C]<>" ")) do begin Ch:=Ch+1; Ch_C:=Ch_C+1; end; if Sl=1 then Min:=Ch; if Ch>Max then Max:=Ch; if Ch<=Min then Min:=Ch; end else if Str[N]=" " then Flag:=False; N:=N+1; end else Writeln("Нет ни одного слова!"); end;

← →
Курдль © (2005-12-28 16:28) [1]

Чтобы оценить правильность логики работы процедуры самому или попросить ее оценить других - надо не код присылать, а блок-схему алгоритма вывешивать.
Дай ссылку на свою блок-схему!

← →
ferr © (2005-12-28 16:31) [2]

левое полушарие, правый нейрон на третьей секции снизу)

← →
Ega23 © (2005-12-28 16:31) [3]

В предложении "Стой, собака!" сколько символов в самом длинном слове?

← →
Unknowing (2005-12-28 16:33) [4]

Уф!! Блок схему создавать лениво, а логику делаю на словах.
Опытным глазом так сразу оценить нельзя?

← →
Игорь Шевченко © (2005-12-28 16:33) [5]

> Опытным глазом так сразу оценить нельзя?

Для опытного глаза слишком непонятный код

← →
Unknowing (2005-12-28 16:35) [6]

> Ega23 © (28.12.05 16:31) [3]

Слова здесь все что между пробелами!! Задача посчитать стоимость телеграммы, которая считается из перечисленных параметров.

← →
ferr © (2005-12-28 16:35) [7]

вот такие вещи не почитаемы
(Flag=False)

сионисты вот на такие вещи любят набрасываться
Sl:=Sl+1;

← →
Ega23 © (2005-12-28 16:37) [8]

Рекомендую обратить внимание на функции Copy, ExtractDelimited ичто-то ещё. Сейчас вспомню.
А, ещё Trim.

← →
Unknowing (2005-12-28 16:38) [9]

Здесь Flag определяет было ли вхождение "пробела"/

> ferr © (28.12.05 16:35) [7]

А почему эти сионисты такого не любят?

← →
Джо © (2005-12-28 16:39) [10]

> [9] Unknowing (28.12.05 16:38)
> Здесь Flag определяет было ли вхождение "пробела"/

not Flag

> А почему эти сионисты такого не любят?

Потому что каждый раз происходит реаллокация памяти под строку.

← →
Ega23 © (2005-12-28 16:40) [11]

> Здесь Flag определяет было ли вхождение "пробела"/

Речь идёт о том, что вместо
if (Flag=False)
обычно пишут
if not Flag

А сионисты не любят потому, что в С есть ++

← →
Unknowing (2005-12-28 16:41) [12]

> Ega23 © (28.12.05 16:37) [8]

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

← →
Джо © (2005-12-28 16:41) [13]

> Потому что каждый раз происходит реаллокация памяти под
> строку.

Тьфу, не так прочитал. В данном случае красивше и понятнее Inc (S1).
П.С. Названия переменных ужасны, голова болит от такого.

← →
ferr © (2005-12-28 16:42) [14]

А сионисты не любят потому, что в С есть ++))
звучит!

← →
Lexer © (2005-12-28 16:43) [15]

а почему функция pos не катит?

← →
ferr © (2005-12-28 16:43) [16]

а что искать?

← →
MBo © (2005-12-28 16:44) [17]

Используй TStrings.CommaText - код сильно упростится

← →
Unknowing (2005-12-28 16:44) [18]

> Джо © (28.12.05 16:41) [13]

Да, правда! :) Болит даже у меня. Но тем не менее, так ли всё с точки зрения эффективности решения??

← →
Ega23 © (2005-12-28 16:45) [19]

> Задача все сделать без применения готовых функций, так сказать,
>
> на низком уровне..
>

Как ты тогда объяснишь применение функции Length ?

← →
Igorek © (2005-12-28 16:46) [20]

> Unknowing (28.12.05 16:21)
Ужас. Учи конечные автоматы.

← →
Курдль © (2005-12-28 16:46) [21]

> Опытным глазом так сразу оценить нельзя?

Можно! .... [censored] на [censored], мать ![censored] :[censored], а не код!

← →
Unknowing (2005-12-28 16:46) [22]

> MBo © (28.12.05 16:44) [17]

Да нет! Опять же: я решаю как бы на "низком уровне". Т.е. ни о каких классах и слыхать не слыхивал.

← →
Unknowing (2005-12-28 16:49) [23]

> Курдль © (28.12.05 16:46) [21]

Спасибо, конечно, но думаю что censored можно назвать учителя который не учит, а показывает свою крутость перед учеником!!
Больше от Вас ответов не требую. Еще раз спасибо!

← →
Джо © (2005-12-28 16:51) [24]

> [23] Unknowing (28.12.05 16:49)

Дык ведь указывают на ошибки, пока не видел, чтобы хоть одну исправил.

← →
Igorek © (2005-12-28 16:52) [25]

>
> Unknowing (28.12.05 16:49) [23]
> Спасибо, конечно, но думаю что censored можно назвать учителя
> который не учит, а показывает свою крутость перед учеником!

А также ученика, который в каждом предложении усматривает меряние во крутости. :)

← →
Unknowing (2005-12-28 16:53) [26]

> Джо © (28.12.05 16:51) [24]

Стараюсь на критику реагировать правильно! Но всё же: меня интересует больше не удобочтаемость, а эффективность!.

← →
Курдль © (2005-12-28 16:54) [27]

> Unknowing (28.12.05 16:49) [23]

Последний раз уж отвечу. (Я сёдня добрый :)

Хотел я поведать, как надо создавать процедуры... Про метод последовательной детализации от самого Паскаля, про некоторые приемы оптимизации от Вирта...

Но если Вы из тех вундеркиндов, что пишут код без схемы, проектируют базы без модели, то вряд ли Вам нужна чья-то помощь.

Однако и в серьезную компанию Вас на работу не возьмут, пока не научитесь.

← →
ferr © (2005-12-28 16:55) [28]

Курдль © (28.12.05 16:54) [27]

тут достаточно простой автомат, схема и в голове уместится.

← →
Чародей © (2005-12-28 16:56) [29]

> Unknowing (28.12.05 16:21)

> Правильно ли составлена логика работы процедуры или можно
> эффективней??

Если процедура работает правильно то логика не может быть не праыильной. А эффективнее можно сделать всегда (правда после некоторого рубежа это становится не рационально). Можно Length(Str)+1 вычислить один раз до цикла, в конце концовможно обойтись одним циклом вместо двух.

← →
Джо © (2005-12-28 16:56) [30]

> [26] Unknowing (28.12.05 16:53)
>
> > Джо © (28.12.05 16:51) [24]
>
> Стараюсь на критику реагировать правильно! Но всё же: меня
> интересует больше не удобочтаемость, а эффективность!.

А вряд-ли кто-то возьмется забесплатно оценивать непонятно какую "эффективность" плохо написанного и неотформатированного кода. Обычно расценивают как неуважение, со всеми вытекающими.

Вот самый банальный пример. Использование название переменной Sl — очень дурной тон. Потому, что маленькая "l" почти не отличима от "1" во многих моноширинных шрифтах.

← →
Курдль © (2005-12-28 16:58) [31]

> ferr © (28.12.05 16:55) [28]
> тут достаточно простой автомат, схема и в голове уместится.

Я среагировал не на конкретную процедуру, а на исходный пост автора:

> Уважаемые профессионалы!!! Учусь программировать, решаю
> типовые задачи, а ответить на мои вопросы некому :(

Если автор учится программировать, ему бы начать не с кодинга, а с алгоритминга :)

← →
Gero © (2005-12-28 16:59) [32]

> Эффективность алгоритма

По каким критериям оценивать эффективность?

> А Ты сможешь лучше??

Это, что, лозунг?

← →
Unknowing (2005-12-28 16:59) [33]

> Курдль © (28.12.05 16:54) [27]

Спасибо! Я не претендую на звание вундеркинда и уже работаю. Просто решил несколько автоматизировать свою работу... Конечно чтобы написать процедуру я создал нечто вроде блок-схемы, но в виде простых предложений. Собственно, изложил подход на листе фразами.

← →
Курдль © (2005-12-28 16:59) [34]

> Unknowing (28.12.05 16:53) [26]
> меня интересует больше не удобочтаемость, а эффективность!.

Пиши на Аssembler-е!

← →
Unknowing (2005-12-28 17:03) [35]

> Чародей © (28.12.05 16:56) [29]

А вот про один цикл вместо двух это уже интересней!! Но у меня голова не варит как это можно сделать.
И что правильней вводить дополнительную переменную и каждый раз считать в цикле Length(S)+1

← →
Lexer © (2005-12-28 17:09) [36]

Unknowing, так почему ты всё-таки решил считывать каждый символ, скорость функции pos не устраивает?
iEndW = Pos(" ", Str)
можно сделать один цикл с постоянным уменьшением строки...
?

← →
ferr © (2005-12-28 17:09) [37]

эээээ

← →
Ega23 © (2005-12-28 17:11) [38]

> А вот про один цикл вместо двух это уже интересней!! Но
> у меня голова не варит как это можно сделать.
> И что правильней вводить дополнительную переменную и каждый
> раз считать в цикле Length(S)+1

Ну то, что один цикл - это и ежу понятно.
Просто один проход по исходной строке, этого вполне достаточно.

← →
Digitman © (2005-12-28 17:18) [39]

Удалено модератором
Примечание: Следи за словарем

← →
MBo © (2005-12-28 17:18) [40]

procedure ParseString(const s:string; var Longest, Shortest, NumWords:Integer); const Delimiters = [" ",",","."]; var i, CurrLen, LastDelim:Integer; StateInWord: Boolean; procedure EndOfWord; begin CurrLen:=i-LastDelim; if CurrLen>Longest then Longest:=CurrLen; if CurrLen<Shortest then Shortest:=CurrLen; Inc(NumWords); StateInWord := False; end; procedure StartWord; begin LastDelim:=i; StateInWord:=True; end; begin Longest:=0; Shortest:=MaxInt; LastDelim:=0; NumWords:=0; StateInWord:=False; for i := 1 to Length(s) do if (s[i] in Delimiters) then begin if StateInWord then EndOfWord end else if not StateInWord then StartWord; if StateInWord then EndOfWord; if NumWords=0 then Shortest:=0; end;

← →
Джо © (2005-12-28 17:21) [41]

> [40] MBo © (28.12.05 17:18)

Красиво.

← →
Игорь Шевченко © (2005-12-28 17:25) [42]

procedure StringStats (const S: string; var WordCount, MinWordSize, MaxWordSize: Integer); var P, PStartWord: PChar; MinLength, MaxLength, CurrentLength: Integer; begin WordCount := 0; MinWordSize := 0; MaxWordSize := 0; MinLength := Length(S) + 1; MaxLength := 0; P := PChar(S); while P^ = " " do Inc(P); while P^ <> #0 do begin Inc(WordCount); PStartWord := P; while P^ > " " do Inc(P); CurrentLength := P - PStartWord; if CurrentLength < MinLength then begin MinWordSize := CurrentLength; MinLength := CurrentLength; end; if CurrentLength > MaxLength then begin MaxWordSize := CurrentLength; MaxLength := CurrentLength; end; while P^ = " " do Inc(P); end; end;

← →
MBo © (2005-12-28 17:31) [43]

Более краткая форма с подчеркнутой "конечноавтоматностью":

procedure ParseString2(const s:string; var Longest, Shortest, NumWords:Integer); const Delimiters = [" ",",","."]; var i, CurrLen, LastDelim:Integer; StateInWord: Boolean; procedure ChangeState; begin if StateInWord then begin CurrLen:=i-LastDelim; if CurrLen>Longest then Longest:=CurrLen; if CurrLen<Shortest then Shortest:=CurrLen; Inc(NumWords); end else LastDelim:=i; StateInWord := not StateInWord; end; begin Longest:=0; Shortest:=MaxInt; LastDelim:=0; NumWords:=0; StateInWord:=False; for i := 1 to Length(s) do if (not (s[i] in Delimiters)) xor StateInWord then ChangeState; if StateInWord then ChangeState; if NumWords=0 then Shortest:=0; end;

← →
Игорь Шевченко © (2005-12-28 17:34) [44]

MBo © (28.12.05 17:31) [43]

> if (not (s[i] in Delimiters)) xor StateInWord then

Ты меня, конечно, извини, но эта строка нечитабельна :)

← →
MBo © (2005-12-28 17:39) [45]

>Игорь Шевченко © (28.12.05 17:34) [44]
>Ты меня, конечно, извини, но эта строка нечитабельна :)

Осознавая это, я сначала и дал развернутую версию ;))

← →
DErad (2005-12-28 17:44) [46]

> Спасибо! Я не претендую на звание вундеркинда и уже работаю.
> Просто решил несколько автоматизировать свою работу...
> Конечно чтобы написать процедуру я создал нечто вроде блок-
> схемы, но в виде простых предложений. Собственно, изложил
> подход на листе фразами.

А тебе лет сколько? если можно узнать!!!

← →
Курдль © (2005-12-28 17:51) [47]

> Игорь Шевченко © (28.12.05 17:25) [42]

Не мытьем, так катаньем аутор научился писать оптимальные процедуры! Вот его терь на работе похвалють! :)

← →
OldNaum © (2005-12-28 18:02) [48]

MBo © (28.12.05 17:31) [43]
красиво, блин.

← →
Vlad433 © (2005-12-28 18:22) [49]

procedure StringStats (S: string; var WCount, MinWord, MaxWord: Integer);
var
P:Char; MinLength, MaxLength, i, CurLength: Integer;
begin
WCount:=0; MinWord:=1000000;MaxWord:=0;CurLength:=0;
for i:=1 to Length(S)+1 do
begin
P:=S[i];
if P in [" ",#0] then if CurLength=0 then continue else
begin
if CurLength<MinWord then MinWord:=CurLength;
if CurLength>MaxWord then MaxWord:=CurLength;
CurLength:=0; Inc(WCount);
end else Inc(CurLength);
end;
end;

← →
Sha © (2005-12-28 19:54) [50]

procedure TelegramStatistics(s: string; var wordcount, minlen, maxlen: integer); const characters= ["0".."9","A".."Z","a".."z","А".."Я","Ё","ё","а".."я"]; var i, len: integer; begin; wordcount:=0; minlen:=MaxInt; maxlen:=0; len:=0; if s<>"" then for i:=1 to Length(s)+1 do if s[i] in characters then inc(len) else if len>0 then begin; inc(wordcount); if minlen>len then minlen:=len; if maxlen<len then maxlen:=len; len:=0; end; end;

← →
Verg © (2005-12-28 20:09) [51]

> Игорь Шевченко © (28.12.05 17:34) [44]
> MBo © (28.12.05 17:31) [43]
>
>
> > if (not (s[i] in Delimiters)) xor StateInWord then
>
>
> Ты меня, конечно, извини, но эта строка нечитабельна :)

Хм, чем же?

← →
Verg © (2005-12-28 20:30) [52]

Ах да, с т.з. логики, xor следовало бы заменить на <>
Было бы очевиднее ? Т.е. "читабельнее"?

← →
pasha_golub © (2005-12-28 20:32) [53]

> Verg © (28.12.05 20:09) [51]
>
>

if (not (s[i] in Delimiters) and not StateInWord) or ((s[i] in Delimiters) and StateInWord) then...

Потому шо надо было так ;0))

PS Части разделенные OR можно было писать без скобок, но ради наглядности всегда пишу так...

← →
Sha © (2005-12-28 20:33) [54]

> Verg © (28.12.05 20:30) [52]

Еще читабельнее
if StateInWord=(s[i] in Delimiters) then

← →
Verg © (2005-12-28 20:38) [55]

> pasha_golub © (28.12.05 20:32) [53]

Это вообще ф топку.

← →
pasha_golub © (2005-12-28 20:40) [56]

> Verg © (28.12.05 20:38) [55]

Господе, все такие сурьезные...
Гоню я... По правилу какому-то преобразовал, да и все...

Что наша жизнь? Игра! (с) Пиковая дама, по-моему

;0)

← →
Verg © (2005-12-28 20:46) [57]

> Что наша жизнь? Игра! (с) Пиковая дама, по-моему

http://lain.ru/trash/curveball.swf

← →
pasha_golub © (2005-12-28 20:48) [58]

> Verg © (28.12.05 20:46) [57]

КЛАСС!!! Блин, а я ссылку на нее потерял в свое время. Огромное спасибо, чессслово.

← →
Verg © (2005-12-28 20:50) [59]

В догонку...

http://lain.ru/trash/curveball.swf
http://yonkis.com/mediaflash/yeti_gore.htm

← →
pasha_golub © (2005-12-28 20:55) [60]

> http://yonkis.com/mediaflash/yeti_gore.htm

Оригинальный вариант, интересней, ИМХО.

← →
OldNaum © (2005-12-28 21:03) [61]

<offtop>
блин, ну не даром Sha на FastProject"e рулит :D

кстати, выигрывал когда-нибудь в итоге? интересно, просто ) я щас частенько туда заглядываю. интересная все-таки штука. щас в инете все чаще можно встретить пакеты компонентов на базе FP.
</offtop>

← →
Verg © (2005-12-28 21:11) [62]

> pasha_golub © (28.12.05 20:55) [60]
>
> > http://yonkis.com/mediaflash/yeti_gore.htm
>
>
> Оригинальный вариант, интересней, ИМХО.

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

← →
MBo © (2005-12-28 22:20) [63]

>Verg © (28.12.05 20:09) [51]
> > if (not (s[i] in Delimiters)) xor StateInWord then
> Ты меня, конечно, извини, но эта строка нечитабельна :)
>Хм, чем же?

Ну загнул я там, конечно... ;)
Стоило сделать так:
if (s[i] in Delimiters) <> StateInWord then

← →
Sha © (2005-12-28 22:32) [64]

> OldNaum © (28.12.05 21:03) [61]
> выигрывал когда-нибудь в итоге? интересно, просто )

в некоторых номинациях :)

← →
Verg © (2005-12-28 22:34) [65]

> MBo © (28.12.05 22:20) [63]

Нормально все. :)

Делай как хочешь - МЫ - разрешаем :))))))))))))))

← →
MasterPaleva © (2005-12-29 05:23) [66]

Я так понял, что нужно сделать без использования функций и процедур, чтобы повысить эффективность алгоритма. Не считая length :)

var i, j, slov,n, n2: integer; str: string; ... slov:=0; j:=0; n:=0; n2:=length(str); for i:=1 to length(str) do begin if str[i]=" " then begin inc(slov); j:=i-j-1; if j>n then n:=j; if j<n2 then n2:=j; end; end;

В работе не проверял, щас Делфи не стоит. Вроде быстрее...

← →
vidiv © (2005-12-29 06:22) [67]

$data = "Стой, собака моя!"; preg_match_all("/[A-Za-zА-Яа-я]+/s", $data, $out); if (count($out[0])) { $minlen = strlen($out[0][0]); $maxlen = strlen($out[0][0]); for ($i=1; $i<count($out[0]); $i++) { if (strlen($out[0][$i])<$minlen) $minlen = strlen($out[0][$i]); if (strlen($out[0][$i])>$maxlen) $maxlen = strlen($out[0][$i]); } echo "Длина самого короткого слова: ".$minlen."<br>"; echo "Длина самого длинного слова: ".$maxlen."<br>"; echo "Количество слов: ".count($out[0]); }else{ echo "Слов нет"; }

← →
MasterPaleva © (2005-12-29 07:09) [68]

Unknowing (28.12.05 16:21)

Да, твой алгоритм не учитывает же ведь точки, запятые, двоеточия...
Придется еще массив создавать.

← →
з. танька (2005-12-29 07:14) [69]

> MasterPaleva © (29.12.05 05:23) [66]

неправильно.. :(

← →
Unknowing (2005-12-29 09:08) [70]

Так, вроде, лучше... Но уже боюсь реакции :)

Procedure Parse(Str: String; var WordCount,MaxWord,MinWord: Integer); var PosAtString : Integer; PosAtWord, NumOfLetters, LengthOfStr : Integer; Flag : Boolean; begin PosAtString:=1; WordCount:=0; MaxWord:=0; MinWord:=0; LengthOfStr:=Length(Str)+1; Flag:=False; if Str<>"" then while PosAtString<>LengthOfStr do begin if (Str[PosAtString]<>" ") and (not Flag) then begin Inc(WordCount); Flag:=True; PosAtWord:=PosAtString; NumOfLetters:=0; while ((PosAtWord<>LengthOfStr) and (Str[PosAtWord]<>" ")) do begin Inc(NumOfLetters); Inc(PosAtWord); end; if WordCount=1 then MinWord:=NumOfLetters; if NumOfLetters>MaxWord then MaxWord:=NumOfLetters; if NumOfLetters<=MinWord then MinWord:=NumOfLetters; end else if Str[PosAtString]=" " then Flag:=False; Inc(PosAtString); end else Writeln("Нет ни одного слова"); end;

← →
Unknowing (2005-12-29 09:26) [71]

Огромное спасибо всем отозвавшимся!!!
Действительно можно лучше, понятьней и короче! Будем работать над собой :)
С Новым Годом!!!

← →
Ega23 © (2005-12-29 10:24) [72]

MBo © (28.12.05 17:18) [40]
procedure ParseString(const s:string; var Longest, Shortest, NumWords:Integer);
const
Delimiters = [" ",",","."];

Не прокатит, если в предложении прямая речь. Или диалог.

:-)

← →
MBo © (2005-12-29 10:30) [73]

>Ega23 © (29.12.05 10:24) [72]
>Не прокатит, если в предложении прямая речь. Или диалог.
Ну это уже от ТЗ зависит :) Возможно, лучше, как у Sha, не ограничители, а наоборот, допустимые в "словах" символы проверять

← →
Ega23 © (2005-12-29 10:32) [74]

> Ну это уже от ТЗ зависит :)

Согласен.
Просто не удержался код мастера покритиковать. :о)

> MBo © (29.12.05 10:30) [73]
>
> >Ega23 © (29.12.05 10:24) [72]
> >Не прокатит, если в предложении прямая речь. Или диалог.
>
> Ну это уже от ТЗ зависит :) Возможно, лучше, как у Sha,
> не ограничители, а наоборот, допустимые в "словах" символы
> проверять

В варианте Sha не прокатят слова типа "черно-белый"
Нет в мире совершенства. :o)

Это я тоже не удержался :)

← →
Unknowing (2005-12-29 16:21) [77]

Господа! "ТЗ" было такое: посчитать слова в предложении (словом считать все между пробелами). Мой, боюсь сказать, код, работает полностью при любых введенных словах и в любом кол-ве. Просто я хотел убедиться в том, можно ли вообще так подходить к решению подобных задач. Т.е. я зациклился на термине "эффективность". Что лучше два цикла или как у мастера Sha множества. Потому как полагаю что для их обработки компилятор используют цикл. Вообщем: то что сделал я это:
-хорошо, но можно сделать иначе
или
-плохо!! Необходимо сделать иначе!
??

> -хорошо, но можно сделать иначе
> или
> -плохо!! Необходимо сделать иначе!

Каков критерий "необходимости"?

← →
Unknowing (2005-12-30 08:09) [79]

> "Необходимо" - значит можно сделать существенно лучше.

Ещё раз: что значит "существенно"?

Unknowing (29.12.05 16:21) [77]
Что лучше два цикла или как у мастера Sha множества. Потому как полагаю что для их обработки компилятор используют цикл.

Множества лучше. Для проверки на вхождение во множества используется не цикл, а одна машинная команда AND. Мастера, поправьте, если ошибаюсь.

← →
Unknowing (2005-12-30 09:23) [82]

> Ega23 © (30.12.05 09:11) [80]

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

> Unknowing (30.12.05 09:23) [82]
>
>
> > Ega23 © (30.12.05 09:11) [80]
>
> Ну, как с сортировкой!! Можно пузырьковым методом: задача
> выполняется, но не эффективно, а можно быстрой сортировкой:
> задача выполняется, но уже существенно лучше.

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

← →
Unknowing (2005-12-30 09:44) [84]

> Bless © (30.12.05 09:27) [83]

Джулиан Бакнелл (автор книги "Фундаментальные алгоритмы в Delphi")утверждает, что про пузырьковый метод можно смело забыть.

> Джулиан Бакнелл (автор книги "Фундаментальные алгоритмы
> в Delphi")утверждает, что про пузырьковый метод можно смело
> забыть.

Я не знаю, кто такой Джулиан Бакнелл, но на множестве из пяти элементов пузырёк рулит.

Кстати, алгоритм QuickSort - это не бинарное ли дерево?

← →
Unknowing (2005-12-30 09:59) [86]

← →
Unknowing (2005-12-30 10:01) [87]

> Ega23 © (30.12.05 09:49) [85]

> Кстати, алгоритм QuickSort - это не бинарное ли дерево?

Это, скорее, я у Вас должен спрашивать! :)

нет, сортировка с помощью бинарного дерева наз-ся "хипом", сортирующим деревом, пирамидальной

Когда-то реализовывал всё это, вот такие результаты на 16 элементах:
Bubble 0.0025
Shaker 0.0025
Selection 0.0024
Insertion 0.0012
InsertionO 0.0013
QuickSort 0.0027
QuickSortO 0.0016
HeapSort 0.0027

MergeSort 0.0015

Алгоритм распознает все русские слова в тексте, включая слова, которые пишутся через тире ("где-то", например), находит самое длинное и короткое слово в предложении.

Текст для проверки: Где-то на изходной планете времена изменились, это ли то самое удивительное - то, что называется градусником.

Результат:
Самое длинное слово: 12 сим.
Самое короткое слово: 2 сим.
Всего слов: 15

function slov(st:string):string; var mas: array of string; i, j: integer; n, n2: integer; begin st:=st+" "; j:=0; n:=0; n2:=length(st); setlength(mas,1); for i:=1 to length(st) do begin // распознает только русские слова if (ord(st[i])>185+3+3) and (ord(st[i])<253+2+1) then begin //showmessage(st[i]+" / "+IntToStr(length(mas))); mas[j]:=mas[j]+st[i]; end else begin if st[i]="-" then begin if (st[i-1]<>" ") and (st[i+1]<>" ") then mas[j]:=mas[j]+st[i]; end else begin if mas[j]<>"" then begin if length(mas[j])>n then n:=length(mas[j]); if length(mas[j])<n2 then n2:=length(mas[j]); inc(j); setlength(mas, length(mas)+1); end; end; end; end; result:="Самое длинное слово: "+inttostr(n)+" сим. "#13#10+"Самое короткое слово: "+inttostr(n2)+" сим."#13#10+"Всего слов: "+inttostr(length(mas)-1); end;

> MasterPaleva © (31.12.05 07:39) [91]

Давай разбираться.

1. Оператор st:=st+" "; излишен, т.к. непустая ANSI-строка
оканчивается символом #0, который, по идее, является разделителем.

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

3. Также крайне неэффективны операторы типа mas[j]:=mas[j]+st[i];
Ведь тебе впоследствии будут нужны не сами данные, а только длина
текущего слова. Вот и подсчитывай ее в отдельной переменной. Намного
быстрее и понятнее.

4. Буквы "Ё" и "ё", по-твоему, - иностранные?

5. Если строка начинается с "-", то возвращаемый функцией результат
зависит от старшего байта длины строки, т.к. делается попытка сравнения
(st[i-1]<>" ")

Успехов в новом году :)

Sha © (31.12.05 11:15) [93]

> 3. Также крайне неэффективны операторы типа mas[j]:=mas[j]+st[i];
>
> Ведь тебе впоследствии будут нужны не сами данные, а только
> длина
> текущего слова. Вот и подсчитывай ее в отдельной переменной.
> Намного
> быстрее и понятнее.

Да массив вообще там не нужен для решения этой задачи. Предполагается, что впоследствии придется работать с данными, сортировать слова, проверять грамотность написания слов, переводить слова и т.д.

> 4. Буквы "Ё" и "ё", по-твоему, - иностранные?

Мда, портят всю картину.

function slov(st:string):string; var mas: array of string; i, j: integer; n, n2: integer; begin st:=st+" "; j:=0; n:=0; n2:=length(st); setlength(mas,1); for i:=1 to length(st) do begin if (ord(st[i])>186) and (st[i]<>"Ё") and (st[i]<>"ё") then begin mas[j]:=mas[j]+st[i]; end else begin if st[i]="-" then begin if (st[i+1]<>" ") then mas[j]:=mas[j]+st[i]; end else begin if mas[j]<>"" then begin if length(mas[j])>n then n:=length(mas[j]); if length(mas[j])<n2 then n2:=length(mas[j]); inc(j); setlength(mas, length(mas)+1); end; end; end; end; result:="Самое длинное слово: "+inttostr(n)+" сим. "#13#10+"Самое короткое слово: "+inttostr(n2)+" сим."#13#10+"Всего слов: "+inttostr(length(mas)-1); end;

> Sandman29 © (30.12.05 09:23) [81]

> Для проверки на вхождение во множества используется не цикл,
> а одна машинная команда AND.

Цикл не используется. Но и одной командой AND дело не обходится. Обычно используется либо команда BT, либо арифметические операции с последующим анализом флагов. Зависит это от многих факторов: является ли множество переменной или константой, какова его максимальная мощность, и т.д.

> begin...end © (31.12.05 13:11) [95]
> Sandman29 © (30.12.05 09:23) [81]
> Sha © (28.12.05 19:54) [50]

Чтобы ускорить работу и оставить только BT, имеет смысл использовать
"полноразмерное" множество (set of char).

Для ускорения пролога и эпилога также хорошо бы объявить входной
параметр как const.

Т.о. процедура должна начинаться так:

procedure TelegramStatistics(const s: string; var wordcount, minlen, maxlen: integer); const characters: set of char= ["0".."9","A".."Z","a".."z","А".."Я","Ё","ё","а".."я"];

← →
Unknowing (2006-01-10 08:26) [97]

Рад снова всех приветствовать!!
Никак мне не дает покоя мой вопрос...:)

> Sha © (31.12.05 16:34) [96]

Каково Ваше мнение на предмет:

> -хорошо, но можно сделать иначе;
> или
> -плохо!! Необходимо сделать иначе!

> Unknowing (30.12.05 09:44) [84]
> > Bless © (30.12.05 09:27) [83]
> Джулиан Бакнелл (автор книги "Фундаментальные алгоритмы
> в Delphi")утверждает, что про пузырьковый метод можно смело
> забыть.

Интересно, а как автор предлагает сортировать большие сильно упорядоченные массивы?

> Unknowing (10.01.06 08:26) [97]

-плохо!! Необходимо сделать иначе!

Тут небыло хорошего варианта. Хорошего - в смысле как "в книге написано".

← →
Unknowing (2006-01-10 09:01) [100]

ато я теперь знаюкак правильно составлять телеграммы. Не ставить пробеллы. И платишь за одно слово. Гениально.

← →
Unknowing (2006-01-10 09:08) [102]

> Думкин © (10.01.06 09:05) [101]

Это не реальная задача!!!! Это, блин, для начинающих программировать!
> Igorek © (10.01.06 08:55) [99]

Не понял! Есть свой вариант?? Поясните!

Unknowing (28.12.05 16:35) [6] > Ega23 © (28.12.05 16:31) [3] Слова здесь все что между пробелами!! Задача посчитать стоимость телеграммы, которая считается из перечисленных параметров.

Я вас за язык не тянул, и за другие части тела тоже.

> Unknowing (10.01.06 09:08) [102]

Своего нету. Пока. :)
Хорошим вариантом я считаю полностью по-человечески расписанный конечный автомат. Он и по читабельности и по скорости будет близок к идеалу.

← →
Unknowing (2006-01-10 09:20) [105]

> Unknowing (10.01.06 09:20) [105]

Неужели ты думаешь я не видел [43] когда писал [104]?
И я имел ввиду конечный автомат в одной процедуре.

Эффективность алгоритма... А Ты сможешь лучше?? Найти похожие ветки