2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Генератор случайных чисел.
Сообщение12.09.2010, 15:28 
Аватара пользователя
Задача такова:
есть генератор случайных чисел - "Лотерея".
В каждом тираже случайно выпадают 5 чисел.
В лотерее участвуют цифры от 1 до 18, включительно.

Примеры тиражей:

Тираж № 198
Выигрышные номера: 4, 13, 8, 3, 9

Тираж № 197
Выигрышные номера: 6, 4, 8, 9, 11

Тираж № 196
Выигрышные номера: 4, 6, 12, 11, 15

Тираж № 195
Выигрышные номера: 8, 13, 6, 7, 5

Тираж № 194
Выигрышные номера: 5, 13, 12, 16, 11

Вопрос: как вычислить или маску генератора случайных чисел?
Или проще - вычислить следующую комбинацию 5 цифр, т.е. узнать как работает генератор по выходным данным?
генератор - программа, вероятно, но не точно, php/
Всего участвуют 15000 билетов, из них можно выбрать 20 билетов. Порядок выйгравших номеров значения не имеет! Т.о. выйгравших билетов может быть нескролько(если у несколькох билетов совпали цифры). Какие цифры выпадут с наибольшей вероятностью?

Напоминает разбор генератора паролей, работающего по маске... =)

 
 
 
 Re: Генератор случайных чисел.
Сообщение12.09.2010, 20:28 
Цитата:
Вопрос: как вычислить или маску генератора случайных чисел?
...
генератор - программа, вероятно, но не точно, php/

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

 
 
 
 Re: Генератор случайных чисел.
Сообщение12.09.2010, 21:48 
Аватара пользователя
e2e4
Не согласен. Существуют они да. Но с чего вы взяли что в нашей реальности? В нашей реальности повторяемость и закономерности это обыденные вещи. Солнце каждый день восходит. Атом водорода имеет валентность I. При наборе сайта dxdy.ru вы поподаете сюда и никакойто случайный сайт.
Следовательно если взять за аксиому
Цитата:
В нашей реальности повторяемость и закономерности это обыденные вещи.
то найти правильный ответ очень даже вероятно.
С большой долей вероятности этот какой-то известный метод. Просто надо их проверить и все. А основных методов чучуть с десяток.

 
 
 
 Re: Генератор случайных чисел.
Сообщение12.09.2010, 22:57 
Аватара пользователя
Pavia в сообщении #351740 писал(а):
С большой долей вероятности этот какой-то известный метод. Просто надо их проверить и все. А основных методов чучуть с десяток.
Если бы я устраивал лотерею, я бы перед каждым розыгрышем выставлял seed на основе внешнего источника энтропии.

 
 
 
 Re: Генератор случайных чисел.
Сообщение13.09.2010, 00:28 
2Antonina
Цитата:
Вопрос: как вычислить или маску генератора случайных чисел?
Или проще - вычислить следующую комбинацию 5 цифр, т.е. узнать как работает генератор по выходным данным?

Можно попробовать собирать статистику. Один человек на форуме уже пытался предсказывать случайные последовательности. :)

-- Пн сен 13, 2010 03:47:58 --

Возможно, скрытые марковские модели могут помочь...

 
 
 
 Re: Генератор случайных чисел.
Сообщение13.09.2010, 06:14 
Аватара пользователя
Pavia в сообщении #351740 писал(а):
e2e4
Не согласен. Существуют они да. Но с чего вы взяли что в нашей реальности? В нашей реальности повторяемость и закономерности это обыденные вещи. Солнце каждый день восходит. Атом водорода имеет валентность I. При наборе сайта dxdy.ru вы поподаете сюда и никакойто случайный сайт.
Следовательно если взять за аксиому
Цитата:
В нашей реальности повторяемость и закономерности это обыденные вещи.
то найти правильный ответ очень даже вероятно.
С большой долей вероятности этот какой-то известный метод. Просто надо их проверить и все. А основных методов чучуть с десяток.


обалденный ответ, супер))))
только вот вопрос, какие же методы есть??

 
 
 
 Re: Генератор случайных чисел.
Сообщение13.09.2010, 07:57 
Вот моя статья из журнала Алгоритм.

Реализация класса, размещающего элементы списка в случайной последовательности

Случайные числа находят широкое применение в таких областях как моделирование, численный анализ, программирование, принятие решений. К сожалению, библиотеки .NET Framework не содержат класс, который бы реализовывал размещение элементов списка заданного типа в псевдо-случайной последовательности. Псевдо-случайная последовательность на самом деле генерируется детерминистким алгоритмом с очень большим циклом повторяющихся элементов.

Ссылка:

(Д.Кнут Искусство программирования, Т2, 3-е издание, стр22)

Ниже приводится класс Shuffle, который реализует эту функцию.
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
using System;
using System.Collections.Generic;

namespace ShuffleNik
{
    sealed class Shuffle<T>
    {
        List<T> _list = new List<T>();

        public Shuffle(T[] list)
        {
            _list.AddRange(list);
        }

        public List<T> Next()
        {
            List<T> result = new List<T>(_list.Capacity);
            Random random = new Random();

            while (_list.Count > 0)
            {
                int i = random.Next(0, _list.Count);
                result.Add(_list[i]);
                _list.RemoveAt(i);
            }

            return (_list = result);
        }
    }
}
 


Конструктор класса Shuffle инициализирует списочную структуру, заданным массивом данных. Метод Next класса Shuffle размещает элементы исходного массива в псевдо-случайной последовательности. Метод Next класса Random, принадлежащий базовой библиотеки .NET Framework, возвращает следующее случайное число в интервале [0, c], где c – текущее количество элементов списка. К результирующему списку добавляется элемент исходного списка, проиндексированный полученным случайным числом. Далее этот элемент удаляется из исходного списка. Данный цикл продолжается до тех пор, пока исходный список содержит элементы.
Класс Program содержит три примера использования класса Shuffle. Все три примера генерируют 100 случайных последовательностей целых, вещественных чисел и строк, соответственно.
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
using System;

namespace ShuffleNik
{
    class Program
    {
        static void Main(string[] args)
        {
            ////////////////////////////////////////////////////////////////////////////////
            Shuffle<int> shuffleInt = new Shuffle<int>(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 });
            for (int i = 0; i < 100; i++)
            {
                Console.Write("shuffle[{0}] = ", i + 1);
                foreach (int j in shuffleInt.Next())
                {
                    Console.Write("{0} ", j);
                }
                Console.WriteLine("");
            }
            Console.Write("=================================================");
            Console.ReadLine();

            ////////////////////////////////////////////////////////////////////////////////
            Shuffle<double> shuffleFloat =
                new Shuffle<double>(new double[] { 1.56, 2.86, 3.57, 4.56, 5.98, 6.35, 7.87, 8.69, 9.38, 10.57, 11.57, 12.74, 13.03, 14.46, 15.92 });
            for (int i = 0; i < 100; i++)
            {
                Console.Write("shuffle[{0}] = ", i + 1);
                foreach (double j in shuffleFloat.Next())
                {
                    Console.Write("{0} ", j);
                }
                Console.WriteLine("");
            }
            Console.Write("=================================================");
            Console.ReadLine();
           
            ////////////////////////////////////////////////////////////////////////////////
            Shuffle<Customer> shuffleCustomer =
                new Shuffle<Customer>(new Customer[] { new Customer("Sidorov"),
                                                       new Customer("Petrov"),
                                                       new Customer("Ivanov"),
                                                       new Customer("Strunov"),
                                                       new Customer("Klinkin"),
                                                       new Customer("Mironov"),
                                                       new Customer("Smirnov")
                                                     });
            for (int i = 0; i < 100; i++)
            {
                Console.Write("shuffle[{0}] = ", i + 1);
                foreach (Customer customer in shuffleCustomer.Next())
                {
                    Console.Write("{0} ", customer.Name);
                }
                Console.WriteLine("");
            }
            Console.Write("=================================================");
            Console.ReadLine();
        }
    }
}

Класс Customer определяется так

namespace ShuffleNik
{
    class Customer
    {
        string _name;
       
        public Customer(string name){ _name = name; }
       
        public string Name
        {
            get{ return _name; }
        }
    }
}
 

 
 
 
 Re: Генератор случайных чисел.
Сообщение14.09.2010, 12:31 
Аватара пользователя
Если автор программы обладает хотя бы минимальной квалификацией - то никак. В этом случае он не забудет поставить randomize перед выдачей очередного тиража, тем самым изменив начальные установки ГСЧ на, скажем, число миллисекунд на часах на момент запроса (и восстановление практически невозможно) или вывод аппаратного ГСЧ (такие есть на некоторых материнских платах от Intel и др., и задача становится неразрешимой даже теоретически).
Если начальная установка ГСЧ сохраняется между тиражами (что может быть, только если тиражи идут один за другим в одном прогоне программы, сохранять это число между запусками и вредно, и трудоёмко), задача может быть решена в принципе, при условии, что мы что-то о ГСЧ знаем. Если, скажем, он относится к мультипликативным x[n+1]=(a*x[n]+c) % M, то по серии значений Х можно восстановить a, c и M. Хотя эффективный алгоритм для этого я назвать не могу, а полный перебор будет крайне расточителен.

 
 
 
 Re: Генератор случайных чисел.
Сообщение14.09.2010, 12:45 
Евгений Машеров в сообщении #352299 писал(а):
тем самым изменив начальные установки ГСЧ на, скажем, число миллисекунд на часах на момент запроса (и восстановление практически невозможно) или вывод аппаратного ГСЧ

А если, например в делфи, просто используется функция генерации случайного числа, то всегда выдается одна и та же последовательность, и на всех компьютерах?

 
 
 
 Re: Генератор случайных чисел.
Сообщение14.09.2010, 14:17 
Аватара пользователя
Цитата:
Randomize
Процедура Устанавливает генератор случайного числа на следующее значение System unit

procedure Randomize ;



Описание
Процедура Randomize используется вместе с функцией Random. Она устанавливает генератор случайных чисел в его последовательность из 232 псевдослучайных чисел.

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

http://www.delphisources.ru/pages/faq/f ... e.php.html

 
 
 
 Re: Генератор случайных чисел.
Сообщение18.09.2010, 10:51 
Но, с другой стороны, можно и принудительно устанавливать переменную RandSeed, после чего результаты работы программы становятся абсолютно повторяемыми, что бывает практически весьма важно (не в лотереях, конечно).

 
 
 
 Re: Генератор случайных чисел.
Сообщение20.09.2010, 13:10 
Аватара пользователя
Можно. Скажем, для отладки весьма полезно быть уверенным, что в прежнем и в исправленном вариантах программы мы обрабатываем одни и те же данные. Но если это лотерея - сие весьма маловероятно...

 
 
 
 Re: Генератор случайных чисел.
Сообщение21.09.2010, 11:28 
Евгений Машеров в сообщении #354315 писал(а):
для отладки весьма полезно

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

 
 
 
 Re: Генератор случайных чисел.
Сообщение21.09.2010, 12:20 
А вот интересно, как соотносятся эти самые случайные числа и ошибки округления при работе с вещественными числами? Ведь комбинация этих двух рептилий может приводить к очень полезным результатам в численном анализе.

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group