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

В процессе поиска каждый раз сдвигаем шаблон на рассотяние равное числу, что соответствует символу, с которым сравнивался последний символ шаблона...


Криво , но, думаю, правильно ))


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

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

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

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

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

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

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

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

Это даже не расширение, а просто чистый плюсизм -- пространства имён. Своим (в 603б) я ничего такого на лекциях не рассказывал (читал чистый C), но есть подозрение, что в некоторых группах читают помесь C и C++, потому и заикнулся про это в посте. По крайней мере, на экзамене дети из других групп сплошь и рядом читают из cin и пишут в cout.

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

Именно. :)

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

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

выдаст "равны" (а если убрать один нолик из f2, то будет уже "не равны"). Получается, что одному набору бит соответствует несколько чисел (целый интервал на прямой), и все действительные числа разбиваются таким образом на классы (классов этих для четырёхбайтного типа float всего 2^32, а на деле ещё меньше -- подробнее об этом ниже). Причём, что интересно, чем больше по модулю число, тем большей длины интервал "равных" ему чисел на прямой.

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

В модели с плавающей запятой ненулевые числа представляются по частям: отдельно знак s, порядок e и мантисса f:

x = s * f * 2^e

(2 -- основание системы счисления). Как это работает, надеюсь, все представляют; отмечу лишь, что мантисса f лежит в интервале [1, 2). Подробнее, опять же, ниже.

Как выполнять арифметические операции с такими числами? Для сложения и вычитания двух чисел, заданных в виде s * f * 2^e, нужно сначала привести их к одному порядку (к большему), затем сложить (вычесть) мантиссы и результат нормализовать. Для умножения и деления нужно сложить (вычесть) порядки и перемножить мантиссы, результат нормализовать.

Какие бывают погрешности и откуда берётся потеря точности? Нас интересуют два момента: нехватка знаков в мантиссе и потеря точности при приведении к большему порядку.

1. Нехватка знаков в мантиссе.

Простейший пример: число 0.1. Если попытаться перевести его в двоичную систему, получим 0.000110011001100..., т.е. 0.0(0011) -- бесконечную дробь. Получается, что на самом деле число 0.1 не может быть точно представлено в типе float. Из этого, например, следует тот факт, что цикл

зависнет, т.к. точного равенства с единицей никогда не получится.

2. Потеря точности при приведении к большему порядку.

Простейший пример: сложим 1000000 и 0.0000001.

Получим следующее:

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

На этом "то, что нужно знать всем", заканчивается, в следующем посте напишу про то, как всё это на самом деле работает. На лекции в 603б я про это читал, но, кажется, мало кто меня до конца понял

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

Реально вместо порядка e хранится число E = e + 127. Сделано это для того, чтобы можно было хранить порядок в виде беззнакового целого числа -- так их удобнее сравнивать. Кроме того, в мантиссе не хранят первую цифру (которая в нормализованном ненулевом двоичном числе всё равно всегда равна единице).

Соответственно, есть следующие варианты:

1. Если порядок числа (e) находится между -126 и 127 включительно (т.е. реально хранится E, лежащее в отрезке от 1 до 254), то число записывается в нормализованном виде "без сюрпризов". Первая цифра мантиссы не хранится. Всего существует 2 * 254 * 2^23 различных чисел в таком формате.

2. Если хранящийся порядок числа E = 0 (что как бы по идее должно соответствовать порядку e = -127), происходит несколько другое. Число считается ненормализованным с порядком -126, мантисса хранится полностью (потому что в ненормализованном числе первая цифра может быть любой). В частности, в записи числа 0 все биты равны нулю (а есть ещё -0, в котором нулю равны все биты, кроме знакового). Различных чисел из второго пункта существует 2 * 2^23.

3. Если хранящийся порядок числа E = 255 (что как бы по идее должно соответстовать порядку e = 128), а мантисса состоит из нулей, то число считается плюс или минус бесконечностью (в зависимости от знака). Бесконечностей, таким образом, две.

4. Если хранящийся порядок числа E = 255 (что как бы по идее должно соответстовать порядку e = 128), а мантисса содержит хотя бы один ненулевой бит, то считается, что данная запись некорректна -- т.е. не соответствует никакому числу. Такие "не числа" так и называются: NaN, Not a Number. Их общее количество равно 2 * (2 ^ 23 - 1).

Таким образом, всего существует 2 * 254 * 2^23 + 2 * 2^23 = 4278190080 различных чисел типа float, две бесконечности и 16777214 NaN'ов. Суммарное число вариантов равно 2^32, т.е. никого не забыли.

В аттаче к данному посту -- код на C, который показывает двоичное строение числа типа float. Пример работы ниже. Заметьте, что первый бит мантиссы (единица) не хранится для ненулевых нормализованных чисел!

Дополнительная информация: статья на Википедии про IEEE 754.