Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Про алгоритм rand, srand, И про seed... 
:(
    Опции темы
bugmenot
Дата 14.6.2009, 01:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 135
Регистрация: 3.7.2006

Репутация: нет
Всего: 1



Я знаю, что в Visual C++ эти функции заданы примерно так:

Код

unsigned int seed;

void srand(unsigned int new_seed)
{
    seed = new_seed;
}

int rand()
{
    return ((seed = seed * 214013 + 2531011) >> 16) & 0x7FFF;
}


А это значит, что seed после каждого вызова rand будет равняться:
(seed*214013+2531011)&0xFFFFFFFF

И не вызывая rand, мы можем узнать, какой seed будет, например, через 5 вызовов.
А вопрос у меня такой: зная текущий seed, можно ли узнать предыдущий?


С математической точки зрения:
a = (b*214013+2531011) mod 0x100000000
Зная b, можно легко узнать a
А вот зная только a, можно узнать b? (Не делая данную операцию 0xFFFFFFFF раз smile)
P.S. 0x100000000 равняется 4294967296

В Википедии про это тоже что-то написано, но я ничего не понял %)
http://ru.wikipedia.org/wiki/%D0%9B%D0%B8%...%82%D0%BE%D0%B4
--------------------
доска объявленийвсе о горных велосипедах 
PM MAIL   Вверх
Pavia
Дата 14.6.2009, 02:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 418
Регистрация: 6.12.2008

Репутация: 11
Всего: 12



a = (b*214013+2531011) mod 0x100000000
Тут нет однозначности есть множество вариантов ответов.

Возможно два случая 

(b*214013+2531011) меьше 0x100000000 и тогда (b*214013+2531011) равно a
И второй вариант  (b*214013+2531011) больше 0x100000000 и тогда  с учетом что и b тоже 32 бита.
(b*214013+2531011) =a+I*0x100000000
(0xFFFFFFFF*214013+2531011)=0x343FD00235AC6  откуда I от 0 до 214014

b=(a+I*0x100000000 - 2531011) / 214013
В висуале идет вычисления в long формате в отличии от твоего кода. 
PM MAIL   Вверх
bugmenot
Дата 15.6.2009, 22:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 135
Регистрация: 3.7.2006

Репутация: нет
Всего: 1



Например b=123456
a = (123456*214013+2531011) & 0xFFFFFFFF = 0x626F9F803 & 0xFFFFFFFF = 0x26F9F803

А теперь ситуация, в которой мы знаем только то, что a=0x26F9F803 (653916163)
Можно ли узнать b?
По форумуле: b=(a+I*0x100000000 - 2531011) / 214013
Какой I брать?

Цитата(Pavia @  14.6.2009,  02:51 Найти цитируемый пост)
В висуале идет вычисления в long формате в отличии от твоего кода.  

Да, верно.
Но в 32 битной системе это не имеет значение.
--------------------
доска объявленийвсе о горных велосипедах 
PM MAIL   Вверх
Pavia
Дата 16.6.2009, 00:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 418
Регистрация: 6.12.2008

Репутация: 11
Всего: 12



Цитата(bugmenot @  15.6.2009,  22:50 Найти цитируемый пост)
Какой I брать?

Все брать и все дадут верное решение.


PM MAIL   Вверх
bugmenot
Дата 16.6.2009, 00:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 135
Регистрация: 3.7.2006

Репутация: нет
Всего: 1



Что значит все?
То есть любой?
0, например, не подходит, получается дробь
--------------------
доска объявленийвсе о горных велосипедах 
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

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


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0959 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.