РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты в разделе

Алексеев Владимир Николаевич Статус: Мастер-Эксперт Рейтинг: 1250 ∙ повысить рейтинг »

solowey Статус: Профессионал Рейтинг: 95 ∙ повысить рейтинг »

CradleA Статус: Профессор Рейтинг: 3 ∙ повысить рейтинг »

∙ Алгоритмы и теория программирования

Номер выпуска:	235
Дата выхода:	04.11.2020, 16:15
Администратор рассылки:	Зенченко Константин Николаевич (Старший модератор)
Подписчиков / экспертов:	30 / 15
Вопросов / ответов:	3 / 5

Консультация # 53032:

Нужен красивый алгоритм: существует два условия 1(существование объекта) и 2(наличие свойства), если 1 = ложь, то проверка 2-го на истинность вызывает ошибку, если оба условия истинны выводится одно сообщение, иначе другое - обычный метод - (1 and 2) - не подходит, если не 1, то 2 вызывает ошибку! Спасибо!

Дата отправки: 23.08.2006, 15:53
Вопрос задал: Дмитрий Т.
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Лысков Игорь Витальевич (Мастер-Эксперт):

Здравствуйте, Дмитрий Т.!
Если не устраивает проверка 1&2, то можно предложить
if (1)
{
if (2)
{
//оба истинны
}
else
{
//1 - истина, 2 - ложь
}
}
else
{
//1 - ложь
}

Консультировал: Лысков Игорь Витальевич (Мастер-Эксперт) Дата отправки: 23.08.2006, 16:03

Рейтинг ответа: 0 поблагодарить эксперта

Консультирует Басков Олег Владимирович:

Здравствуйте, Дмитрий Т.!

Уточню предыдущий ответ: на Паскале надо поставить перед ifом директиву {$B-},тогда до второй проверки просто не дойдёт. А вообще всё гораздо проще на асме...

Консультировал: Басков Олег Владимирович Дата отправки: 24.08.2006, 01:32

Рейтинг ответа: 0 поблагодарить эксперта

Консультация # 185967:

Здравствуйте уважаемые эксперты! У меня возникли сложности с таким вопросом:

Дата отправки: 05.05.2012, 13:15
Вопрос задал: Куценко Андрей Валерьевич
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Vest:

Здравствуйте, Андрей Валерьевич!

Так как нельзя явно задавать компьютеру какие входящие символы являются буквами, пробелами и знаками препинания (для цифр и букв иностранных алфавитов эти группы можно расширить), то необходимо составить такое множество условий или правил, которое бы позволяло разгруппировать символы по группам.

Всё что разрешено делать со входящим текстом - это собрать статистику по символам. Статистика будет полезна в том случае, когда невозможно явно определить к какой группе принадлежит символ.

Для начала воспользуемся условными обозначениями: (б)уква, (р)азделитель, знак (п)препинания и (х) - любой символ.

На основе статистики выбрать первые несколько символов, которые наиболее часто употребляются в тексте. И предположить, что текущий символ является разделителем (р). Для них осуществить поиск по шаблону: "рхр", "рххр". Эти правила определяют, что разделитель как минимум отделяет один или два л юбых символа от остальных. Можно было бы воспользоваться правилом, где три любых символа идут подряд, но это если возникнет противоречивая ситуация.
Отдельно, можно предположить, что разделитель не будет присутствовать в начале или конце текста (или строки). Потому что в задаче ничего не говорится про разрыв строк, и мы можем предположить, что строки непрерывны и отделяются друг от друга клавишами Enter.

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

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

Консультировал: Vest Дата отправки: 05.05.2012, 18:47

Рейтинг ответа: 0 поблагодарить эксперта

Консультирует Алексей Бурин:

Здравствуйте, Куценко Андрей Валерьевич!

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

(1) подсчёт символов
(1.2) выбор 3-х групп символов
1 - вероятные разделители
2 - вероятные буквы
3 - вероятные специальные символы
* группы должны иметь довольно существенную разницу, например
вес разделителя 100 -90 %
вес буквы 70 - 30 %
вес знака 10-1 % (знак в данном случае - знак препинания или служебный символ)
тут считаешь сколько раз встречается каждый символ и самый большой результат берёшь за 100%
** естественно, может получится несколько символов в группе 1.
в таком случае, если например, в первой группе оказалось 3 символа - каждый из них является разделителем с вероятностью в 33%
***статистику и распределение по группам не выбрасывай - сделай табличку со всеми найденными с имволами и занеси туда статистику для каждого
(2) уточнить разделитель
в случае, если в группе 1 оказалось несколько символов, нужно отсеять "лишние" (например ' ', о, а)
тут нужно применять правила.. можно придумать кучу правил.
правило 1 - длина слов. смысл в том, что знаки препинания делят цепочки символов на более мелкие слова, чем буквы
нужно просматривать весь текст и искать, например, самое длинное слово, для каждого разделителя.
причём, мы ищем "статистически" - то есть лучше выбрать не одно а 10 самых длинных "слов" и взять их среднюю длину.
например текст "нужно просматривать весь текст и искать, например, самое длинное слово, для каждого разделителя."
даст результат "пробел" - самое длинное слово - 13 символов, 'о' - 46 символов, 'а' - 24 символа.
то есть "о" - 100%, "а" - 52% и пробел - 28%.
разница очевидна.
правило 2 - знаки всегда идут до или после пробела.
тоже хорошее правило... но пока что невозможно быть уверенным на счёт знаков, то есть пробел никогда не будет стоять рядом с "ъ"
с другой стороны, ни "а" ни "о" тоже не стоят рядом с "ъ", что делает это правило оправданным.
нужно считать пары "знак"+"пробел" или "пробел"+"знак" для всех возможных пробелов со всеми возможными знаками
например, тот же текст " нужно просматривать весь текст и искать, например, самое длинное слово, для каждого разделителя. "
для пробела даст 5 совпадений ( ","+" "), ( "ь"+" " ), ("." + " ")
для "о" даст 1 совпадение ("о" + ",")
для "а" даст 0 совпадений
я в этом случае указал и "ь" потому что скорее всего буквы "ь", "ъ" ока жутся в группе знаков..
в любом случае - правило однозначно работает
...можно составить сколько угодно правил..
в итоге, используя набор правил можно выбрать наиболее вероятный разделитель
*я рекомендую ВСЕ результаты сохранять в табличке, в которой записана статистика по символам
в разных столбцах, конечно ))

(3) уточнить знаки (знаки препинания и специальные символы)
нужно применить другой набор правил к тексту
например
правило 1 знаки - это символы, которые всегда идут до или после "разделителя"
берёшь список всех символов, которые встретились в тексте и начинаешь просматривать текст
если встречается сочетание "символ"+"пробел" или "пробел"+"символ" - подтверждаешь этот символ
если встречается сочетание "не пробел"+"символ"+"не пробел" - вычёркиваешь этот символ из списка.
получается список из "вычеркнутых", "подтверждённых" ; и "не подтверждённых" знаков - заносим в ту же табличку со статистикой
"подтверждённые знаки", которые входят в группу 3 - можно считать доказанными
"вычеркнутые знаки" - это буквы типа "ъ"
"не подтверждённых" теоретически быть не должно... если появятся - стоит поискать ошибки

(4) Правила - "заглавные буквы"
можно применить правило поиска "заглавных букв" по шаблону типа
"пробел"+"возможная заглавная буква"+"буква"
бывают одиночные заглавные буквы ( "А", "И"), но их невозможно подтвердить..
подтверждение "заглавных букв" - считать "слово" после "заглавной буквы" и найти совпадение в тексте
если найдётся совпадение, но вместо заглавной буквы будет стоять другая буква - можно считать "заглавную букву" доказанной
и даже занести её в ту же табличку на против соответствующей &qu ot;строчной буквы"
если одной "заглавной букве" будет соответствовать несколько "строчных букв" то нужно считать, что это исключение
- вычеркнуть символ из списка "заглавных букв" и не применять к нему это правило.
если есть несколько исключений, то можно считать, что это правило не работает на данном тексте.


(5) Дополнительные правила - "цифры" это сложный разбор текста...
"цифры" могут входить во все 3 группы, но практически всегда идут вместе друг с другом
это работа для небольшой базу данных...
нужно прочитать текст и сделать табличку из всех сочетаний всех символов, которые встречаются в тексте,
подсчитав количество таких сочетаний.
при разборе нужно принять во внимание, что, например, "б" скорее всего никогда не встретится с "щ" но оба символа встретятся с "о"
тут можно использовать порог, например "цифра с 80% вероятность ю"
но, нужно помнить, что требуется проанализировать БОЛЬШОЙ объём текста
и всё равно - не факт, что удастся корректно выделить "цифры"

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

Консультировал: Алексей Бурин Дата отправки: 08.05.2012, 07:50

Рейтинг ответа: 0 поблагодарить эксперта

Консультация # 173026:

Здраствуйте уважаемые эксперты.
Не могу обьяснить алгоритм.
Код программы реализующей сортировку массива методом вставки.
for (i=0;i<n;i++)
{
key=a[i];
j=i-1;
while (j>=0 &key<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=key;
Сохраняю время перед началом и после конца и от последнего отнимаю первое.
Нужно построить зависимость времени затраченого на выполнение от кол-ва.
Вот таблица значений что получились:
Количество элементов Количество мили секунд
6000 11
8000 22
10000 33
12000 44
14000 60
16000 82
18000 105
20000 132
22000 159
24000 198

Зависимость не прямая. Как это можно правильно обьяснить? Какая она и почему?

При сортировке прямым упорядочением:
for (i=0;i<n-1;i++)
{
key=a[i];
for (j=i+1;j<n;j++)
{
while (a[j]<key)
{
a[i]=a[j];
a[j]=key;
key=a[i];
Получается следующий график. Значения брал другие и больше для большей точности :
n Время
5001 16
6001 27
7001 33
8001 44
9001 55
10001 66
11001 82
12001 99
13001 110
14001 132
15001 149
16001 165
17001 192
18001 208
19001 236
20001 258
21001 285
22001 313
23001 340
24001 368
25001 396
26001 434
27001 467
28001 494
29001 527

Чем можно обьяснить эту зависимость. Заранее благодарен.

Дата отправки: 07.10.2009, 19:18
Вопрос задал: Dimon4ik
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Evgenijm:

Здравствуйте, Dimon4ik.
А у сортировки и не долна быть линейная зависимость. Хороший показатель для сравнивающей сортировки (это почти все использующиеся кроме корзинки) - n*log(n). А вернее - log(n!), что немного меньше. Сложность у хороших методов обычно в границах 1,5*logn - 3*logn. Оба Ваши примера относятся к плохим - их сложность n^2. А разные числа - тут мы сталкиваемся с реальностью, а не с теорией :)
1) Слишком короткие временные рамки - очень велика погрешность измерений. Это можно сгладить.
2) Разное количество операций на итерацию у разных алгоритмов. Благодаря этому, если сравнивать отношение времени у двух алгоритмов - оно тоже будет плавать. "Быстрые" алгоритмы обычно очень плохо дружат с короткими последовательностями.
3) Во время выполнения может проснуться какая-то другая программа (вот тут короткий интервал все портит)
4) Параметры системы: если количество данных уже не помещается в кеш или в оперативную память - производител ьность очень резко падает.
5) Разные последовательности одинаковой длины все равно требуют разного количества операций. Причем зачастую очень разного. Более-менее стабильные сортировки: Heapsort, Mergesort, Tablesort.

Так что для теста желательно заготовить сортируемый блок и перед вызовом метода копировать этот блок в рабочий массив. А короткую сортировку просто повторять по 100-1000 раз. Но также: копировать данные из заготовки. Еще можно воспользоваться счетчиком: они менее зависимы от внешних условий.
А еще желательно проделать эту процедуру несколько раз с заново сгенерированными блоками, чтобы не впадать в зависимость.

Консультировал: Evgenijm Дата отправки: 11.10.2009, 03:08

Рейтинг ответа: 0 поблагодарить эксперта

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка