183648 (596697), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Контрольные примеры.

.

Замечания.

1. Если разряды p-ичного числа необходимо формировать не от старшего разряда, а от младшего и далее, то в программе dec_p_i() первый и второй аргументы функции stack() необходимо поменять местами.

2. При переводе неотрицательных десятичных чисел в конкретную систему счисления, в функции dec_p_i() достаточно иметь один аргумент. Например, перевод в двоичную систему можно осуществлять следующей программой-функцией dec_b_i(m).

Контрольные примеры.

Как мы уже отмечали при реализации функций dec_p_i(m,p) и dec_b_i(m) использован рекурсивный вариант алгоритма последовательного деления выделения цифр p-ичной системы для целых чисел. Пояснений требуют лишь фрагменты вида identity(1)x. Дело в том, что функция stack() в качестве своих аргументов использует векторы или матрицы. И смысл записи identity(1)x состоит в превращении скаляра х в матрицу размера 11 с элементом x.

Задача 2. Составить программу-функцию перевода правильной неотрицательной десятичной дроби y в систему счисления по основанию p.

Решение. Функция dec_p_f(y,p,k) решает поставленную задачу, используя рекурсивный алгоритм последовательного умножения. Результат формируется в виде вектора с не более чем k (k=1,2,…) компонентами, которые суть p-ичные цифры числа y, начиная от старших разрядов и далее.

Контрольные примеры.

Задача 3. Составить программу-функцию перевода неотрицательного действительного десятичного числа a в систему счисления по основанию p (p=2, 3, …).

Решение. Функция dec_p(a,p,k) решает поставленную задачу, осуществляя перевод десятичного числа a в p-ичную систему счисления. Результат вычислений формируется в виде составного вектора. Компоненты этого вектора снова векторы, содержащие соответственно цифры целой и дробной частей числа a в p-ичной системе счисления. Цифры целой и дробной части a возвращаются, начиная со старших разрядов и далее. В дробной части присутствует не более чем k (k=1,2,...) цифр. При вычислениях функция dec_p() обращается к двум рекурсивным функциям dec_p_i() и dec_p_f().

Контрольные примеры.

Задача 4. Пусть m=(v₀v₁…v_n1)₁₀ целое десятичное неотрицательное число, цифры которого от старшей и далее заданы последовательными компонентами вектора v=(v₀, v₁, …,v_n1)^T . Составить программу-функцию перевода m в систему счисления по основанию p.

Решение. Функция dec_p_iv(v,p) осуществляет перевод v в p-ичную систему счисления. Результат вычислений формируется, начиная от старших разрядов и далее, в виде вектора, компоненты которого суть p-ичные цифры исходного числа. Функция dec_p_iv(v,p) отличается от ранее рассмотренной функции dec_p_i(v,p) лишь формой представления первого аргумента. Поэтому её вычисление можно свести к вычислению dec_p_i(v,p) с предварительным обращением к рекурсивной функции dv_norm(v), переводящей десятичное число из векторного представления в нормальную форму. Это и сделано ниже.

Контрольные примеры.

Задача 5. Пусть y=(.v₀v₁…v_n1)₁₀ правильная неотрицательная десятичная дробь, цифры которой от старшей и далее заданы последовательными компонентами вектора v=(v₀, v₁, …,v_n1)^T. Составить программу-функцию перевода y в систему счисления по основанию p.

Решение. Функция dec_p_fv(v,p,k) осуществляет перевод v в p-ичную систему счисления. Результат вычислений формируется, начиная от старших разрядов и далее, в виде вектора длины не более k, компоненты которого суть p-ичные цифры исходного числа. Функция dec_p_fv(v,p,k) отличается от ранее рассмотренной функции dec_p_f(v,p,k) лишь формой представления первого аргумента. Поэтому её вычисление можно свести к вычислению dec_p_f(v,p,k) с предварительным обращением к рекурсивной функции dv_normf(v), переводящей десятичную дробь из векторного представления в нормальную форму. Это и сделано ниже.

Контрольные примеры.

Задача 6. Пусть действительное неотрицательное десятичное число a представлено двумя векторами in и fr, компоненты которых последовательные десятичные цифры, начиная от старшей и далее, соответственно целой и дробной части а. Составить программу-функцию перевода a в систему счисления по основанию p.

Решение. Функция dec_pv(in,fr,p,k) решает поставленную задачу, осуществляя перевод десятичного числа a в p-ичную систему счисления. Результат вычислений формируется в виде составного вектора. Компоненты этого вектора снова векторы, содержащие соответственно цифры целой и дробной частей числа a в p-ичной системе счисления. Цифры целой и дробной части a возвращаются, начиная со старших разрядов и далее. В дробной части присутствует не более чем k (k=1,2,...) цифр. При вычислениях функция dec_p() обращается к двум рекурсивным функциям dec_p_iv() и dec_p_fv().

Контрольные примеры.

B. Перевод чисел из p-ичной системы в десятичную систему

Пусть p{2,3,…} и цифрами p-ичной системы являются десятичные числа 0,1,... ,p1. Будем считать, что рассматриваются неотрицательные p-ичные числа, а их цифры от старшего разряда и далее задаются последовательными компонентами векторов. Рассмотрим 3 конкретные задачи.

Задача 7. Пусть m=(v₀v₁…v_n1)_p целое p-ичное неотрицательное число, цифры которого от старшей и далее заданы последовательными компонентами вектора v=(v₀, v₁, …,v_n1)^T . Составить программу-функцию перевода m в десятичную систему счисления.

Решение. Функция p_dec_i(v,p) решает поставленную задачу, используя рекурсивный алгоритм последовательного деления. Результат формируется в естественной форме.

Контрольные примеры.

Задача 8. Пусть y=(.v₀v₁…v_n1)_p правильная неотрицательная десятичная дробь, цифры которой от старшей и далее заданы последовательными компонентами вектора v=(v₀, v₁, …,v_n1)^T . Составить программу-функцию перевода y в десятичную систему счисления.

Решение. Функция p_dec_f(v,p) решает поставленную задачу, используя рекурсивный алгоритм последовательного умножения. Результат формируется в естественной форме.

Контрольные примеры.

Задача 9. Пусть действительное неотрицательное p-ичное число а представлено двумя векторами in и fr, компоненты которых последовательные p-ичные цифры, начиная от старшей и далее, соответственно целой и дробной части а. Составить программу-функцию перевода a в десятичную систему счисления.

Решение. Функция p_dec(in,fr,p) решает поставленную задачу, осуществляя перевод p-ичного числа a в десятичную систему счисления. Результат вычислений формируется в естественной форме. При вычислениях функция p_dec() обращается к двум рекурсивным функциям p_dec_i() и p_dec_f().

Контрольные примеры.

Замечание. Перевод чисел из p-ичной системы счисления в q-ичную систему (p,q{2,3,…}) можно осуществлять через промежуточную десятичную систему.

13.5 Генераторы перестановок

Ранее в разделе 12.9 мы описали один из алгоритмов получения n! перестановок из элементов множества S={a₀, a₁, …, a_n1}, где a_k (k=0..n1) попарно различные действительные числа. Считая, что S={1,2,…,n}, обсудим еще несколько вариантов рекурсивных алгоритмов генерирования перестановок. Отличаются друг от друга они разными характеристиками: быстродействием, компактностью записи, количеством транспозиций при получении очередной перестановки и т.д.

A. Метод вертикальной прогонки. При S={1} имеем одну перестановку 1. Если уже имеется последовательность перестановок из n1 элемента {1,2,…,n1}, то получить все перестановки из n элементов {1,2,…n} можно способом, который мы будем именовать как “метод вертикальной прогонки” элемента n. Суть его в следующем. Рассмотрим n идентичных экземпляров (групп) последовательностей перестановок из элементов {1,2,…,n1}. В первом экземпляре в конец каждой перестановки поместим элемент n. Во втором экземпляре этот элемент поместим на предпоследнем месте и т.д. Наконец, в последнем экземпляре поместим n перед первым элементом. На рисунке 13.4 описанная процедура демонстрируется при переходе от n=3 к n=4. Нетрудно понять, что указанные действия любую перестановку из n1 элемента переводят в некоторую перестановку из n элементов. При этом общее количество полученных перестановок равно n!. Остается показать, что среди них нет совпадающих. Если взять две сгенерированные перестановки внутри одной группы, то они будут различаться друг от друга позициями элементов {1,2,…,n1} и, значит, не могут быть совпадающими. Если же взять перестановки из разных групп, то позиции элемента n в них будут разными и перестановки опять не могут быть совпадающими. Таким образом, все полученные n! перестановок различны.

Рис. 13.6. Генерирование перестановок методом вертикальной прогонки.

Описанный алгоритм вертикальной прогонки реализуется рекурсивной программой-функцией permut1(n):

Контрольный пример

B. Метод последовательного замещения. При S={1} имеем одну перестановку 1. Если уже имеется последовательность перестановок из n1 элемента {1,2,…,n1}, то получить все перестановки из n элементов {1,2,…n} можно способом, который мы будем именовать как “метод последовательного замещения” элемента n. Суть его в следующем. Рассмотрим n идентичных экземпляров (групп) последовательностей перестановок из элементов {1,2,…,n1}. В первом экземпляре, как и в методе вертикальной прогонки, в конец каждой перестановки поместим элемент n. В каждой перестановке второго экземпляра поменяем местами элементы n и 1. В каждой перестановке третьего экземпляра поменяем местами элементы n и 2 и т.д. Наконец, в последнем экземпляре поменяем местами элементы n и n1. На рисунке 13.5 описанная процедура демонстрируется при переходе от n=3 к n=4. Нетрудно понять, что указанные действия любую перестановку из n1 элемента переводят в некоторую перестановку из n элементов. При этом общее количество полученных перестановок равно n!. Остается показать, что среди них нет совпадающих. Если взять две сгенерированные перестановки внутри одной группы, то они обязательно будут различаться друг от друга расположением элементов на позициях от 1 до n1 и, значит, не могут быть совпадающими. Если же взять перестановки из разных групп, то на последних позициях у них стоят разные элементы и перестановки опять не могут быть совпадающими. Таким образом, все полученные n! перестановок различны.

Рис. 13.5. Генерирование перестановок методом последовательного

замещения

Описанный алгоритм последовательного замещения реализуется рекурсивной программой-функцией permut2(n):

С. Перестановки в антилексикографическом порядке. На множестве P всех перестановок 0,x₁,…,x_n-1> из элементов {1,2,…,n} определим два типа порядка.

Лексикографический порядок на P вводится следующим образом. Для

(0,a₁,…,a_n1>,0,b₁,…,b_n1>P) (19)

положим

0,a₁,…,a_n1> <’ 0,b₁,…,b_n1>

(k 0) [(a_k b_k) & (s < k) [(a_s = b_s)]], (20)

где символ <’ использован в качестве знака лексикографического сравнения перестановок.

Заметим, что если вместо чисел 1,2,…,n использовать буквы с естественным порядком следования их в алфавите, то лексикографический порядок определяет стандартную последовательность, в которой слова длины n появляются в словаре. И это справедливо для алфавитов любых языков.

Аналогично вводится и антилексикографический порядок на P. Для (19) положим

0,a₁,…,a_n1> <” 0,b₁,…,b_n1>

(k n1) [(a_k > b_k) & (s > k) [(a_s = b_s)]], (21)

где символ <” использован в качестве знака антилексикографического сравнения перестановок.

Построим рекурсивную программу-функцию, генерирующую перестановки элементов {1,2,…n} в антилексикографическом порядке. Соответствующий алгоритм может базироваться на следующих двух утверждениях, непосредственно вытекающих из определения 21.

Утверждение 1. Если множество перестановок P упорядочено антилексикографически, то начальная и конечная перестановки это соответственно <1,2,…,n> и .

Утверждение 2. Упорядоченная антилексикографически последовательность перестановок по значению последнего элемента в них может быть разбита на n блоков длины (n1)!. При этом q-й блок на последнем месте имеет элемент равный (nq+1), а первые n1 позиций этого блока определяют последовательность перестановок множества {1,2,…,n}\{q} в антилексикографическом порядке.

Головная функция permut3(n) решает поставленную задачу. В ней по значению n для рекурсивной программы-функции permu(p) формируется начальная перестановка p. В permu(p) и проводятся все вычисления. На рис. 13.6 представлен результат выполнения permut3(n) при n=3 и n=4. Для n=4 полученные перестановки расположены по столбцам.

Рис. 13.6. Генерирование перестановок в антилексикографическом порядке

D. Перестановки в лексикографическом порядке. В предыдущем разделе мы ввели понятие лексикографического порядка. Алгоритм генерирования перестановок в таком порядке и соответствующие программы-функции могут быть построены на идеях, близких к тем, которые использовались при генерировании перестановок в антилексикографическом порядке. Поэтому здесь мы ограничимся лишь приведением соответствующих функций permut(p) и permut4(n) и представим полученный по ним результат вычислений для n=3 и n=4 (см. рис. 13.7). Для n=4 полученные перестановки расположены по столбцам.

Рис. 13.7. Генерирование перестановок в лексикографическом порядке

E. Перестановки c одной транспозицией соседних элементов. В этом пункте рассматривается алгоритм генерирования последовательности перестановок U из элементов множества {1,2,…,n} такой, что любая перестановка U, кроме начальной, получается из предыдущей перестановки одной транспозицией соседних элементов. Проиллюстрируем на примере идею соответствующего алгоритма, приписываемого Джонсону [] и Троттеру []. Предположим, что для элементов {1,2,…,n1} уже построена требуемая последовательность перестановок U. Тогда из элементов {1,2,…,n} необходимая последовательность может быть построена перемещениями элемента n между начальной и конечной позициями каждой перестановки U. При этом перемещения должны производиться попеременно вперед и назад (n1)! раз так, как это показано на рис. 13.8.

Рекурсивная программа-функция permut5(n) реализует этот, схематично описанный, алгоритм. На рис. 13.8 приведены полученные по permut5(n) перестановки для n=3 и n=4.

Рис. 13.8. Генерирование перестановок c транспозицией соседних элементов

В заключение автор выражает признательность профессорам. Ваграменко Я.А. и Добровольскому Н.М. за консультации и советы при написании пособия.

Литература

1. Кнут Д. Искусство программирования для ЭBM. Основные алгоритмы: т. 1, M.: Мир, 1976.

2. Кнут Д. Искусство программирования для ЭBM. Получисленные алгоритмы: т. 2, М.: Мир, 1977.

3. Кнут Д. Искусство программирования для ЭBM. Сортировка и поиск: т. 3, М.: Мир, 1978.

4. Лекции лауреатов премии Тьюринга. М.: Мир, 1985.

5. Бауэр Ф.Л., Гнац Р., Хилл У. Информатика. Задачи и решения. М.: Мир, 1978 г.

6. Бауэр Ф.Л., Гооз Г. Информатика. T. 1, М.: Мир, 1990 г.

7. Бауэр Ф.Л., Гооз Г. Информатика. T. 2, М.: Мир, 1990 г.

8. Ландау Э. Основы анализа. М.: изд. Иностранной литературы, 1947.

9. http://www-cs-staff.stanford.edu/~knuth/taocp.html#vol4-{volume4}).

Характеристики

Список файлов ВКР