Глава 38. Задание " Г "

Книга адресована школьникам средних и старших классов, желающим испытать себя в «олимпийских схватках». Может быть полезна студентам-первокурсникам и преподавателям информатики.

Модераторы: Oleg_D, Модераторы

Глава 38. Задание " Г "

Сообщение Герман » 16.11.2016 23:39:29

Строка:

v:= (v+1+Random(2)) mod 3;

в:
Код: Выделить всё
function PassWord_3: string;
var S: string; { результат }
v: integer; { вариант очередного символа }
C: char; { очередной символ }
begin
S:='';
v:= Random(3);
while Length(S)<8+Random(5) do begin
case v of
0: C:= Char(Random(10)+Ord('0'));
1: C:= Char(Random(26)+Ord('a'));
2: C:= Char(Random(26)+Ord('A'));
end;
S:= S+C;
v:= (v+1+Random(2)) mod 3;
end;
PassWord_3:=S;
end;


Ну очень интересно, сколько времени ушло на то, чтобы найти эту формулу.
Герман
новенький
 
Сообщения: 26
Зарегистрирован: 27.10.2016 11:11:41

Re: Глава 38. Задание " Г "

Сообщение Oleg_D » 17.11.2016 15:06:53

Пара минут, наверное. Вы и сами скоро этому научитесь, а логика такова.
Имеем исходное число V, значение которого лежит в диапазоне 0..2 (0, 1, 2). Из него случайным образом надо получить другое число в этом же диапазоне. Это можно сделать прибавлением любого числа, не кратного трём (ноль прибавлять не имеет смысла). Стало быть, имеет смысл прибавить либо 1, либо 2 (либо 4, 5, 7, 8 …). Отсюда выражение 1+Random(2).
Разумеется, после сложения результат может оказаться больше 2, поэтому берём остаток от деления на 3.

Добавлено спустя 19 часов 37 минут 1 секунду:
Вот ещё один вариант решения той же проблемы: сформировать случайное число, отличное от текущего значения V:
var V, N : integer;
. . .
repeat N:= Random(3) until N<>V;
V:= N;
-----
Кстати, в нашей Галактике нередко случаются задачи, в которых надо формировать псевдо-случайные числа или их последовательности в соответствии с некоторыми требованиями. Например, сгенерировать случайное число, принадлежащее некоторому множеству S:
repeat N:= Random(100) until N in S;
Или не принадлежащее ему:
repeat N:= Random(100) until not (N in S);

В этой связи предлагаю всем желающим задачу: написать процедуру, выводящую на экран при каждом своём вызове группу из пяти чисел в диапазоне 0..99 так, чтобы числа следовали по возрастанию (или по убыванию). Например:
1) 18 31 40 90 91
2) 6 7 54 70 81
3) 49 77 89 95 97
и т.д.
Oleg_D
постоялец
 
Сообщения: 386
Зарегистрирован: 09.05.2011 11:28:36

Re: Глава 38. Задание " Г "

Сообщение bormant » 18.11.2016 13:27:55

Код: Выделить всё
procedure R5;
const u=100; n=5;
var a, i: Integer;
begin
  a:=-1;
  for i:=n-1 downto 0 do begin
    a:=a+1+Random(u-1-a-i); Write(' ',a);
  end; WriteLn;
end;
Хоть и просится на первый взгляд:
Код: Выделить всё
procedure R5;
const u=100; n=5;
var a, p, i: Integer;
begin
  i:=n; a:=-1;
  repeat
    p:=a; repeat a:=p+1+Random(u-p) until a<=u-i;
    Write(' ',a); Dec(i);
  until i=0; WriteLn;
end;
Аватара пользователя
bormant
постоялец
 
Сообщения: 369
Зарегистрирован: 21.03.2012 11:26:01

Re: Глава 38. Задание " Г "

Сообщение Oleg_D » 18.11.2016 20:07:41

Первый вариант проверил -- работает. Но возникло сильное подозрение, что генерируемые числа чаще будут смещаться в бОльшую сторону. Из любопытства взялся проверить. Заодно проверил и свой вариант генерации такой последовательности. В представленной ниже программе формируется массив с плотностью распределения чисел в интервале 0..99. Для сокращения массива квант по оси X взят равным 5% (можно взять 2% или даже 1%).
Вот код:
Код: Выделить всё
program Bormant;

const Cu=100;   { диапазон генерируемых чисел }
      Cn=5;     { количество чисел в последовательности }
      Cq=5;     { квант для массива = 5% }
      Cr=1000;  { количество испытаний }

type TSet = set of byte;
     { массив для накопления результатов }
     TArr = array [0..Cu div Cq -1] of integer;

var Arr : TArr;  { массив для накопления результатов }

{ Накопление результатов в массиве }

procedure AddToArray(const aSet: TSet);
var i: integer;
begin
  for i:=0 to 255 do begin
    if i in aSet then Inc(Arr[i div Cq]);
  end;
end;

{ Вывод массива в файл }

procedure ShowArray(var aFile: Text);
var i: integer;
    pc : extended;
begin
  for i:= 0 to Cu div Cq - 1 do begin
    pc:= 100*(Arr[i]/(Cr*Cn));
    Writeln(aFile, i*Cq:2,'-',(i+1)*Cq-1:2, pc:5:1,' %');
  end;
end;

{ Генерация одной последовательности }

procedure _Bormant(var aSet: TSet);
var a, i: Integer;
begin
  aSet:=[]; a:=-1;
  for i:=Cn-1 downto 0 do begin
    a:=a+1+Random(Cu-1-a-i);
    aSet:= aSet + [a];
  end;
end;

{ Генерация одной последовательности }

procedure _Oleg(var aSet: TSet);
var i, n: integer;
begin
  aSet:=[];
  for i:=1 to Cn do begin
    repeat n:= Random(Cu) until not (n in aSet);
    aSet:= aSet +[n];
  end;
end;

var L: string;
    S: TSet;
    n: integer;
    F: Text;
begin
  FillChar(Arr, SizeOf(Arr), 0);
  for n:= 1 to Cr do begin
    _Bormant(S);
    AddToArray(S);
  end;
  ShowArray(Output);
  Assign(F,'Bormant.txt'); Rewrite(F);
  ShowArray(F);
  Close(F);
  Writeln('- - - - - - - - - - - - - - -');
  FillChar(Arr, SizeOf(Arr), 0);
  for n:= 1 to Cr do begin
    _Oleg(S);
    AddToArray(S);
  end;
  ShowArray(Output);
  Assign(F,'Oleg.txt'); Rewrite(F);
  ShowArray(F);
  Close(F);
  Readln;
end.

Вот результат для _Bormant
Код: Выделить всё
0- 4  1.0 %
5- 9  1.3 %
10-14  1.4 %
15-19  1.3 %
20-24  1.0 %
25-29  1.3 %
30-34  1.5 %
35-39  1.8 %
40-44  1.7 %
45-49  2.2 %
50-54  2.2 %
55-59  2.2 %
60-64  2.9 %
65-69  3.5 %
70-74  3.8 %
75-79  4.6 %
80-84  5.9 %
85-89  9.1 %
90-94 15.4 %
95-99 35.9 %

А это для _Oleg
Код: Выделить всё
0- 4  5.6 %
5- 9  5.1 %
10-14  4.5 %
15-19  5.4 %
20-24  5.2 %
25-29  4.7 %
30-34  4.8 %
35-39  4.5 %
40-44  5.1 %
45-49  5.1 %
50-54  4.8 %
55-59  5.3 %
60-64  4.9 %
65-69  4.6 %
70-74  5.0 %
75-79  5.7 %
80-84  4.7 %
85-89  5.0 %
90-94  5.0 %
95-99  5.0 %

Побочный вывод: функция Random весьма неплохо справляется с генерацией равномерного распределения :)
Oleg_D
постоялец
 
Сообщения: 386
Зарегистрирован: 09.05.2011 11:28:36

Re: Глава 38. Задание " Г "

Сообщение bormant » 18.11.2016 23:59:47

Oleg_D,
в условии не было ничего про распределение полученных 5 чисел :)
Безусловно, отсортированные 5 чисел (использование множества в этом случае -- вариант сортировки подсчетом) без повторов из диапазона 0..99 распределены более равномерно, чем из сужающегося к концу интервала.
Аватара пользователя
bormant
постоялец
 
Сообщения: 369
Зарегистрирован: 21.03.2012 11:26:01

Re: Глава 38. Задание " Г "

Сообщение Oleg_D » 19.11.2016 12:38:59

bormant писал(а):в условии не было ничего про распределение полученных 5 чисел

Согласен. Это не претензия, а констатация факта, для полноты картины, так сказать. :)

Добавлено спустя 2 минуты 1 секунду:
И, кстати, если бы потребовалась серия более чем из 5 чисел, ваш алгоритм мог бы забуксовать :(
Oleg_D
постоялец
 
Сообщения: 386
Зарегистрирован: 09.05.2011 11:28:36

Re: Глава 38. Задание " Г "

Сообщение bormant » 19.11.2016 13:19:25

Нет оснований буксовать, обратите внимание на правую границу интервала при генерации ПСЧ, она гарантированно оставляет место для ещё n-1 чисел :wink:
Аватара пользователя
bormant
постоялец
 
Сообщения: 369
Зарегистрирован: 21.03.2012 11:26:01

Re: Глава 38. Задание " Г "

Сообщение Oleg_D » 19.11.2016 13:30:35

Согласен, прошу прощения, не внимательно посмотрел. :)

Добавлено спустя 1 минуту 52 секунды:
Кстати, у нас с вами одинаковое количество сообщений на форуме (на данный момент). С чего бы это? :)
Oleg_D
постоялец
 
Сообщения: 386
Зарегистрирован: 09.05.2011 11:28:36


Вернуться в Книга "Песни о Паскале"

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

Рейтинг@Mail.ru