Случайных неповторяющихся чисел

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

) Листинг 10.3. Множество случайных неповторяющихся чисел

var a;set of byte;

k,x,n:byte; begin

randomize; a:=[]; k:=l;

write('Введите количество чисел: '); readln(n);

while k<=n do begin

x:=random(n)+1;{ определяем случайное х от 1 до n }

if not {x in a) then begin { нет такого числа в множестве? }

»

write(x, ' '); а:=а+[х]; { добавляем х в множество а } k:=k-f-l, end;

end; readln; end.

Приведенный вариант обладает одним существенным недостатком — коли­чество сформированных случайных чисел не может быть больше 255. Более длинные последовательности формируются с использованием массивов.

Ввиду важности задачи приведем здесь эффективный вариант ее решения, который основан на массиве. Если воспользоваться примерно тем же алго­ритмом, что и для множеств, то решение получится неэффективным, т. к. проверка принадлежности элемента массиву осуществляется значительно медленнее, чем проверка на принадлежность множеству. Особенно много "лишних" действий выполняется при определении последних элементов массива.

Все же есть очень быстрый вариант решения этой задачи. Идея состоит в том, что массив сначала заполняется последовательными числами, а затем каждый его элемент меняется значением с каким-нибудь другим элементом (его номер определяется случайным образом) этого же массива (лис­тинг 10.4).

[Листинг 10.4. Массив из случайных неповторяющихся чисел

: ' т -V \-.

var a:array[l..10000] of integer; k,l,i,n:integer;

ok:boolean; begin

randomize;

write('Введите количестве элементов массива: '); readln(n);

for k:=l to n do

a[k]:=k; { заполняем массив последовательными числами от 1 до n } for k:=l to n do begin

l:=random(k)+l; { определяем номер второго элемента } i:=a[k]; a[k]:=a[l]; a[l]:=i; { меняем значениями a[k] и а[1] } end;

writeln('Сформированный массив:'); for k:=l to n do write(a[k],' '}; readln; end.

Записи

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

Для записи комбинации данных разных типов в Turbo Pascal применяется комбинированный тип данных — запись. Запись представляет собой наибо­лее общий и гибкий структурированный тип данных, т. к. она может быть образована из неоднотипных компонентов, и в ней явным образом выра­жена связь между элементами данных, которые характеризуют реальный объект.

. _Л

Определение и правила записи

Запись — это структурированный тип данных, состоящий из фиксированно­го числа компонентов одного или нескольких типов, называемых полями записи. В отличие от массива, компоненты (поля) записи могут быть раз­личного типа. Чтобы можно было ссылаться на тот или иной компонент записи, каждое поле имеет свое имя (а не номер, как элемент массива). Записи можно объявить следующим способом.

Сначала объявляется тип записи.

type

ИмяТипа = record

ИмяПоля!: ТипПоля!;

ИмяПоля2: ТипПоля2;

ИмяПоляЫ: ТипПоляЫ; end;

Затем объявляются переменные соответствующего типа.

Var

ИмяПеременной: ИмяТипа;

Например:

type avto=record

number: integer; { номер автомобиля }

marka: string[20]; { марка автомобиля }

fio: string[40]; { фамилия, инициалы владельца }

address: string[60]; { адрес владельца } end; var m,v: avto;

Можно задать в программе типизированную константу типа записи, опре­делив значения каждого из полей. Например, для типа avto можно объявить константу:

Значения полей записи могут использоваться в выражениях. Обращение к значению поля осуществляется с помощью имени переменной и имени по­ля, разделенных точкой. Такая комбинация называется составным именем. Например, чтобы получить доступ к полям записи avto, надо записать:

m.number, т.marka, т.fio, m.address

Составное имя можно использовать везде, где допустимо применение типа поля. Для присваивания полям значений используется оператор присваи­вания.

Например:

m.number:=1964; m,marka:='Audi — 100'; m.fio:= 'Федорова Н.В.'; m.address:='y^. Красина 53 к.1 — 73';

Составные имена можно использовать в операторах ввода/вывода:

readln(m.number,m.marka,m. fio,m.address) ;

write(m.number:4,m.marka:lO.ra.fio:13,m.address:23);

Обратите внимание — нельзя использовать в операторах ввода/вывода за­пись целиком (как и массив).

Например:

writeln(m) { ошибочная инструкция }

Однако допускается применение оператора присваивания к записям в це­лом, если они имеют один и тот же тип:

После выполнения этого оператора значения полей записи v станут равны значениям соответствующих полей записи т.

В ряде задач удобно пользоваться массивами из записей. Их можно описать, например, следующим образом:

type person = record

fio: string[20];

age: 1..99;

prof: string[30] ; end; var list :array [1 . . 50] of person;

Обращение к полям записи имеет несколько громоздкий вид. Для решения этой проблемы в языке Turbo Pascal имеется оператор with, в виде:

with ПеременнаяТипаЗапись do Оператор; { обычно составной оператор }

Один раз указав переменную типа запись в операторе with, можно работать с именами полей как с обычными переменными.

Например:

with m do

begin

number:=1964 ; marka:='Audi - 100';

address :='ул. Красина 53 к.1 — 73'; end;

Записи часто используются при работе с динамическими структурами дан­ных и для организации файлов записей на дисках. Обо всем этом речь пой­дет в следующих главах. Применение записей может улучшить исходный текст программы, если в ней используются переменные, которые можно объединить в группы по какому-либо признаку. Например, разумно исполь­зовать записи для описания комплексных чисел или координат точки на плоскости или в пространстве.

type complex=record

re:real; { действительная часть } ira:real; { мнимая часть } end;

var a,b,c: complex; { a,b,c — переменные типа complex } begin

a.re:=6.8; a.im:=l.6;

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

Записи часто применяются для работы с датами (день, месяц, год) или от­резками времени (часы, минуты, секунды). В большинстве современных языков программирования есть специальные типы данных для работы с да­той и временем, однако в Turbo Pascal все действия с датой и временем приходится программировать вручную.

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

Для решения задачи введем тип записи pupil (ученик) для описания сведе­ний об учащихся, а затем объявим массив а, состоящий из 10 записей типа pupil (листинг 11.1).

[Листинг 11.1. Пример использования массива записей

type pupil = record { описание типа записи }
name: string[10]; { имя }
surname: string[20]; { фамилия }
school: integer; { школа }
class: byte; { класс }

end;

var school:array[1.,10]of pupil; n: 1 .. 10; с:byte;

procedure input_data;

{ процедура ввода данных — используем составные имена } begin

writeln('Введите данные №', п, ' :');

write('Ваше имя ?'); readln(school[n].name);

write (' Фамилия ?'); readln(school[n].surname);

write (' и класс ?'); readlnfschool[n].class);

writeln; end;

procedure write_data;

{ вывод на экран содержимого текущей записи — используем оператор with } begin

with school[n] do begin

writeln('Имя :',name); writeln('Фамилия: ',surname); writeln('Школа: ',school); writeln('Класс: ',class);

end; end; begin { основная программа }

for n:=l to 10 do input_data;

writeln;

writeln(' Вьшод данных о 5 ученике :');

writeln; n:=5; write_data;

writeln(' Вьшод данных по номеру класса :')/writeln;

writeln{' Задайте номер класса :'); readln(c);

for n:=l to 10 do if school[n].classic then write_data;

readln;

. end.

"

Записи с вариантами

Записи, имеющие строго определенную структуру, весьма ограничены по возможностям применения. Однако в языке Turbo Pascal есть возможность задать тип записи, содержащий несколько вариантов структуры. Такие записи называются записями с вариантами и являются средствами объеди­нения записей, которые похожи, но не идентичны по форме.

Записи с вариантами состоят из фиксированной и вариантной частей.

Фиксированная часть задается так же, как и в простых записях. Вариантная часть формируется с помощью оператора case ... of и может состоять из нескольких вариантов. Оператор задает особое поле записи — поле призна­ка, которое определяет, какой из вариантов в данный момент будет активи­зирован. Значением признака в каждый текущий момент выполнения про­граммы должна быть одна из расположенных в операторе case констант. Константа, служащая признаком, задает вариант записи и называется кон­стантой выбора.

В любой записи может быть только одна вариантная часть, и, если она есть, она должна располагаться за всеми фиксированными полями. Имена полей должны быть уникальными в пределах той записи, где они объявлены. Од­нако, если записи содержат поля-записи, т. е. вложены одна в другую, име­на могут повторяться на разных уровнях вложенности. Формат записи с вариантами:

type

ИмяТипа=гесогс1

фиксированная часть

case ПолеПризнака : ИмяТипа of

КонстантаВыбора! : (Поле : Тип,...);

КонстантаВыбораЫ : (Поле : Тип,...);
end; - ,,

Компоненты каждого варианта (идентификаторы полей и их типы) заклю­чаются в круглые скобки. У части case нет отдельного end, как этого следо­вало бы ожидать по аналогии с обычным оператором сазе. Одно слово end заканчивает всю конструкцию записи с вариантами. Необходимо отметить, что количество полей каждого из вариантов не ограничено.

При использовании записей с вариантами необходимо придерживаться сле­дующих правил:

П все имена полей должны отличаться друг от друга, по крайней мере, од­ним символом, даже если они встречаются в разных вариантах;

П запись может иметь только одну вариантную часть, причем вариантная часть должна размещаться в конце записи;

П если вариантная часть, соответствующая какой-либо константе выбора, является пустой, то она записывается следующим образом: константаВы-

OopaN{);.

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

Рассмотрим структуру каждого вида публикаций. П Книга (book).

Автор (author).

к \ /

Название (title).

Год (year).

Издательство (publishinghouse).

Страницы (pages).

П Статья (article).

Автор (author).

Название (title).

Год (year).

Журнал (journal).

Номер журнала (numberofjournal).

Начальная страница (begpagej).

Конечная страница (endpagej). П Реферат (paper).

Автор (author).

Название (title).

Год (year).

Номер реферативного журнала (numberofpaper).

Начальная страница (begpagerj).

Конечная страница (endpagerj).

В предложенной структуре три параметра: автор, заголовок и год повторя­ются для каждого вида публикаций, поэтому их можно вынести в фиксиро­ванную часть записи, остальные — в вариантную часть (листинг 11.2).

! Листинг 11.2. Пример использования;записей с вариантами

type

kind = (book,article,paper);

publi cat ion=re cord

{ фиксированная часть записи }

autor,title : string;

year : word;

string; word); string; byte; word); byte; word);

{ вариантная часть записи } case kindp : kind of

book : (publishinghouse pages

article : (journal numberofj ournal begpagej, endpagej paper : (numberofpaper begpagerj, endpagerj

end;

var pub: publication; j: word; begin

writeln('Выход — недопустимый вид публикации'

repeat

write('Вид публикации (0 .. 2)='); readln(j); if j in [0..2] then with pub do begin Jcindp: = kind(j) ;

write{'Автор :'); readln(autor); write('Название :');readln(title); write('Год :'>;readln(year); case kindp of

book : begin

write('Издательство :'); readln(publishinghouse) ;

writef'Объем, стр. :'); readln(pages);

j end;

article : begin

write('Название журнала :'); readln{journal); write('Номер :');readln(numberofjournal); write С'Страницы :'); readln(begpagej, endpagej); end; paper : begin

write('Номер реф. журнала :');readln(numberofpaper); write('Страницы :'); readln(begpagerj, endpagerj); end;

end; { case .. of } end; { with pub .. }

until not (j in [0..2]);(повторять до недопустимого вида публикации nd.

Файлы

' *

Мы уже знаем, что эффективным способом хранения и обработки большого количества однотипных переменных в программе являются массивы (см. гл. 4). Однако как у обычных неиндексированных переменных, так и у индексированных — массивов — есть общий недостаток: они не пригодны для долговременного хранения информации. По окончании работы про­граммы все данные будут потеряны. Результаты работы, конечно же, могут быть сохранены в виде бумажной копии — распечатаны на принтере, или некоторое время находиться на экране. Но при решении серьезных задач, связанных с вводом и/или получением большого количества данных, возни­кает необходимость их сохранения даже после того, как программа будет завершена, а компьютер выключен. В этом программисту могут помочь файлы (от английского слова file — подшивка, картотека).

Например, для расчета заработной платы сотрудников предприятия необхо­димы исходные данные на десятки или сотни человек: карточки персональ­ного учета, лицевые счета, табель рабочего времени и т. д. Зарплата рассчи­тывается ежемесячно. Данные обновляются, достигая к декабрю расчетного года максимального объема. Вводить их с самого начала каждый месяц не­разумно. Файлы обеспечивают хранение сведений, их обновление и обра­ботку. Налоговая инспекция и фонды требуют, чтобы сведения о доходах передавались как в бумажном виде, так и на "магнитных носителях" — в виде файлов на дискетах. По сути, большая часть окружающей нас ин­формации, в том числе и личные сведения о любом человеке, хранится как файлы.

Файл — это набор данных, хранящихся во внешней памяти компьютера (на жестком диске, дискете, компакт-диске и т. п.) под заданным именем.

Замечание

Любой источник или приемник информации в компьютере (клавиатура, экран, принтер и т. п.) может рассматриваться как файл (см. разд. 12. 1).

Особенности файлов:

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

2. Файл содержит элементы только одного типа (или тип его компонентов
не оговаривается). Исключение — файловый тип недопустим. Например,
можно создать файл записей или файл строк, но нельзя организовать
"файл файлов".

3. Длина файла— это число его элементов (компонентов). При создании
файла длина файла не задается заранее и ограничивается только ем­
костью устройств внешней памяти. Файл, не содержащий элементов,
называется пустым, его длина — ноль.

( Замечание )

Массивы и файлы — по сравнению с массивом файл обладает как недостатка­ми, так и достоинствами. Первые две особенности файла роднят его с масси­вом, последняя отличает и является преимуществом. Ведь особенностью мас­сива как, впрочем, множества и записи является то, что его размер должен быть известен компилятору заранее. Для файла этого не требуется — число его компонентов можно увеличивать. Но, с другой стороны, массив целиком располагается в быстродействующей оперативной памяти компьютера. Файл же, по сути, представляет собой именованное пространство на диске, а ско­рость обмена данными с винчестером, дискетой или компакт-диском гораздо ниже. Поэтому операции с файлом выполняются существенно медленнее. Для их ускорения необходимо приобретать дорогие быстродействующие внешние устройства, совершенствовать алгоритмы, уменьшая число обращений к жест­кому диску или считывать данные из "медленного" файла в "быструю" опера­тивную память, обрабатывать их там и снова записывать на диск. В отличие от массива, файлы позволяют сохранять информацию для последующего исполь­зования не только в текущей, но и в другой программе.

Файлы удобно использовать потому, что:

П многократно вводить повторяющиеся или просто большие объемы дан­ных для обработки, а потом терять их — неразумно, это трата времени. Удобно заранее создавать отдельные файлы данных, которые можно применять неоднократно;

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

П файл данных может быть подготовлен другой программой, становясь по­средником по обмену данными между двумя разными задачами;

П файл может выступать как средство связи программы с внешней средой.