2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Генератор случайных чисел.
Сообщение12.09.2010, 15:28 
Аватара пользователя


09/03/06
40
Владивосток
Задача такова:
есть генератор случайных чисел - "Лотерея".
В каждом тираже случайно выпадают 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 


21/03/06
1545
Москва
Цитата:
Вопрос: как вычислить или маску генератора случайных чисел?
...
генератор - программа, вероятно, но не точно, php/

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

 Профиль  
                  
 
 Re: Генератор случайных чисел.
Сообщение12.09.2010, 21:48 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Генератор случайных чисел.
Сообщение12.09.2010, 22:57 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Генератор случайных чисел.
Сообщение13.09.2010, 00:28 
Заслуженный участник


26/07/09
1559
Алматы
2Antonina
Цитата:
Вопрос: как вычислить или маску генератора случайных чисел?
Или проще - вычислить следующую комбинацию 5 цифр, т.е. узнать как работает генератор по выходным данным?

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

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

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

 Профиль  
                  
 
 Re: Генератор случайных чисел.
Сообщение13.09.2010, 06:14 
Аватара пользователя


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


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

 Профиль  
                  
 
 Re: Генератор случайных чисел.
Сообщение13.09.2010, 07:57 


07/02/10
7
Вот моя статья из журнала Алгоритм.

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

Случайные числа находят широкое применение в таких областях как моделирование, численный анализ, программирование, принятие решений. К сожалению, библиотеки .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 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Генератор случайных чисел.
Сообщение14.09.2010, 12:45 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Генератор случайных чисел.
Сообщение14.09.2010, 14:17 
Заслуженный участник
Аватара пользователя


11/03/08
9541
Москва
Цитата:
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 
Заслуженный участник


11/05/08
32166
Но, с другой стороны, можно и принудительно устанавливать переменную RandSeed, после чего результаты работы программы становятся абсолютно повторяемыми, что бывает практически весьма важно (не в лотереях, конечно).

 Профиль  
                  
 
 Re: Генератор случайных чисел.
Сообщение20.09.2010, 13:10 
Заслуженный участник
Аватара пользователя


11/03/08
9541
Москва
Можно. Скажем, для отладки весьма полезно быть уверенным, что в прежнем и в исправленном вариантах программы мы обрабатываем одни и те же данные. Но если это лотерея - сие весьма маловероятно...

 Профиль  
                  
 
 Re: Генератор случайных чисел.
Сообщение21.09.2010, 11:28 
Заслуженный участник


11/05/08
32166
Евгений Машеров в сообщении #354315 писал(а):
для отладки весьма полезно

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

 Профиль  
                  
 
 Re: Генератор случайных чисел.
Сообщение21.09.2010, 12:20 
Заблокирован


18/09/10

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group