Билет 9. Генерация К-подмножеств в порядке минимального изменения

Теорема. Первым кодовым словом в G(n) ровно k единицами будет 1^k0^n-^k, а последним - 1^k-10^n-^k1 и 0ⁿ, если k=0.

Доказательство:

Проведем индукцию по n, при n=1 - очевидно. Пусть теорема справедлива для i£n и любых k, покажем, что теорема справедлива для n+1 и всех k. В терминах G(n) соотношение {1} из п.3.2 может быть записано как G(n+1)=G(n)0;G^R(n)1, поэтому первое кодовое слово с k³0 единицами (кроме k=n+1) есть первое кодовое слово в G(n) с приписанным справа нулем. Иными словами, 1^k0^n+1-^k, как и требовалось. Аналогично последнее кодовое слово с k³1 единицами в G(n) c приписанной справа единицей - это 1^k-10^n-^k+11, как и требовалось. В случае k=n+1 единственным словом в G(n+1), содержащим n+1 единицу, является 1ⁿ⁺¹.

Теорема 4.2. Соседние кодовые слова в G(n,k) различаются ровно в двух разрядах.

Доказательство:

Проведем индукцию по n. Теорема, очевидно, справедлива для n=1, поскольку k=0, либо k=1. Предположим, что теорема верна для n и всех k, 0£k£n. Покажем, что она верна для n+1 и любого k, 0£k£n+1. Если k=0 или k=n+1, она справедлива, так как G(n+1) содержит только одно соответствующее кодовое слово. Для 1£k£n теорема выполняется по индукционному предположению, если кодовые слова оба либо в G(n)0 либо G^R(n)1. Таким образом, требуется только рассмотреть, на сколько разрядов отличается последнее кодовое слово с k единицами в G(n)0 от первого кодового слова с k единицами в G^R(n)1. Из предыдущей теоремы следует, что эти слова имеют вид: при k=1 0^n-110 и 0ⁿ1, при k>1 1^k-210^n-^k10 и 1^k-200^n-^k11 соответственно.

Следствие. Последовательность кодовых слов G(n,k), n³k³0, можно определить следующей рекурсией:

G(n,k)=G(n-1,k); G^R(n-1,k-1)1 и G(n,0)=0ⁿ, G(n,n)=1ⁿ. {2}

В самом деле, это определение действительно задает последовательность, совпадающую с той, которая получается удалением из G(n) всех кодовых слов с числом единиц, не равным k.

Рекурсивное определение {2} приводит к следующей программе генерации кодовых слов G(n,k) на языке Паскаль.

program subset2;

const n= ; k= ; {0<k<=n}

var i : integer;

s:array[1..n] of 0..1;

procedure print (m,h:integer);

begin

if h<>0 then h:=1;

for i:=1 to m do s[i]:=h;

for i:=1 to n do write(s[i]);

Writeln

end;

procedure GR(m,h:integer); forward;

procedure G(m,h:integer);

begin

if (h=0) or (m=h) then print(m,h)

else

                                                 begin s[m]:=0; G(m-1,h);

                                                             s[m]:=1; GR(m-1,h-1)

                                                 end

end;

procedure GR;

begin

              if (h=0) or (m=h) then print(m,h)

                                     else

                                                 begin s[m]:=1; G(m-1,h-1);

                                                             s[m]:=0; GR(m-1,h)

                                                 end

end;

   begin {SUBSET2} G(n,k) end.

Комментарий. Процедура GR(m,h) соответствует G^R(m,h). Процедура print служит для вывода генерируемых кодовых слов. Для дальнейшего анализа алгоритма остановимся подробнее на дереве вызова процедурG и GR.

Билет 10. Строки

String

Объявление строк:

Var s:string;

Type s1:string [20];

Длина строки меньше или равна 255 символам. Первая ячейка – длина строки.

Конкатенация – «склеивание»

‘E’ + ‘A’ + ‘2012’ = ‘EA2012’

К строкам можно применять операторы отношений, т.к. “<”, “>”, “>=” etc.

(в лексикографическом порядке)

Процедуры:

Delete (St, Poz, N); - удаляет N элементов в строке St начиная с позиции Poz

Insert (St, St2, Poz); - вставляет St в строкe St1 начиная с позиции Poz

Функции:

Copy(St, Poz, N) :string - выделяет подстроку в строке St размеров в N символов начиная с Poz

Concat (St1 , St2 , , Stn) :string - выполняет конкатенацию (то же самое, что и «+»)

Length(S) :integer - длина строки

Pos(St1,St2) :integer - номер символа, с которого начинается первое вхождение St1 в St2

Билет 11. Процедурные типы

Пример: вычисление определенного интеграла от функции f.

        F не передать ни по ссылке, ни по значению.

Передача по наименованию:

Type Proc1=procedure;

   Proc2=procedure (var x,y:integer);

   Func1=function(x:real):real;

Var p1=proc1;

P2=proc2;

F1=Func1;

Существует ряд правил использования подпрограмм в качестве процедурной переменной:

- они должны компилироваться с ключом компилятора {$F+} или иметь директиву far для получения полного адреса подпрограмм;

- они не должны быть стандартными процедурами и функциями;

- они не должны объявляться внутри других процедур и функций;

- они не должны быть типа inline или interrupt.

{$f+}

Procedure Swap(var a,b:integer);

Var t:integer;

Begin

    t:=a;

    a:=b;

    b:=t;

End;

Function tan(angle:real):real;

Begin

       Tan := sin(angle) / cos(angle) ;

End;

{$f-}

Begin

       P2:=swap;

       F1:=tan;

End;

Билет 12. Файлы

Файл состоит из последовательности компонент одного и того же типа может в разное время содержать различное число компонент (возможно и ни одной).

Тип компонент файла может быть любым, но не должен содержать внутри себя других файлов или указателей. (Последнее ограничение связано с тем, что файлы хранятся, как правило, на внешних устройствах, при этом указатели, которые указывают на объекты в основной памяти, теряют смысл после окончания работы программы, в то время как файл может быть сохранен и дольше.)

Определение типа файла выглядит так

File of T

где T – определение типа компонент файла.

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

С особенностью размещения файлов связано еще одно ограничение, накладываемое на работу с переменной типа файла: нельзя присваивать такой переменной новое значение с помощью оператора присваивания и передавать значение такой переменной в процедуру или функцию. Это ограничение не относится к передаче параметров- переменных в процедуру.

Изменение значений переменных типа файла происходит путем добавления или удаления компонент файла с помощью стандартных процедур обработки файлов.

Файлы могут быть внешними и внутренними (локальными). Локальные файлы создаются при входе в ту подпрограмм, где они описаны, и уничтожаются при выходе из нее. Такие файлы могут физически располагаться как во внешней, так и в оперативной памяти.

Внешние файлы – хранятся на внешних устройствах. Связываемся с ними специальными директивами.

В Турбо Паскале существуют три класса файлов: типизированные, текстовые и нетипизированные. Для типизированных указан тип компонент файла; в текстовых компоненты имеют стандартный тип TEXT; в нетипизированных компоненты представляют собой конечные совокупности символов или байтов, при этом представление char или byte не играют никакой роли|, а важно лишь с точки зрения объема занимаемых данных.

Процедуры:

Assign (F, Name) – связь файловой переменной с внешним файлом, имеющим имя Name. Name – переменная или константа типа string (или совместимого для присваивания с ним типа) или типа PСhar. Имя типа должно быть написано в соответствии с правилами MS DOS, может включать путь и не должно превышать 79 символов. Если строка имени пустая, осуществляется связь со стандартными файлами ввода или вывода.

Reset(F[,Size]) – открытие существующего файла.

Открывается существующий файл, с которым связана файловая переменная F, и указатель текущей компоненты файла настраивается на начало файла. Необязательный параметр целого типа Size используется только с файлами без типа и задает размер пересылаемого элемента информации в байтах. По умолчанию этот размер равен 128.

Rewrite(F[,Size]) –открытие нового файла.

Открывается новый пустой файл, и ему присваивается имя, заданное процедурой Assign. Если файл с таким именем уже существует, то он уничтожается. Необязательный параметр Size имеет тот же смысл, что и в процедуре Reset.

Close(F) –закрытие внешнего файла.

Закрывает внешний файл, с которым связана файловая переменная F. При этом в случае необходимости в содержимое файла вносятся все произведенные изменения.

Функции:

Eof(F)– конец файла.

Принимает значение true, если указатель текущей компоненты находится за последней компонентой файла (за последним символом, если файл текстовой), и false – в противном случае.

IOResult –результат последней операции ввода-вывода.

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

Процедуры для типизированных файлов:

Read(F,<список ввода>) – чтение информации из файла.

То же, что и процедура read для текстовых файлов, но переменные, в которые читается информация, должны быть того же типа, что и компонента файла.

Write(F,<список вывода>) –запись информации в файл.

То же, что и процедура write для текстовых файлов, но список вывода представляет собой переменные того же типа, что и компонента файла.

Билет 13. Текстовые файлы

Файл называется текстовым, если его компоненты являются литерами.

Text – стандартный тип, разбивает на строки.

Дата добавления: 2018-04-04; просмотров: 270; Мы поможем в написании вашей работы!
Поделиться с друзьями:

⇐ Предыдущая 1 234 Следующая ⇒

Мы поможем в написании ваших работ!