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

Пусть требуется сформировать последовательность натуральных чисел от 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 применяется комбинированный тип данных — запись. Запись представляет собой наибо­лее общий и гибкий структурированный тип данных, т. к. она может быть образована из неоднотипных компонентов, и в ней явным образом выра­жена связь между элементами данных, которые характеризуют реальный объект.

. _Л

Дата добавления: 2015-11-14