Forum Webscript.Ru

Программирование => Теория, алгоритмы и стандарты => Тема начата: scientist от 27 Января 2004, 22:18:28

Название: Изучаем С. Урок 2.
Отправлено: scientist от 27 Января 2004, 22:18:28

Каким алгоритмом можно реализовать на языке С выбор случайного числа? Возможно ли сгенерировать идеальный алгоритм, который бы выдавал идеально-случайные последовательности чисел?

Название: Изучаем С. Урок 2.
Отправлено: Xander от 27 Января 2004, 23:15:11

нельзя.

Название: Изучаем С. Урок 2.
Отправлено: scientist от 27 Января 2004, 23:33:08

Почему?

Название: Изучаем С. Урок 2.
Отправлено: Макс от 28 Января 2004, 00:23:14

языки программирования используют генератор псевдо-случаных последовательностей.
Для реализации действительно случайной последовательности используются специальные микросхемы.

PS
(AFAIK)

Название: Изучаем С. Урок 2.
Отправлено: scientist от 28 Января 2004, 00:29:45

А по какому принципу работают специальные микросхемы. Какой алгоритм отбора случайного числа?

Название: Изучаем С. Урок 2.
Отправлено: Макс от 28 Января 2004, 00:34:05

судя по тем источникам, которые я когда-то читал, там используются случайные физически процессы (например белый шум).
Такие микросхемы используются в крупных криптографических системах (например у военных). Так что алгоритмы простым смертным недоступны :)

Название: Изучаем С. Урок 2.
Отправлено: Макс от 28 Января 2004, 00:36:08

а вообще пользуйся яндексом и гуглом.
Поиск по словам:
 - генератор случайной последовательности
 - генератор псевдослучайной последовательности

Название: Изучаем С. Урок 2.
Отправлено: ThE0ReTiC от 28 Января 2004, 12:26:00

Цитировать

Макс:
случайные физически процессы (например белый шум).

Скорее розовый
Белый шум можно упорядочить с точки зрения формальной логики
правда розовый реализовать сложнее

Название: Изучаем С. Урок 2.
Отправлено: scientist от 28 Января 2004, 16:47:59

Хорошо, идеальный процесс нам неудасться сымитировать здесь программно, тогда остается процесс генерации псевдо-случайных чисел. Какой алгоритм позволяет добиться наиболее сложного(если хотите - завуалированного) процесса отбора случайного числа посредством банальных операторов логики, таких как OR, XOR, AND (Аналоги на С: ||, !=, <=, ==, >=, && и другие)?

Название: Изучаем С. Урок 2.
Отправлено: Макс от 28 Января 2004, 17:23:11

scientist
а не проще использовать возможности, которые предоставляет язык ? В с++ по любому есть (хотя я его не знаю) функция, возвращающая случайное число из заданного диапазона.

Название: Изучаем С. Урок 2.
Отправлено: Yukko от 28 Января 2004, 18:00:51

ИМХО, максимализм... из разряда: я где-то читал, что средствами языка получается псевдослучайная последовательность, меня не устраивает псевдо... мне надо

Цитировать

добиться наиболее сложного

, а надо сначала задаться вопросом зачем.

Название: Изучаем С. Урок 2.
Отправлено: scientist от 28 Января 2004, 20:33:59

Затем, чтобы сгенерировать псевдо-случайное число, которое будет уникальным с точки зрения наблюдающих. Например, игровой автомат.

Макс
Вот хорошая  информация (http://algolist.manual.ru/maths/generator/index.php) по генераторам случайных чисел. Как правило, зарезервированных функций в языке недостаточно, т.к. такие генераторы принято считать "грязными". Наиболее чистые и равномерные последовательности случайных чисел получаются в результате сложных алгоритмов, требующих значительных вычислительных мощностей.

Название: Изучаем С. Урок 2.
Отправлено: Макс от 28 Января 2004, 22:26:04

Цитировать

scientist:
Затем, чтобы сгенерировать псевдо-случайное число, которое будет уникальным

именно уникальное или все же случайное ?

Название: Изучаем С. Урок 2.
Отправлено: scientist от 13 Февраля 2004, 04:43:51

Макс, ты прав, идеальных чисел нет в генераторах.

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

Название: Изучаем С. Урок 2.
Отправлено: metton от 13 Февраля 2004, 19:16:19

scientist

Цитировать

Наиболее чистые и равномерные последовательности случайных чисел

Мы вообще о чём говорим? Что значит ЧИСТЫЕ (!) и РАВНОМЕРНЫЕ (!) СЛУЧАЙНЫЕ (!!!) последовательности? Это что-то типа горько-солёная клубника... имхо

Название: Изучаем С. Урок 2.
Отправлено: FreeSpace от 13 Февраля 2004, 20:28:05

scientist имел в виду дисперсию или среднеквадратическое отклонение, которое в идеале равно, если не ошибаюсь, единице.
[off]Математики, поправьте.[/off]
Это значит, что вероятность появление определенного числа из диапазона возможных значений одинакова для всего этого диапазона.

Название: Изучаем С. Урок 2.
Отправлено: metton от 13 Февраля 2004, 21:36:03

Понял, тады извиняюсь за невежество :rolleyes: