Предлагаю выделить отдельную тему (эту) для вопросов и ответов по курсу методов программирования, чтобы не привязываться к предыдущему треду про "нужны лабы".

 

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

 

Задавайте ваши вопросы, господа студенты https://academ.club/html/emoticons/smile.gif

 

// в принципе, вопросы можно задавать по любой школьной математике, не только по методам программирования https://academ.club/html/emoticons/smile.gif

Расскажите, пожалуйста алгоритм Бойера-Мура, этот алгоритм я не понимаю в принципе...уделите внимание, пожалуйста, описанию пострения таблицы смещений....

QUOTE (SupremEvil @ Jun 11 2007, 23:09)

Расскажите, пожалуйста алгоритм Бойера-Мура, этот алгоритм я не понимаю в принципе...уделите внимание, пожалуйста, описанию пострения таблицы смещений....

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

 

В процессе поиска каждый раз сдвигаем шаблон на рассотяние равное числу, что соответствует символу, с которым сравнивался последний символ шаблона... https://academ.club/html/emoticons/supdup.gif

 

 

Криво https://academ.club/html/emoticons/blink.gif , но, думаю, правильно ))

 

 

А теперь расскажите мне пожалуйста поподробнее алгоритмы пирамидальной сортировки и генерации перестановок по таблице инверсий ))

Изменено 11 июня, 200719 г. пользователем Гость

Пирамидальная сортировка

 

Попытаюсь изложить идею кратко, по пунктам. Даже вот рисунки нарисовал.

 

Пирамидой назовём такой массив A, в котором для каждого i выполняются условия A[i ] >= A[2*i+1] и A[i ] >= A[2*i+2] (кроме тех элементов, у которых нет парных). Я здесь считаю, что элементы нумеруются с нуля. Если мы каким-то волшебным образом сделали из массива пирамиду, то ясно, что максимальный элемент в таком массиве стоит в нулевой позиции. Можно сказать, что элементы массива выстроены в такое дерево, как на первом рисунке.

 

Научимся превращать массив в пирамиду. Во-первых, ясно, что у всех элементов правее середины (начиная с A[N/2+1]) парных элементов просто нет, т.е. для них условие пирамиды выполняется. На втором рисунке показан процесс просеивания -- в условии, что пирамида начинается от i+1-го элемента и продолжается до конца массива, к пирамиде добавляется i-й элемент. Делается это просто:

 

просеивание(A, i, N):
пока i < N, повторять:
   max = i
   если 2*i+1 < N и A[2*i+1] > A[max], присвоить max = 2*i+1
   если 2*i+2 < N и A[2*i+2] > A[max], присвоить max = 2*i+2
   // max -- номер максимального из трёх: A[i], A[2*i+1], A[2*i+2]
   если max == i, выход // условие пирамиды выполнено
   обмен A[i] <=> A[max] 
   // при этом пирамида может сломаться в элементе A[max], ведь мы поменяли его на меньший
   i = max // поэтому перейдём к проверке max-го элемента

 

Теперь, собственно, сам алгоритм. Изначально у нас, как вы помните, пирамида в массиве начинается от середины. Поочерёдно просеивая все элементы от среднего до нулевого, добавляем их к пирамиде (как на рис. 2) и получаем массив, как на рис. 3 справа. Максимальный элемент у него в начале. Ставим его в конец массива, отсекаем конец (N--) и замечаем, что элементы от первого (не считая отсечённого последнего) всё ещё образуют пирамиду (см. на дерево на рис. 3). Чтобы очередной максимальный элемент опять вылез в начало, достаточно вызвать просеивание для нулевого элемента. Затем новый максимальный опять в конец, и так далее.

 

пирамидальная сортировка(A, N):
для i от N/2 до 0 выполнить
   просеивание(A, i, N)
пока N > 1, повторять
   обмен A[0] <=> A[N-1]
   N--
   просеивание(A, 0, N)

 

Алгоритм можно легко переписать на C -- размер программы будет ничуть не больше.

 

Время работы алгоритма: т.к. операция просеивания выполняет не более log N операций (по основанию 2), суммарная сложность -- O(N log N).

heapsort.png

Генерация перестановок по таблице инверсий

 

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

 

Оказывается, таблицы инверсий проще перебирать, чем перестановки. Достаточно заметить, что последний элемент таблицы инверсий -- всегда 0, предпоследний -- 0 или 1, предпредпоследний -- 0, 1 или 2 и т.п. Начинаем от таблицы инверсий 000...0 и "добавляем" к ней по единице как будто бы "в столбик", но помня о максимально допустимых значениях. По каждой таблице инверсий восстанавливаем перестановку.

 

Пример (пишу от руки, надеюсь, без ошибок):

 

 0000  => 1234
+  1
----
0010  => 1243
+  1
----
0100  => 1324
+  1
----
0110  => 1423
+  1
----
1000  => 2134
+  1
----
1010  => 2143
+  1
----
1100  => 3124
+  1
----
1110  => 4123
+  1
----
2000  => 2314
......
и т.п.
+  1
----
3210  => 4321

 

Вот так они все и перебираются.

По Бойеру-Муру есть вопросы? Amigos рассказал всё правильно.

Машинная память как однородный линейно-адресуемый массив ячеек фиксированной разрядности. Понятие разрядности и формата числа.

 

Здесь просто нужно сказать, что память для программы представляется в виде одномерного (т.е. линейного) массива ячеек по 1 байту каждая. Адрес каждой переменной можно рассматривать как номер ячейки в этом массиве.

 

Любой тип (беззнаковое целое, знаковое целое, вещественные числа) занимают какое-то количество разрядов (бит), кратное восьми (1 байту), и записаны согласно некоторым правилам (формату). В курсе методов мы рассматривали следующие типы:

 

* целые числа без знака

* целые числа со знаком

* вещественные числа в формате с фиксированной точкой

* вещественные числа в формате с плавающей точкой

не очень понимаю суть билета

 

36. Области существования данных, связанные с программой и процедурами. Правила видимости имён из разных областей.

Александр Генадьевич обьясните этот билет

 

8. Проблема представления произвольного действительного числа в ЭВМ. Модель действительных чисел конечной точности: интервалы (классы чисел, сравнимых с заданной точностью). Арифметика интервалов. Понятие погрешности (потери точности).

Области существования данных, связанные с программой и процедурами. Правила видимости имён из разных областей.

 

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

 

int a; // глобальная переменная

void f()
{
   int a; // локальная переменная
   { // вложенный блок
       int a; // локальная переменная для блока
       a = 7; // присваивание локальной переменной блока
       ::a = 8; // присваивание глобальной переменной
       // здесь нет способа получить доступ к переменной a,
       // объявленной в начале функции
   }
   a = 9; // переменная a в начале функции
}

 

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

 

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

Изменено 13 июня, 200719 г. пользователем Гость

Проблема представления произвольного действительного числа в ЭВМ. Модель действительных чисел конечной точности: интервалы (классы чисел, сравнимых с заданной точностью). Арифметика интервалов. Понятие погрешности (потери точности).

 

Про это, Женя, рассказывать не буду, потому что было и на лекциях очень подробно, и хорошо описано в методичке. Если есть конкретные вопросы по каким-либо способам представления -- welcome.

2fenster: прошу прощения, ноя перепутал, мне нужно было узнать ответ на вопрос

 

8. Проблема представления произвольного действительного числа в ЭВМ. Модель действительных чисел конечной точности: интервалы (классы чисел, сравнимых с заданной точностью). Арифметика интервалов. Понятие погрешности (потери точности).

все дело в том, что я не могу уловить суть и найти нужное место в методичке. В Вирте тоже нет((

QUOTE (fenster @ Jun 13 2007, 02:14)

::a = 8; // присваивание глобальной переменной

:: -- расширение из C++.

QUOTE (worklez @ Jun 13 2007, 16:18)

QUOTE (fenster @ Jun 13 2007, 02:14)         ::a = 8; // присваивание глобальной переменной :: -- расширение из C++. Это даже не расширение, а просто чистый плюсизм -- пространства имён. Своим (в 603б) я ничего такого на лекциях не рассказывал (читал чистый C), но есть подозрение, что в некоторых группах читают помесь C и C++, потому и заикнулся про это в посте. По крайней мере, на экзамене дети из других групп сплошь и рядом читают из cin и пишут в cout.   Замечу, что комментарии в стиле // -- это тоже фича из C++, которую в C (С99) добавили заметно позже https://academ.club/html/emoticons/smile.gif

QUOTE (fenster @ Jun 13 2007, 15:43)

Это даже не расширение, а просто чистый плюсизм -- пространства имён.

Именно. :)

QUOTE

По крайней мере, на экзамене дети из других групп сплошь и рядом читают из cin и пишут в cout.

Есть подозрение, что народ приходит уже в таком состоянии. Некоторые просто отказываются понимать/использовать "эти неудобные функции из C" :).

QUOTE

Замечу, что комментарии в стиле // -- это тоже фича из C++, которую в C (С99) добавили заметно позже :)

Но они таки есть в стандарте C :).