Требования к реализации Язык реализации – Паскаль.

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

type

edition = ( book, newspaper, magazine);

publication = record

name : string; { — название }

year : integer; { — год издания }

shelf : word; { — номер полки }

case kind : edition of { — вид издания }

book : { для книги: }

( author : string[20]; { — автор }

publishers : string[10] { — издательство}

);

newspaper: { для газеты: }

( day : 1..31; { — день }

month : 1..12 { — месяц }

);

magazine : { для журнала: }

( issue : byte) { — номер выпуска }

end;

var

f : file of publication;

Лабораторная работа № 4. Системы счисления

Задание

Написать программу, которая переводит вещественное число из одной системы счисления в другую. Использовать алгоритмы перевода для целой и вещественной частей числа, описанные в [1].

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

На вход программе подаются:

b1 — целое число, основание входной системы счисления (2  b1  16),

b2 — целое число, основание выходной системы счисления (2  b2  16),

S — строка, представляющая собой последовательность цифр (запись чис­ла в системе счисления с основанием b1).

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

Нужно выдать на экран запись заданного числа в системе счисления с основанием b2.

Метод

Введем следующие обозначения:

число(c) – функция, выдающая числовое значение, соответствующее ли­тере c, обозначающей цифру в записи числа в некоторой системе счисления, на­при­мер, число(’1’) = 1, число(’B’) = 11.

символ(k) – для целого числа k выдает литеру, обозначающую соот­ветствующую данному числу цифру, например: символ(7)=’7’, символ(11) = ’B’.

Шаг 1. Разделить входную строку S на две части: строку S1, содержащую целую часть записи числа, и строку S2, содержащую дробную часть. S = S1.S2 (дробная часть может отсутствовать). Будем считать, что нумерация в строках начинается с 1.

Шаг 2. Перевод целой части числа из b1-с.с. в b2-с.с.

Пусть n1 — длина строки S1, d1 — массив целых чисел.

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

N := 0;

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

N := N * b1 + число(S1[i]);

конец цикла

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

если N = 0

то

начало

выдать_на_экран(’0’);

переход на Шаг 3;

конец

r1 := 1; //количество цифр в выходной записи числа

пока N  0 выполнять

d1[r1] := N mod b2; //остаток от деления на b2

N := N div b2; //целая часть от деления на b2

r1 := r1 + 1;

конец пока

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

выдать_на_экран(символ(d1[i]));

конец цикла

Шаг 3. Перевод дробной части числа из b1-с.с. в b2-с.с.

Пусть n2 — длина строки S2, K — максимальное количество знаков после запятой.

если (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]);

конец цикла

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