Методы программирования: Методическое пособие для выполнения лабораторных работ, страница 3

     если (n2 = 0) то переход на Шаг 4.

     Выдать_на_экран (’.’);

По схеме Горнера найти значение дробной части числа и записать в переменную Nf:

Nf := 0;

цикл по i от n2 до 1 с шагом -1

     Nf := (число(S2[i]) + Nf)/ b1;

конец цикла

Найти запись дробной части числа в системе счисления с основанием b2:

k2 := 1;

пока (Nf ¹ 0) и (k2 < K)

  выдать_на_экран (символ(целая_часть(Nf * b2)));

 Nf := дробная_часть(Nf * b2)

  конец пока

Шаг 4. Конец работы алгоритма 

Требования к  реализации

Язык программирования – С.

Написанная программа должна проверять корректность входных данных.

Лабораторная работа № 5.  Перестановки

Задание

Написать программу, которая генерирует все перестановки заданной длины двумя способами.

Использовать следующие алгоритмы, описанные в [1]:

1)  рекурсивный,

2)  один из алгоритмов по выбору:

§ Дейкстры (поиск следующей по алфавиту перестановки),

§ инверсионный.

Входные данные

На вход программе подается целое число N — порядок перестановки.

Выходные данные

Нужно выдать на экран или в файл все перестановки чисел из множества {1, 2 ,..., N} по одной перестановке на каждой строке.

Метод 1.Рекурсивный

Пусть N £ 9 (например, N = 5).

Тогда метод состоит в вызове рекурсивной процедуры

Permut (’’, ’12345’).

процедура Permut

(rez   : строка; // результирующая строка

          source : строка  // исходная строка

         )

начало процедуры

//Вычисляется длина исходной строки:

ls := длина(source);

  если ls = 0     // Это условие окончания рекурсии.

// Перестановка построена и ее

то выдать(rez)  // нужно выдать на экран или в файл

  иначе

цикл по i от 1 до ls с шагом 1

       // вызвать процедуру Permut, вырезав из исходной

       // строки i-тый элемент и добавив его в конец

    // результирующей строки :

    Permut( rez+source[i],

         source[1..i-1] + source[i+1..ls]);

 конец цикла

конецпроцедуры

Метод 2. Алгоритм Дейкстры построения следующей по алфавиту перестановки

Шаг 1. Выдать первую по алфавиту перестановку p= 1, 2, 3, ...  N.

Шаг 2. Пусть p = a_1, a₂, ..., a_N  — перестановка, полученная на предыдущем шаге.

   i := N – 1;

Найти первую с конца пару элементов перестановки, упорядоченную по возрастанию:

   пока a_i > a_i+1 выполнять 

   i := i – 1;

конец пока         

 Найти наименьший элемент a_j, такой что a_j > a_i при j>i:

j := i + 1;

пока a_j > a_i выполнять    

  j := j + 1;             

j := j – 1;

 a_j и a_i поменять местами в перестановке p:

x := a_i;                  

a_i := a_j;                  

a_j := x;

Отсортировывать хвост перестановки, начиная с i-го элемента, впорядке возрастания:

цикл по k от 1 до ((N-i) div 2) с шагом 1

  x := a_i+k;      

  a_i+k := a_N-k+1;

  a_N-k+1 := x;

конец цикла

Выдать на экран или в файл полученную перестановку p.

Шаг 3.  если  перестановка p равна N, N–1,...,3, 2, 1 ,

то   конец работы алгоритма

иначе перейти на Шаг 2.

Метод 3. Инверсионный

Шаг 1.

Построить начальную таблицу инверсий B длины N, состоящую из нулей: 0, 0,...,0.

Выдать на экран или в файл соответствующую ей перестановку: 1, 2, 3, ..., N.

Шаг 2.

Пусть B = b₁, b₂, ..., b_N – таблица инверсий, построенная на предыдущем шаге. Тогда следующая таблица инверсий получается из нее прибавлением к ней единицы:

   i := N;

   flag := истина;

пока flag выполнять

     x := b_i + 1;

     если x > N – i

     то

начало

b_i := 0;

i := i–1;

 конец

     иначе

       начало

b_i := x;

         flag := ложь;

       конец

   конец пока

Построить перестановку, соответствующую полученной таблице инверсий:

Пусть А — массив длины N, заполненный 0 (0 обозначает пустое место).

цикл по i от 1 до N  с шагом 1 выполнять

  //для каждого i пропустить b_i пустых мест

  j := 0;                      

     k := 0;

  пока j £ b_i выполнять        

    k := k + 1;

       если A[k] = 0

       то j := j + 1;             

     конец пока

      //и поместить i на следующее пустое место: