Информативный заголовок: задачки о случайности и определённости
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Информативный заголовок: задачки о случайности и определённости - 2010-04-19 22:20:44.496666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
задачка первая. дана функция, возвращающая псевдослучайное целое число в промежутке от 1 до 7 включительно с равномерным распределением; необходимо написать функцию, возвращающую псевдослучайное целое число в промежутке от 1 до 9 включительно с распределением, как можно более близким к равномерному. для получения случайной величины запрещено напрямую пользоваться генератором псевдослучайных чисел, ограничиваясь исключитально данной функцией. иными словами, необходимо написать функцию rand_1to9, используя для генерации случайных величин исключительно функцию rand_1to7
задачка вторая. необходимо написать функцию fun(int x) такую, чтобы выполнялось равенство fun(fun(x)) = -x. тип x в данном случае - знаковое 32-х битное целое, функция должна корректно работать с как можно большим диапазоном значений из возможных
задачка третья. мы работаем с потоком неизвестной длинны, из которого по очеди считываем по одному байту; у нас есть место в памяти, достаточное для хранения одного байта, и автоматический счётчик входящих байт (в каждый момент времени мы знаем, сколько байт уже было обработано). задача: после обработки всего потока, вернуть случайный байт из потока с равномерным распределением (вероятность возвращения любого байта должна быть одинаковой). в случае, если бы у нас было достаточно памяти, мы могли бы сохранить весь поток, посчитать его длину, и выбрать случайную позицию - результат работы должен быть полностью эквивалентен такому подходу, с той лишь разницей, что памяти у нас всего байт
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-19 22:44:22.746666
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
да, пожалуй это стоит отметить. решение верное - не возражаешь, если я попрошу его удалить и дать возможность размяться остальным?
Да без проблемм.
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-19 23:02:30.146666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Родригес
1.
хорошо, хотя можно и лучше (как в смысле производительности, так и в смысле равномерности)
quote:
ORIGINAL: Родригес
3. А как для счетчика, еще пару тройку байт выделить можно?
да, пожалуй это стоит отметить. решение верное - не возражаешь, если я попрошу его удалить и дать возможность размяться остальным?
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-20 11:24:30.040000
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
хорошо, хотя можно и лучше (как в смысле производительности, так и в смысле равномерности)
Насчет производительности не спорю, а вот равномерность , мне кажется должна быть. Вечером, домой приду прогоню варианты программно, проверю.
2. Нашел решение, позволяющее охватить весь диапазон. Выкладывать или как? (Всё гениальное действительно просто)
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-20 11:48:48.600000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: Родригес
2. Нашел решение, позволяющее охватить весь диапазон. Выкладывать или как? (Всё гениальное действительно просто)
Не, подожди. Вторая задача, по-моему, наиболее интересна с точки зрения исследования местного контингента. Кругом сплошные хакеры, они должны сообразить. Или нет?
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-20 15:32:37.183333
|
|
|
_ruzmaz_
Сообщений: 105
Оценки: 0
Присоединился: 2009-08-22 18:26:07.173333
|
1. rand_1to9 = ((rand_1to7 - 1)/6)*8 + 1
2. явно не гениально), но как вариант (диапазон 0 - $FFFFFFFC)
function f(n: integer): integer;
const
nmax = MaxInt - 1;
nhalf = trunc(nmax/2);
begin
Result := 0;
if (n > 0) and (n <= nhalf) then
begin
Result := n + nhalf;
exit;
end;
if (n > nhalf) and (n <= nmax) then
begin
Result := -(n - nhalf);
exit;
end;
if (n >= -nhalf) and (n < 0) then
begin
Result := -(-n + nhalf);
exit;
end;
if (n >= -nmax) and (n < -nhalf) then
begin
Result := -n - nhalf;
exit;
end;
end;
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-20 16:07:32.766666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Родригес
Насчет производительности не спорю, а вот равномерность , мне кажется должна быть. Вечером, домой приду прогоню варианты программно, проверю.
проверь. результатами, в принципе, можно делиться сюда - заодно другие прежде чем выкладывать решение подумают над подобной проверкой
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-20 18:12:50.753333
|
|
|
a13xb
Сообщений: 17
Оценки: 0
Присоединился: 2010-03-12 06:22:14.200000
|
сегодня, на свежую голову добил #2, методом тыка.
#include <stdio.h>
/* задачка вторая. необходимо написать функцию fun(int x) такую, чтобы выполнялось равенство fun(fun(x)) = -x. тип x в данном случае - знаковое 32-х битное целое, функция должна корректно работать с как можно большим диапазоном значений из возможных */
#define ODD(x) (x & 1)
int fun (int x)
{
if (x > 0)
return ODD (x) ? x+1 : -x+1;
else if (x < 0)
return ODD (x) ? x-1 : -x-1;
else
return 0;
}
int main (int argc, char *argv[])
{
int x;
const int imax = ((unsigned) ~0) >> 1;
const int imin = imax+1;
for (x = imin; x <= imax; x++) {
if (fun (fun (x)) != -x)
printf ("%d\t0x%x\n", x, x);
if (x == imax)
break;
}
return 0;
}
для любого x, кроме imax.
quote:
2. Нашел решение, позволяющее охватить весь диапазон. Выкладывать или как? (Всё гениальное действительно просто)
если там не глобальная переменная, которая держит стейт, пока мне это кажется невозможным.
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-20 18:29:42.990000
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
если там не глобальная переменная, которая держит стейт, пока мне это кажется невозможным.
quote:
для любого x, кроме imax.
Да, да, кроме максимума.
quote:
ORIGINAL: Denaturat
quote:
ORIGINAL: Родригес
Насчет производительности не спорю, а вот равномерность , мне кажется должна быть. Вечером, домой приду прогоню варианты программно, проверю.
проверь. результатами, в принципе, можно делиться сюда - заодно другие прежде чем выкладывать решение подумают над подобной проверкой
Вызвал функцию 10 000 000 раз. Вроде достаточно равномерно.
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-21 10:24:41.853333
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Хм. Чёт я со второй задачкой не о том подумал: корень из минус единицы-то не извлечь не вылезая за пределы кольца int. Я почему-то свято верил в обратное. Мдя…
Но значит придётся обойтись без умножения на "мнимую единицу" :)
int f (int x)
{
const int bound = ((~0U >> 1) + 1) >> 1;
int y = x + (~0U >> 1) + 1;
if (abs (y) < bound) // в вызовах f (f... (f (x)) условие будет верным через раз
y = - y;
return y;
}От условия же мне ну никак не избавится.
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-21 12:46:44.880000
|
|
|
_ruzmaz_
Сообщений: 105
Оценки: 0
Присоединился: 2009-08-22 18:26:07.173333
|
quote:
ORIGINAL: Denaturat
заодно другие прежде чем выкладывать решение подумают над подобной проверкой
1. ну вот так равномерно, но не производительно)
function rand_1to9: integer;
var
x: real;
n: integer;
begin
x := (7*7*7*7*7)/9;
n := 7*7*7*7*(rand_1to7 - 1) +
7*7*7*(rand_1to7 - 1) +
7*7*(rand_1to7 - 1) +
7*(rand_1to7 - 1) +
(rand_1to7 - 1);
Result := trunc(n/x + 1);
end;
3. здесь тоже достаточно равномерно (проверял)
GetNextByte читает очередной байт из потока
EoS указывает достигнут ли конец потока
function GetRandomByte: byte;
var
i: integer;
b: byte;
begin
i := 0;
b := 0;
while not EoS do
begin
i := i + 1;
if random < 1/i then
b := GetNextByte
else
GetNextByte;
end;
GetRandomByte := b;
end;
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-21 18:10:43.096666
|
|
|
_ruzmaz_
Сообщений: 105
Оценки: 0
Присоединился: 2009-08-22 18:26:07.173333
|
quote:
Result := Random(6)+1;
надо Random(7), вместо Random(6)
Вот мой код для проверки (на delphi)
program Denaturat_problem;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
CheckCount = 100000000;
type
TCheckArray_1to7 = array [1..7] of integer;
TCheckArray_1to9 = array [1..9] of integer;
function rand_1to7: integer;
begin
Result := 1 + Random(7);
end;
function rand_1to9: integer;
var
x: real;
n: integer;
begin
x := (7*7*7*7*7)/9;
n := 7*7*7*7*(rand_1to7 - 1) +
7*7*7*(rand_1to7 - 1) +
7*7*(rand_1to7 - 1) +
7*(rand_1to7 - 1) +
(rand_1to7 - 1);
Result := trunc(n/x + 1);
end;
var
CheckArray_1to7: TCheckArray_1to7;
CheckArray_1to9: TCheckArray_1to9;
i: integer;
begin
for i := 1 to 7 do
CheckArray_1to7[i] := 0;
for i := 1 to 9 do
CheckArray_1to9[i] := 0;
Randomize;
for i := 1 to CheckCount do
begin
Inc(CheckArray_1to7[rand_1to7]);
Inc(CheckArray_1to9[rand_1to9]);
end;
for i := 1 to 7 do
WriteLn(i, ' :: ', CheckArray_1to7[i]);
WriteLn;
for i := 1 to 9 do
WriteLn(i, ' :: ', CheckArray_1to9[i]);
ReadLn;
end.
… и вот результаты
1 :: 14283784
2 :: 14286934
3 :: 14284339
4 :: 14283462
5 :: 14281777
6 :: 14287734
7 :: 14291970
1 :: 11116978
2 :: 11109196
3 :: 11115949
4 :: 11106662
5 :: 11113301
6 :: 11114107
7 :: 11110552
8 :: 11108256
9 :: 11104999
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-21 18:37:28.200000
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
надо Random(7)
Прошу прощения, моя ошибка.
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-23 17:40:06.983333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
1.
rand1_9 =
trancate ((rand1_7 + rand1_7 + rand1_7 + rand1_7 + rand1_7 + rand1_7 + rand1_7 + rand1_7 + rand1_7) / 7)
update. Тут соврал. Оставляю, чтобы другим было не павадно так врать. Правильный вариант решения:
a и b - нижняя и верхняя границы 1-ого интервала, то есть 1 и 7,
a' и b' - нижняя и верхняя границы 2-ого интервала, то есть 1 и 9,
f - плотность вероятности, для нормального распределения имеем:
f = 1 / (b - a)
f' = k * f
1 / (b - a) = k / (b' - a')
k = (b' - a') / (b - a)
k = (9 - 1) / (7 - 1) = 8 / 6 = 4 / 3
Итого,
rand1_9 = 4 / 3 * rand1_7
или на языке программирования
rand1_9 = trancate(rand1_7 * 4 / 3)
2. Без условия пока не знаю, с условием неинтересно, уже два варианта было.
3.
def exchange_needed(count):
return random() < 1 / count
def proceed_byte(b):
if exchange_needed(count):
byte = b
В правильности функции exchange_needed не совсем уверен, по-хорошему, надо бы проверить законами теории вероятностей и, возможно, уточнить, но суть всё равно будет та же: необходимо заменять хранимый байт со всё убывающей вероятностью, обратно пропорциональной количеству обработанных байт. То есть, если у нас приходит байт, то вероятность того, что нужно выбрать именно его должна быть 1/3, то есть 1/count.
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-23 18:15:43.260000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: kreol
2. Без условия пока не знаю, с условием неинтересно, уже два варианта было.
А ты попробуй. Я тут на досуге подумавши, понял что мой вариант в одной точке даёт неверные результаты. В одной или в двух, уж не помню точно, я в нескольких вариантах сочинял, и как ни крути одна-две точки, такие что f(f(x))==x остаются. Причём я вроде придумал правильный вариант, закодил по-быстрому, а он вместо результатов какой-то бред выдаёт. Всё никак не добраться не посмотреть, что ж там не так.
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-23 19:02:57.873333
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
1. Укоротил:
function rand_1to9 : integer;
var i : integer;
begin
repeat
i := (rand_1to7 * 7 + rand_1to7 -7)
until i < 46 ;
Result := i mod 9 +1 ; //
end;
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-23 22:53:44.400000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: rgo
А ты попробуй.
Ну пусть будет так:
int fun(int x) {
int y;
if (bit_is_set(x, LSB)) // if less significant bit is set
y = -x;
else
y = x;
switch_bit(y, LSB);
return y;
}
Дискляймер: я не помню, как хранятся в C целые числа, поэтому допустил, что их знак кодируется наиболее значимым битом. Если это не так, или на это нельзя расчитывать, то можно повторить тот же самый алгоритм, используя в качестве флага не один из битов числа, а его чётность, но в таком случае придётся отказаться от использования чисел maxint и minint. Впрочем, поведения функции в этих точках само по себе не определено, т.к. f(f(minint)) != -minint.
Anyway, решение скучное и некрасивое. Даёшь математическую функицю с такими свойствами!
|
|
|
|
|
RE: Информативный заголовок: задачки о случайности и определённости - 2010-04-30 10:37:08.100000
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
ORIGINAL: kreol
Anyway, решение скучное и некрасивое. Даёшь математическую функицю с такими свойствами!
F(X) = X * cos (p i* X) - X / |X| , справедливо для целых Х , не равных нулю.
Можно написать и для не только целых, но будут точки, где ф-я неопределенная.
|
|
|
|
|
|
