Random без повтора чисел

Random без повтора чисел

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

Особенно это видно при задании узкого диапазона, например если вывести 10 элементов массива, заполнив их случайными числами в диапазоне от 0 до 9, то среди них почти всегда есть повторы. Ниже код реализации.

const
n = 10;

var
m: array [1..n] of integer;
i:integer;

begin
randomize;
for i := 1 to n do
begin
z: m[i] := random(1, 10);
write(m[i]);
end;
end.

Каков наш алгоритм, позволяющий убрать повтор чисел ? Для того,чтобы числа не повторялись, нам достаточно сделать своего рода фильтр ,который из всех случайных чисел будет брать только те,которых еще не было. Объясняю на примере массива. Смотрим последовательность.

Шаг 1.Заполняем первый элемент массива

Шаг 2.Заполняем второй элемент

Подшаг 1. Сверяем его с первым.

а) Если элементы разные, то переходим к следующему шагу.
б) Если они одинаковы ,то заполняем второй элемент еще раз до тех пор, пока они не будут неравными.

Шаг 3. Заполняем третий элемент.

Подшаг 1. Сверяем его с первым.

а) Если элементы разные, то переходим к следующему подшагу.
б) Если они одинаковы, то заполняем третий элемент еще раз до тех пор, пока они не будут неравными.

Подшаг 2. Сверяем его со вторым.

а) Если элементы разные, то переходим к следующему шагу.
б) Если они одинаковы, то заполняем третий элемент еще раз до тех пор, пока они не будут неравными.

Шаг 4. ……

Random без повтора чисел

Random без повтора чисел

На картинке изображен момент, когда шаг равен 3 и происходит сначала сравнение третьего элемента и первого, а затем третьего и второго. И таким вот образом алгоритм повторяется от первого щага до десятого. Каждый раз, когда мы делаем i шагов, мы делаем i-1 подшагов.

А теперь весь алгоритм. Для алгоритма был использован оператор goto. О нем я уже упоминал в статье выход из цикла. Итак код алгоритма

randomize;
for i := 1 to n do
begin
z: m[i] := random(1, 10);
for k := 1 to i — 1 do
if m[k] = m[i] then goto z;
end;

Полный код с выводом сгенерированных элементов массива на экран.

label z;
const
n = 10;

var
m: array [1..n] of integer;
i, k: integer;

begin
randomize;
for i := 1  to n do
begin
z: m[i] := random(1, 10);
for k := 1 to i — 1 do
if m[k] = m[i] then goto z;
end;

for i := 1 to n do
write(m[i]:3);
end.

Тот же код, но без использования метки.

const
n = 10;

var
m: array [1..n] of integer;
i, k: integer;

begin
randomize;
i := 0;
while i < n do
begin
i := i + 1;
m[i] := random(1, 10);
for k := 1 to i — 1 do
if m[k] = m[i] then
begin
i := i — 1;
break;
end;
end;

for i := 1 to n do
write(m[i]:3);
end.

На этом все. В следующий я планирую написать статью о НОД (наименшем общем делителе). Чтобы не пропустить ее вы можете подписаться на обновления с сайта. Удачи вам)

12 Replies to “Random без повтора чисел”

  1. Не за что)
    Для этого и создавался сайт
    Жаль,что в последнее время много дел,из-за чего я не успеваю писать. Но это ненадолго.
    Кстати, советую Вам подписаться ,если Вы еще не подписаны)

  2. Группа: Гости
    Публикаций: 0
    Комментариев: 0

    Здравствуйте, хотелось бы уточнить, используете ли Вы всегда только PascalABC.net для своих программ? Дело в том, что TurboPascal почему-то «ругается» на массив, когда я ввожу тот же самый код программы, что и у Вас. При запуске программы получаю сообщение об ошибке «type mismatch».

    Спасибо.

  3. Евгения,
    Здравствуйте,
    Вообще мы пишем код для PascalABC и TurboPascal, просто есть некоторые вещи, которые необходимо дописывать, если Вы хотите запустить программу через TurboPascal. Например пустой readln в самом конце любой программы (для вывода результата на экран ) или тот же самый random в TurboPascal пишеться по-другому (подробнее в статье Оператор random ). Я проверил код в TurboPascal — все работает. Не могли бы Вы прислать скриншот программы ?

  4. Грамотное использование меток приводит к тому, что код становится короче и прозрачней. Есть пара случаев, когда без меток просто не обойтись. Но здесь согласен: можно и без них. Поэтому добавил вариант без меток

  5. Данил,

    Это не деление на 3
    деление обозначается как /
    это write(m[i]:3) значит, что при выводе на экран каждому элементу массива будет даваться 3 «клетки», т.е например
    числа
    3,2,4,10,-12
    будут выведены так
    3 2 4 10-12
    делается это, чтобы числа не стояли вплотную друг к другу

  6. Способ, конечно, простой. Код небольшой — тоже хорошо. Но такой генератор неповторяющихся чисел будет работать медленно, особенно это будет заметно на больших диапазонах. Как вариант решения предлагаю следующий код: http://pastebin.com/Kz1uT17D

  7. Не кто не проверял что ли?
    Не работает же.
    i := 0;
    while i < n do
    begin
    i := i + 1;
    m[i] := random(1, 10);
    for k := 1 to i — 1 do — вот в этом месте на первой итерации всегда k=1, а i=0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *