Рекурсия (стр. 11 из 12)
Задача 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=(v0v1…vn-1)10 - целое десятичное неотрицательное число, цифры которого от старшей и далее заданы последовательными компонентами вектора v=(v0, v1, …,vn-1)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=(.v0v1…vn-1)10 - правильная неотрицательная десятичная дробь, цифры которой от старшей и далее заданы последовательными компонентами вектора v=(v0, v1, …,vn-1)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,... ,p-1. Будем считать, что рассматриваются неотрицательные p-ичные числа, а их цифры от старшего разряда и далее задаются последовательными компонентами векторов. Рассмотрим 3 конкретные задачи.
Задача 7. Пусть m=(v0v1…vn-1)p- целое p-ичное неотрицательное число, цифры которого от старшей и далее заданы последовательными компонентами вектора v=(v0, v1, …,vn-1)T . Составить программу-функцию перевода m в десятичную систему счисления.
Решение. Функция p_dec_i(v,p) решает поставленную задачу, используя рекурсивный алгоритм последовательного деления. Результат формируется в естественной форме.
Контрольные примеры.
Задача 8. Пусть y=(.v0v1…vn-1)p- правильная неотрицательная десятичная дробь, цифры которой от старшей и далее заданы последовательными компонентами вектора v=(v0, v1, …,vn-1)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={a0, a1, …, an-1}, где ak (k=0..n-1) - попарно различные действительные числа. Считая, что S={1,2,…,n}, обсудим еще несколько вариантов рекурсивных алгоритмов генерирования перестановок. Отличаются друг от друга они разными характеристиками: быстродействием, компактностью записи, количеством транспозиций при получении очередной перестановки и т.д.
A.Метод вертикальной прогонки. При S={1} имеем одну перестановку - 1. Если уже имеется последовательность перестановок из n-1 элемента {1,2,…,n-1}, то получить все перестановки из n элементов {1,2,…n} можно способом, который мы будем именовать как “метод вертикальной прогонки” элемента n. Суть его в следующем. Рассмотрим n идентичных экземпляров (групп) последовательностей перестановок из элементов {1,2,…,n-1}. В первом экземпляре в конец каждой перестановки поместим элемент n. Во втором экземпляре этот элемент поместим на предпоследнем месте и т.д. Наконец, в последнем экземпляре поместим n перед первым элементом. На рисунке 13.4 описанная процедура демонстрируется при переходе от n=3 к n=4. Нетрудно понять, что указанные действия любую перестановку из n-1 элемента переводят в некоторую перестановку из n элементов. При этом общее количество полученных перестановок равно n!. Остается показать, что среди них нет совпадающих. Если взять две сгенерированные перестановки внутри одной группы, то они будут различаться друг от друга позициями элементов {1,2,…,n-1} и, значит, не могут быть совпадающими. Если же взять перестановки из разных групп, то позиции элемента n в них будут разными и перестановки опять не могут быть совпадающими. Таким образом, все полученные n! перестановок различны.