Форум программистов, компьютерный форум, киберфорум
Наши страницы
Turbo Pascal
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.83
iama
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
#1

Определить, являются ли два слова анаграммами - Turbo Pascal

26.09.2010, 15:24. Просмотров 3581. Ответов 27

Задание: написать программу, которая опеределяет, являются ли два слова анаграммами (т. е. слова, которые содержат только одинаковые буквы в одинаковом колличестве, например, "апельсин" и "спаниель")
Алгоритм:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
var s1, s2: string;
 
function is_anagram(s1, s2: string): boolean;
var a1, a2: array [0..255] of byte; i: word; res: boolean;
begin
for i := 0 to 255 do begin
     a1[i] := 0;
     a2[i] := 0;
end;
 
for i := 1 to length(s1) do
     a1[ord(s1[i])] := a1[ord(s1[i])] + 1;
 
for i := 1 to length(s2) do
    a2[ord(s2[i])] := a2[ord(s2[i])] + 1;
 
res := true;
 
for i := 0 to 255 do
    if a1[i] <> a2[i] then begin
        res := false;
        break;
    end;
 
is_anagram := res;
end;
 
begin
readln(s1);
readln(s2);
if is_anagram(s1, s2) then write('they are')
else write('they aren''t');
readln;
end.
Нужно сравнять его с грязью. Ну, или нужна обьективная критика, кому как нравится. 100 000 выполнений этой функции должны происходить меньше, чем за 3 секунды.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.09.2010, 15:24
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Определить, являются ли два слова анаграммами (Turbo Pascal):

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

вывести "YES" – если введенные слова являются анаграммами друг друга, "NO" – если нет
Даны два слова на отдельных строках. Слова состоят из строчных латинских букв и...

Проверить, являются ли данные два слова обращенными друг к другу
Проверить, являются ли данные два слова обращенными друг к другу, то есть...

Определить, являются ли два файла тождественными
Даны два файла целых чисел. Определить , являются ли они тождественными.

Определить, являются ли два числа взаимно простыми
Здравстуйте! У меня есть задание. Написать программу проверки введенные два...

Определить, являются ли два первых символа цифрами
Дан символьный файл f. В файле не менее двух компонентов. Определить, являются...

27
iama
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
26.09.2010, 20:24  [ТС] #21
и ещё раз, спасибо
0
Вложения
Тип файла: rar optimize-it.rar (42.6 Кб, 19 просмотров)
Tronix
157 / 104 / 6
Регистрация: 22.08.2010
Сообщений: 215
26.09.2010, 20:40 #22
Не,а. Как я и предполагал, тот цикл вообще ни играет роли никакой. Я вот просто заменил тело циклов основных на такое:
Pascal
1
2
3
4
5
6
7
8
9
10
for i := 1 to n - 1 do
        for j := i + 1 to n do
        if length(s[i]) = length(s[j]) then
                if is_anagram(s[i], s[j]) then begin
                        r[l] := s[i];
                        r[l+1] := s[j];
                        Inc(l,2);
                        {add_word(r, l, s[i]);
                        add_word(r, l, s[j]);}
                end;
Тоесть без вызова add_word, а просто тупо сразу в массив выходной заношу. И сравнил разницу выполнения. Разница состовляет ~50 ms, что ничто вообщем-то. Смысла нет.
0
iama
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
26.09.2010, 20:44  [ТС] #23
Tronix, там есть такой кусок:
Pascal
1
for i := 1 to l do if a[i] = s then goto no_need;
нужно проверить, есть ли уже в массиве такое слово, т. к. анаграмм одного слова может быть много, например, "мама", "аамм", "маам".
А что тогда за слабое место? а то в стандартном паскале нет GetTickCount
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
26.09.2010, 20:49 #24
Хочется сильно пооптимизировать - пользуйтесь профилировщиком.
0
Tronix
157 / 104 / 6
Регистрация: 22.08.2010
Сообщений: 215
26.09.2010, 20:51 #25
Ну видимо слабое место - это два цикла этих главных:
Pascal
1
2
for i := 1 to n - 1 do
        for j := i + 1 to n do
Я знаю, что в паскале нет gettickcount, но так ты же вроде под FreePascal пишешь? Процедура ассемблерная то под него написана. А если стандартной процедурой паскалевской твоей - то она и тормозит...
0
iama
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
26.09.2010, 20:56  [ТС] #26
Tronix, и там тоже его нет. с процедурой не компилируется, если не сложно, выложи fp.ini, под которым у тебя запустилось
0
Миниатюры
Определить, являются ли два слова анаграммами  
Tronix
157 / 104 / 6
Регистрация: 22.08.2010
Сообщений: 215
26.09.2010, 21:00 #27
А я компилирую прям из командной строки, без IDE.
fpc proga.pas -Mtp

Вот это у меня без проблем так компилируется:
Pascal
1
2
3
4
Uses Windows;
begin
    writeln(gettickcount);
end.
1
iama
1326 / 979 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
26.09.2010, 21:02  [ТС] #28
Tronix, таки опять туплю, приписал досовский модуль и удивляюсь, почему не пашет
0
26.09.2010, 21:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.09.2010, 21:02
Привет! Вот еще темы с решениями:

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

Определить,являются ли 2 слова дружественными.
Два слова назовем дружественными,если из букв одного можно составить другое и...

Определить: являются ли цифрами первые два символа файла
В заданном символьном файле, где не меньше чем два компонента, определить:...

Определить, являются ли два первых символа файла цифрами
Дан текстовый файл f. В файле не менее двух компонент. Определить, являются ли...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
28
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru