Задачка

← →
Kerk © (2010-03-27 15:22) [0]

Все знают игру, в которой дается длинное слово и нужно из его букв составлять другие слова. Как оптимально проверить, действительно ли слово А составлено из букв слова Б? Программно, конечно же.

← →
Юрий Зотов © (2010-03-27 15:28) [1]

Если одна и та же буква может быть использована несколько раз, то проверить принадлежность одного множества символов (А) другому (Б).

Если строго однократное использование, то в цикле по слову А проверяем, есть ли такой символ в слове Б и удаляем его из слова Б.

← →
Kerk © (2010-03-27 15:31) [2]

> Юрий Зотов © (27.03.10 15:28) [1]
>
> Если одна и та же буква может быть использована несколько раз

Да, нужно уточнить. Не может.

← →
Игорь Шевченко © (2010-03-27 15:32) [3]

Не надо переносить в начинающие

← →
Множества в Делфи (2010-03-27 15:36) [4]

www.interface.ru/home.asp?artId=22631
или посмотреть еще в
articles.org.ru

← →
Kerk © (2010-03-27 15:43) [5]

А если чуть подумать и решать не в лоб? :)

← →
xayam © (2010-03-27 15:48) [6]

Удалено модератором
Примечание: Offtopic

← →
xayam © (2010-03-27 15:50) [7]

Удалено модератором
Примечание: Offtopic

← →
И. Павел © (2010-03-27 15:56) [8]

Если задача состоит в том, чтобы искать в текущем слове много других слов, то можно представить текущее слово в виде массива, где 1-ый элемент - количество букв "А" в слове, 2-ой - "Б" и т.д. Тогда не нужно будет искать буквы, и это, наверное, ускорит алгоритм. Повторюсь - только если сравниваемых слов много.

← →
KilkennyCat © (2010-03-27 16:07) [9]

> xayam © (27.03.10 15:48) [6]

самый лучший алгоритм архивации изобрел я, и уже давно, ибо в 1-ом байте умещается три буквы, и при этом никакой архивации ;)

← →
Kerk © (2010-03-27 16:09) [10]

> И. Павел © (27.03.10 15:56) [8]

В данный момент я так и делаю. Интересно, есть ли более быстрый способ?

← →
имя (2010-03-27 16:25) [11]

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

← →
[true]TRIx © (2010-03-27 16:31) [12]

> действительно ли слово А составлено из букв слова Б? Программно,
> конечно же.

Просто. Например проверить по циклу все буквы слова в другом.

← →
имя (2010-03-27 16:32) [13]

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

← →
имя (2010-03-27 16:36) [14]

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

← →
EvChul © (2010-03-28 11:55) [15]

Упорядочить в словах буквы по алфавиту и сравнить результаты.

← →
MBo © (2010-03-28 11:56) [16]

Отсортировать буквы в словах.
слон-> лнос
Далее поиск подпоследовательности

← →
@!!ex © (2010-03-28 11:58) [17]

> [10] Kerk © (27.03.10 16:09)
> В данный момент я так и делаю. Интересно, есть ли более
> быстрый способ?

А куда быстрее-то?

← →
PZ (2010-03-28 12:11) [18]

> [9] KilkennyCat © (27.03.10 16:07)

Такой алгоритм я использовал еще в 80-х годах на БК-0010. Но это не моё изобретение.

← →
[true]TRIx © (2010-03-28 14:05) [19]

Нафиг лишний раз сортировать. Имхо это дольше будет выполняться чем
function test(slovo1,slovo2:string):boolean; var i:integer; begin result:=true; for i:=1 to length(slovo2) do if pos(slovo2[i],slovo1)=0 then begin result:=false; break; end; end;

вхождения всех символов полученного слова из слова 1

← →
@!!ex © (2010-03-28 14:42) [20]

> [19] [true]TRIx © (28.03.10 14:05)

pos - ВЕСЬМА не быстрая операция.

← →
Kerk © (2010-03-28 15:03) [21]

> [true]TRIx © (28.03.10 14:05) [19]

Более того, твой код попросту не решает поставленную задачу.

← →
@!!ex © (2010-03-28 15:15) [22]

> [17] @!!ex © (28.03.10 11:58)
> > [10] Kerk © (27.03.10 16:09)
> > В данный момент я так и делаю. Интересно, есть ли более
>
> > быстрый способ?
>
> А куда быстрее-то?

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

← →
turbouser © (2010-03-28 16:16) [23]

> KilkennyCat © (27.03.10 16:07) [9]
>
>
> > xayam © (27.03.10 15:48) [6]
>
> самый лучший алгоритм архивации изобрел я

Не надо врать.. его я изобрел.. У меня все в один бит жмется %)

← →
KilkennyCat © (2010-03-28 16:46) [24]

> turbouser © (28.03.10 16:16) [23]

не работал ли ты в компании "ТВК" в конце 90-х? Знавал я там одного... у него была гениальная идея, как все сжать до одного бита. С расжатием проблемы только были.

← →
Chirockie (2010-03-28 20:10) [25]

function IsSuperword(ASuperword: AnsiString; const AWord: string): boolean; var P: PAnsiChar; P1: PAnsiChar; begin P := PAnsiChar(AWord); while P^ <> #0 do begin P1 := PAnsiChar(ASuperword); while true do if P1^ = #0 then begin Result := false; Exit end else if P1^ = P^ then begin P1^ := #1; Break end else P1 := P1 + 1; P := P + 1 end; Result := true; end;

← →
Chirockie (2010-03-28 20:21) [26]

function IsSuperword(ASuperword: AnsiString; const AWord: AnsiString): boolean;

← →
Chirockie (2010-03-28 20:24) [27]

+ UniqueString()

:-(

← →
@!!ex © (2010-03-28 21:05) [28]

> [25] Chirockie (28.03.10 20:10)

Если я правильно понял логику работы функции, то:
1) IsSuperword("ABBBB","AAAAB") == true
2) Переборов не счесть. В то время, как массив достаточнор один раз заполнить и один раз проверить.

НЕ увидел профита от этого метода.

← →
Chirockie (2010-03-28 21:38) [29]

Если я правильно понял логику работы функции, то:
1) IsSuperword("ABBBB","AAAAB") == true

false

2) Переборов не счесть

?

2) ...один раз проверить.

Алгоритм проверки?

← →
антифа-- (2010-03-29 01:35) [30]

исходим из предположения, что исходное слово одно, а производных много :)
исходим из того, что слова в аскии. в случае чего, преобразовываем. пользуемся тем, что русские буквы в аски упорядочены по православному алфавиту
заводим массив
SrcLetterEstVSlove array[0..32] of boolean := [false, false,false, .... false,]
where
trueѢ - буква есть в начальном слове
falseѢ - никак не встречается
массив 32 байта утечкой памяти не считаем даже в мобильнике.
заполняем
дальше честно лень набивать. :)

> Kerk © (27.03.10 15:22)

Есть еще игра Эрудит. Там писать игру за комп интересно. Можно вводить разные правила, придумывать реализацию уровней сложностей. Писал такую 7 лет назад.

KilkennyCat сколько людей я на шум поднял. у меня тоже идея такая была, на бумаге логично поначалу было, а потом не все продумал. Теперь что, весь блокнот исписыл, потихоньку подыскиваю методы.

Kerk

почему же нет, итоговое слово проверяется на соответствие из символов первого слова ли оно состоит.

> [29] Chirockie (28.03.10 21:38)
> 1) IsSuperword("ABBBB","AAAAB") == true
>
> false

А. Точно. Оно же единицей затирается. Ступил.

> [29] Chirockie (28.03.10 21:38)
> 2) Переборов не счесть
>
> ?

На каждую букву слова мы проверяем супрслово.

> [29] Chirockie (28.03.10 21:38)
> Алгоритм проверки?

Заоплняем массив, потом проверяем буквы массива.

← →
Chirockie (2010-03-29 10:03) [34]

>@!!ex © (29.03.10 07:33) [33]
>Заоплняем массив, потом проверяем буквы массива.

Интересует конкретно алгоритм проверки, со всеми инициализациями и финализациями, если таковые имеются.

> Chirockie (29.03.10 10:03) [34]
> Интересует конкретно алгоритм проверки, со всеми инициализациями и финализациями, если таковые имеются.

Это демонстрация идеи.
При желании алгоритм можно значительно оптимизировать.

procedure ShaFilterDictionaryByString(var slFiltered: TStringList; const slDictionary: TStringList; const s: string); type TCharCounters= record TestNo: integer; CharCount: byte; CharFound: byte; Rest1: byte; Rest2: byte; end; var Filter: array[char] of TCharCounters; i, j: integer; ch: char; t: string; label NextString; begin; slFiltered.Clear; for ch:=Low(char) to High(char) do with Filter[ch] do begin; TestNo:=0; CharCount:=0; CharFound:=0; end; for i:=1 to Length(s) do inc(Filter[s[i]].CharCount); for j:=0 to slDictionary.Count-1 do begin; t:=slDictionary[j]; for i:=1 to Length(t) do with Filter[t[i]] do begin; if TestNo<>j then begin; TestNo:=j; CharFound:=1; end else if CharFound<CharCount then inc(CharCount) else goto NextString; end; slFiltered.Add(t); NextString: end; end; procedure TForm1.Button1Click(Sender: TObject); var s: string; slFiltered, slDictionary: TStringList; begin slFiltered:=TStringList.Create; slDictionary:=TStringList.Create; slDictionary.Text:=Memo1.Text; s:=Edit1.Text; ShaFilterDictionaryByString(slFiltered, slDictionary, s); Memo2.Text:=slFiltered.Text; end;

← →
Chirockie (2010-03-29 12:59) [38]

2 Sha

Я спрашивал про алгоритм. Не надо было код писать. Тем более такой...

> Как оптимально проверить, действительно ли слово А составлено
> из букв слова Б?

Проверять на этапе формирования слова Б.
Слово А есть суть массив.
Если введенная буква найдена в массиве, удаляем символ из массива, даем вводить следующую букву.

А сейчас возникнет второй вопрос -
Как проверить, что слово Б есть слово, а не абракадабра?

Задачка Найти похожие ветки