Помощь - Поиск - Пользователи - Календарь
Полная версия: random(49) +1
Форум «Всё о Паскале» > Pascal, Object Pascal > Теоретические вопросы
Студент*21в.
Добрый 21 век! smile.gif

program sportlotto;

type num=1..49;
var i:1..6;loto:num;

begin randomize;
for i:=1to 6do
begin
loto:=random(49)+1;
writeln('Nr.',i:2,loto:6)
end
end.

В общем эта программа имеет недостаток в том, что не все числа могут выпасть разными. Но не это мне важно!
Мне важно узнать о функции "random". Мне не понятно почему "+1"? Для чего "+1"?
P.S. Программа из университетского учебника.
TarasBer
Потому что рандом(н) даёт число от 0 до н-1
sheka
А мне очень нравится пример из DRKB. Правда он здесь уже в моей интерпритации. smile.gif
procedure FillVariation(var variation:string);
var
i: integer;
begin
variation := '';
for i := 1 to 6 do
begin
insert(chr(i), variation, random(i));
end;
end;

В строку Variation записываются различные символы в различные места. А потом для того чтобы получить рандомные неповторяющиеся значения достаточно сделать так: ord(Variation[i]);
Для твоего примера это может выглядеть так:


program sportlotto;

{$APPTYPE CONSOLE}

var i:1..6;q,previous: byte;
variation:string;

begin
randomize;
variation := '';
previous:=0;
for i := 1 to 6 do
begin
if i=6 then
q := previous+random((i-1)*8+9-previous)+1
else q := previous+random(i*8-previous)+1;
previous:=q;
insert(chr(q), variation, random(i));
end;

for i:=1to 6do
writeln('Nr.',i:2,ord(Variation[i]):6);
readln;
end.


Хотя они тут не очень уж и случайные получились...
volvo
По мне - так вот это проще будет:
var
s: set of byte;
i, X: byte;
begin
{ Randomize }
s := [];
for i := 1 to 6 do
begin
repeat
X := random(49) + 1;
until not (X in s);
writeln('#', i:2, ' = ', X);
s := s + [X];
end;
end.
Lapp
Мне тоже очень нравится пример из DRKB, который Sheka привел, очень элегантно. Уже который раз его вижу, и всякий раз восторгаюсь )). Я обычно не вспоминаю его в нужный момент и делаю, как в примере volvo. Но вот сейчас вставил счетчик внутрь repeat, и вышло, что полное количество повторений колеблется примерно от одной тысячи до двух (при диапазоне 256). Конечно, это не значит, что метод DRKB в 6 раз эффективнее (1500/250), ибо в нем используются сдвиги, которые, конечно, значительно медленнее, чем операции с множествами, но все равно здорово )). Особенно, если учесть, что вся процедура производится в начале, а потом лишь чтение значений. Тут тоже есть капля дегтя: памяти идет больше (на данные - в 8 раз)..

Оба метода применимы только для чисел, не превосходящих 255 (и DRKB начинается с 1). Для расширения метода DRKB на больший диапазон нужно реализовать вставление элементов в массив (что несложно), а второй метод потребует практически полной реализации множеств (что, на мой взгляд, сложнее). И еще - на большем диапазоне эффективность второго метода еще упадет (количество повторений увеличится непропорционально). Интересно было бы сравнить, однако.. smile.gif
Студент*21в.
Цитата(TarasBer @ 9.04.2010 12:13) *

Потому что рандом(н) даёт число от 0 до н-1

Спасибо!
Lapp
Да, и еще один важный момент (кстати, в тему)).. Вот тут:
Цитата(sheka @ 10.04.2010 1:37) *

пример из DRKB. Правда он здесь уже в моей интерпритации. smile.gif
  ...
insert(chr(i), variation, random(i));

- по идее надо делать так:
      insert(chr(i), variation, random(i)+1);

Эту ошибку легко пропустить, поскольку Insert(c,s,0) дает ровно такой же результат, как и Insert(c,s,1). Sheka, скажи - это ошибка из твоей интерпретации или оригинальная?
С одной стороны, может показаться, что разницы нет - позиции же все равно случайные! Но на самом деле, это компрометирует случайность. Например, последним элементом в строке всегда будет #1 - а это неправильно. В процессах, где случайность является ключевой, это может привести к странным эффектам, и найти их причину будет непросто..
Lapp
Цитата(Lapp @ 10.04.2010 8:13) *
на большем диапазоне эффективность второго метода еще упадет (количество повторений увеличится непропорционально).
Я, похоже, был не совсем прав.. Эффективность действительно падает, но совсем несильно. При диапазоне n=100,000 отношение числа повторений к размеру диапазона равно примерно 11, а при n=1,000,000 оно достигает где-то 13. При n=10,000,000 получается что-то около 16, а дальше я считать не стал - очень долго smile.gif. Вот прога, если кому интересно. Разумеется, это не для TP )).

const
n= 1000000; // диапазон

var
s: array[0..n]of integer;
i,x,l: LongInt;

begin
Randomize;
for i:=0 to n do s[i]:=0;
l:=0;
for i:=1 to n do begin
repeat
x:= random(n+1);
Inc(l)
until s[x]=0;
s[x]:= 1;
end;
WriteLn;
WriteLn('Repeatitions: ',l);
WriteLn('Efficiency: ',(l/n): 3 : 1);

;ReadLn
end.
sheka
Цитата
По мне - так вот это проще будет
Я так тоже делал, пока не нашел Реализацию через символы(искал ее потому, что думал, что этот способ не рациональный smile.gif )

Цитата
последним элементом в строке всегда будет #1
А я то думал в чем же ошибка)

Вот оригинал: оказывается я только переименовал переменные lol.gif
Цитата
type 
arr = array[1..255] of integer;

procedure FillArray(var A: arr; n: integer);
var
i: integer;
s: string;
q: byte;
begin
randomize;
s := '';
for i := 1 to n do
begin
q := random(i);
insert(chr(i), s, q);
end;
for i := 1 to n do
begin
A[i] := ord(s[i]);
end;
end;


DRKB качается только старая версия)

Добавлено через 8 мин.
Кстати, а как сделать Случайный рандом способом DRKB?
Студент*21в.
Цитата(volvo @ 10.04.2010 4:16) *

По мне - так вот это проще будет:
var
s: set of byte;
i, X: byte;
begin
{ Randomize }
s := [];
for i := 1 to 6 do
begin
repeat
X := random(49) + 1;
until not (X in s);
writeln('#', i:2, ' = ', X);
s := s + [X];
end;
end.


Volvo, Ваш код лучше чем в книге! Там вот так:

program lotto1;

uses crt;
const
n=6;
type
lotto=set of 1..49;
var
L:lotto;
k:integer;
i:1..n;
z:1..49;
ok:boolean;

begin
randomize;
L:=[]; {Инициализация множества}
for i:=1to n do
{Цикл выполняется 6 раз - Количество цифр в результате}
begin
repeat
z:=random(49)+1; {Генерация случайных чисел}
if z in L then ok:=false {Определение вхождения сгенерированного числа в множество}
else
begin {Присоединение нового числа}
L:=L+[z];
ok:=true
end;
until ok; {Цикл repeat повторяется до тех пор, пока ok имеет значение false}
end;
clrscr;
{Вывод шести различных случайных чисел из 49}
for k:=1to 49do if k in L then write(k:4);
end.

sheka
Цитата
Там вот так:
Ого, как намудрили)
TarasBer
Цитата
 

repeat
X := random(49) + 1;
until not (X in s);




Дык это ж потенциально бесконечный алгоритм. Кто его знает, как рандом себя поведёт.
Я честно не знаю, стоит ли доверять таким вещам.
Archon
Цитата(sheka @ 10.04.2010 3:37) *

Для твоего примера это может выглядеть так:


program sportlotto;

{$APPTYPE CONSOLE}

var i:1..6;q,previous: byte;
variation:string;

begin
randomize;
variation := '';
previous:=0;
for i := 1 to 6 do
begin
if i=6 then
q := previous+random((i-1)*8+9-previous)+1
else q := previous+random(i*8-previous)+1;
previous:=q;
insert(chr(q), variation, random(i));
end;

for i:=1to 6do
writeln('Nr.',i:2,ord(Variation[i]):6);
readln;
end.


Хотя они тут не очень уж и случайные получились...
Они действительно не очень случайные. За счет того, как ты генерируешь q. На первой итерации, оно не может быть больше 8, например. То есть число до 8 в выборке есть всегда, а это ошибка. Но этот алгоритм из DRKB можно использовать для того, что-бы перемешать числа от 1 до 49 и взять первые 6 =)

Кстати, для перемешивания чисел можно использовать вот такой алгоритм (в нем нет ресурсоемких insert-ов):
procedure Shuffle(var Arr: array of Integer);
var
i, k, Temp: Integer;
begin
for i := High(Arr) downto 0 do begin
k := Random(i + 1);
Temp := Arr[i];
Arr[i] := Arr[k];
Arr[k] := Temp;
end;
end;
Если функцию немного подправить, можно перемешивать только часть массива (например, сделать выборку из 6 элементов).
volvo
Цитата
это ж потенциально бесконечный алгоритм. Кто его знает, как рандом себя поведёт.
Не надо вырывать строки из программы. Там было написано вот это:
  for i := 1 to 6 do { <--- Цикл для 6-ти значений !!! }
begin
repeat
X := random(49) + 1;
until not (X in s);

. Где потенциальная бесконечность? Чуть дольше будет работать - это возможно. Но бесконечно - не будет этого никогда. Если б я написал for i := 1 to 50 do - вот тогда было бы бесконечно.

Цитата
не знаю, стоит ли доверять таким вещам.
Равно как и любым другим вещам. Не нравится - не пользуйся. Мне нравится - я пользуюсь. Ни разу бесконечный цикл не наблюдал от этой конструкции. Если бы стояла задача написать супер-оптимизированную программу под жесткий RealTime, естественно, писАлось бы по-другому. Но для учебной программы - почему нет? Причем я сразу написал:
Цитата
По мне - так вот это проще будет
, никому ничего не навязывал и не собираюсь. У каждого своя голова на плечах.
TarasBer
> Где потенциальная бесконечность?

Где гарантия, что рандом не будет каждый раз возвращать одно число, которое уже занято? Компьютерный рандом неидеален, что он может выкинуть - я не знаю. Теоритеческому рандому я и то больше доверяю, в том смысле, что вероятность того, что алгоритм проработает больше секунды, меньше вероятности сбоя компьютера.
Client
Сори что вмешиваюсь, НО...
TarasBer, а что ты не привел код, которому доверяешь?
для 6 чисел из 49 вариантов ничего криминального, да и для 30 чисел этого же диапазона рано или поздно множество заполнится.
P.S. вопрос про код - это не вопрос
TarasBer
> TarasBer, а что ты не привел код, которому доверяешь?

Меня код Archonа устраивает.

> да и для 30 чисел этого же диапазона рано или поздно множество заполнится.

Гарантируешь? Всё, что тут можно сказать - это "для идеального рандома массив заполнится не более, чем за такое-то время с такой-то вероятностью". Тут же даже рандом неидеален и хз как себя поведёт.
volvo
Цитата
Где гарантия, что рандом не будет каждый раз возвращать одно число, которое уже занято? Компьютерный рандом неидеален, что он может выкинуть - я не знаю.
Я про компьютерный рандом ничего не знаю и знать не хочу. Меня "сферические кони в вакууме" как-то мало интересуют. Паскалевская функция Random возвращает с приблизительно равной вероятностью числа от (начала_интервала) до (конца_интервала-1). Где вероятность того, что рандом будет постоянно возвращать одно и то же число (если только он не вырожден как Random(1)) ? Чему она равна?

Цитата
Гарантируешь?
Гарантирую. Точно с той же уверенностью, с которой ты говоришь, что код МОЖЕТ привести к вечному циклу. Я не говорю "может", я говорю ДА. Вопросы еще будут?

Цитата
Тут же даже рандом неидеален и хз как себя поведёт.
Это твои личные фантазии. Никогда за почти 2 десятка лет Random не вел себя иначе чем так, как он него требовалось. Он ГАРАНТИРОВАННО (могу еще побольше шрифт сделать) возвращает последовательность, распределенную равномерно (это проверялось мной лично неоднократно на выборках любого размера - от минимального до огромного). Это и есть гарантия того, что вечного цикла не будет никогда.

P.S. Ну, а ты можешь с чистой совестью прекратить заниматься программированием. Ибо неидеален Random, неидеальны компиляторы, неидеальны процессоры, в атмосфере много возмущений, вспышки на Солнце. Неровен час, и простейший HelloWorld приведет к ядерной атаке...
TarasBer
> Я про компьютерный рандом ничего не знаю и знать не хочу.

Но пользуешься им. То есть ты пользуешься чем-то, про устройство чего ничего не желаешь знать, просто внушая себе его надёжность? Это плохо.

> Меня "сферические кони в вакууме" как-то мало интересуют.

А это не сферический, это тот, который используется в программе.

> Где вероятность того, что рандом будет постоянно возвращать одно и то же число (если только он не вырожден как Random(1)) ? Чему она равна?

Это я задал вопрос. Где гарантия того, что так не будет?

> Никогда за почти 2 десятка лет Random не вел себя иначе чем так, как он него требовалось.

Да? Рандом имеет свойство зацикливаться. Какой цикл у паскалевского рандома?

> это проверялось мной лично неоднократно на выборках любого размера - от минимального до огромного

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

> Это твои личные фантазии.P.S. Ну, а ты можешь с чистой совестью прекратить заниматься программированием...

Остынь.

Добавлено через 19 мин.
http://ru.wikipedia.org/wiki/Линейный_конгруэнтный_метод

Цитата

При этом длина периода равна m тогда и только тогда, когда:
НОД (c, m) = 1 (то есть c и m взаимно просты);
a - 1 кратно p для всех простых делителей p числа m;
a - 1 кратно 4, если m кратно 4.



Borland Delphi, Virtual Pascal m=232 a=134775813 c=1

Условие на НОД выполнено
условия 2 и 3 тоже

Да, RandSeed действительно пробегает все значения от 0 до 2^32-1.
В данном случае это гарантирует отсутствие бесконечного ожидания.
Хорошо, приношу свои извинения. Но без анализа что-то утверждать - голословно.

Добавлено через 1 мин.
m=2^32, а не 232, разметка не скопировалась.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.