Форум программистов, компьютерный форум, киберфорум
Наши страницы

Turbo Pascal

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.83
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
#1

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

26.09.2010, 15:24. Просмотров 3300. Ответов 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):

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

вывести "YES" – если введенные слова являются анаграммами друг друга, "NO" – если нет - Turbo Pascal
Даны два слова на отдельных строках. Слова состоят из строчных латинских букв и цифр. ребуется вывести &quot;YES&quot; – если введенные слова...

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

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

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

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

27
Tronix
157 / 104 / 5
Регистрация: 22.08.2010
Сообщений: 215
26.09.2010, 19:07 #16
На 50 строке нужно заменить is_anogram на is_anogram2, с 51 строки убрать лишний end. Ну а дальше уже косяки программы.
В 80 строке заменить всю конструкцию на if (i <> j) and (length(s[i]) = length(s[j])) then
В 81 заменить is_anogram на is_anogram2

Типа того )
1
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
26.09.2010, 19:46  [ТС] #17
всё это хорошо, но ругается на 11 строку...

Tronix, можешь перевести кусок на асм?
Pascal
1
2
for i := 1 to l do if a[i] = s then 
    goto no_need;
a - массив строк, s - строка
0
Tronix
157 / 104 / 5
Регистрация: 22.08.2010
Сообщений: 215
26.09.2010, 20:00 #18
Цитата Сообщение от iama Посмотреть сообщение
всё это хорошо, но ругается на 11 строку...
Странно, у меня не ругается... компилил FPC v2.4.0
fpc proga.pas -Mtp

Этот цикл особого смысла не имеет переводить - ускорения значительного не будет.
1
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
26.09.2010, 20:08  [ТС] #19
Tronix, это одно из самых тормозных мест. мне немного ещё дооптимизировать, и будет что надо. на файле из 10 000 работает 3-4 секунды
0
Tronix
157 / 104 / 5
Регистрация: 22.08.2010
Сообщений: 215
26.09.2010, 20:21 #20
Цитата Сообщение от iama Посмотреть сообщение
Tronix, это одно из самых тормозных мест. мне немного ещё дооптимизировать, и будет что надо. на файле из 10 000 работает 3-4 секунды
Ну а скомпилировалась-то нормально? Давай полный код программы, текущая версия и файл in.txt (все можно в рар-архив пакануть). Попробую тебе заоптимизировать все наглухо
1
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
26.09.2010, 20:24  [ТС] #21
и ещё раз, спасибо
0
Вложения
Тип файла: rar optimize-it.rar (42.6 Кб, 19 просмотров)
Tronix
157 / 104 / 5
Регистрация: 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
1251 / 976 / 49
Регистрация: 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 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
26.09.2010, 20:49 #24
Хочется сильно пооптимизировать - пользуйтесь профилировщиком.
0
Tronix
157 / 104 / 5
Регистрация: 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
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
26.09.2010, 20:56  [ТС] #26
Tronix, и там тоже его нет. с процедурой не компилируется, если не сложно, выложи fp.ini, под которым у тебя запустилось
0
Миниатюры
Определить, являются ли два слова анаграммами  
Tronix
157 / 104 / 5
Регистрация: 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
1251 / 976 / 49
Регистрация: 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
Привет! Вот еще темы с ответами:

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

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

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

Определить, являются ли два введеных числа взаимно простыми - Pascal
Набрать и отладить программу,определяющую,является ли два введеных числа взаимнопростыми (НОД=1). помоему так- Function Vz_pr(n,...


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

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

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