Генератора случайных чисел | |
---|---|
of63 Автор Сообщений: 25244 Откуда: Н.Новгород Дата регистрации: 13.02.2008 |
Наверное, не из VFP. Товарищи гуру. Вот задачка, задана "институтке". Создать "генератор случайных чисел". Какие можно предложить алгоритмы генерации этого случайного числа (естественно, без RAND(), SYS(3), SYS(2015), DATATIME() и подобных).
Не в задании: Вероятно, все-таки у этого генератора есть ограничения (возможность повторения сгенерированной последовательности, наличие разрядности, нельзя ли доказать, что последовательность действительно примет все, или много, значений из набора значений заданной разрядности) |
Re: Генератора случайных чисел | |
---|---|
Mitchman Сообщений: 9978 Откуда: Николаев Дата регистрации: 24.05.2002 |
если нужно обязательное присутствие любого елемента - то самый подходящий способ - колода - карт - достаточно легко реализуется и программно
т.е. пока колода / 2 / 3 / нужное задается - закончится - любое значение не может не появиться не повториться - не более и не менее раз колод ------------------ - «свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской» - Олесь Бузина |
Re: Генератора случайных чисел | |
---|---|
of63 Автор Сообщений: 25244 Откуда: Н.Новгород Дата регистрации: 13.02.2008 |
как можно реализовать повторяемость последовательности. Ну, наверное, чтобы ента функция имела параметр, от которого она и начинает последовательность (как RAND() )?
Исправлено 1 раз(а). Последнее : of63, 13.03.09 20:56 |
Re: Генератора случайных чисел | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Почитайте классику
depositfiles.com depositfiles.com depositfiles.com там все это было, причем очень подробно. |
Re: Генератора случайных чисел | |
---|---|
of63 Автор Сообщений: 25244 Откуда: Н.Новгород Дата регистрации: 13.02.2008 |
Что-то не читаются у меня вышеуказанные ссылки...
А нет ли простой идеи по этому поводу? |
Re: Генератора случайных чисел | |
---|---|
XAndy Сообщений: 3803 Откуда: Киев Дата регистрации: 05.02.2004 |
Лучшее, что сейчас есть из открытого - Mersenne twister, период 2^19937
en.wikipedia.org |
Re: Генератора случайных чисел | |
---|---|
XAndy Сообщений: 3803 Откуда: Киев Дата регистрации: 05.02.2004 |
[url]http://ru.wikipedia.org/wiki/Линейный_конгруэнтный_метод[/url] Проще не бывает Исправлено 1 раз(а). Последнее : XAndy, 13.03.09 22:11 |
Re: Генератора случайных чисел | |
---|---|
of63 Автор Сообщений: 25244 Откуда: Н.Новгород Дата регистрации: 13.02.2008 |
Ну, ребята, вы, блин, даете, ссылки в смысле...
Кстати, где-то раньше слышал про сдвиговый регистр, который при каждой генерации числа сдвигается вправо, с отводами, которые суммруются по модулю 2 и прибавляются к выдвигаемому правому разряду из регистра, и, забыл сказать, вдвигаются в него слева. Оказывается, якобы, если "правильно" выбрать эти отводы, то при каждом сдвиге, в регистре, каждый раз образуется "случайное" число. Все вместе это называлось "сигнатурой" (в хорошем смысле этого слова)). Выбор разрядов к этому суммированию и представляет (не берусь сказать "...ло") "маленький" математический секрет математиков (если эти разряды выбрать "неправильно", то случайная последовательность получится "нехорошей"). Я подумал, что, сейчас это общеизвестно, и спросил, может, это уже по-другому надо генерить эту СП, или, может, уже, совсем все по-другому... Исправлено 2 раз(а). Последнее : of63, 13.03.09 22:47 |
Re: Генератора случайных чисел | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Ну вот еще то же самое www.brain2life.com www.brain2life.com www.brain2life.com Про случайные числа во втором томе. Исправлено 1 раз(а). Последнее : leonid, 13.03.09 22:38 |
Re: Генератора случайных чисел | |
---|---|
of63 Автор Сообщений: 25244 Откуда: Н.Новгород Дата регистрации: 13.02.2008 |
Товарищ Xandy, я извиняюсь про вашу ссылку, пока я не понял, я пытаюсь, может пойму...) Там числа очень болшие) Буду учиться.
|
Re: Генератора случайных чисел | |
---|---|
of63 Автор Сообщений: 25244 Откуда: Н.Новгород Дата регистрации: 13.02.2008 |
Кстати, вот чтиво про сигнатурный анализ
www.uran.donetsk.ua |
Re: Генератора случайных чисел | |
---|---|
of63 Автор Сообщений: 25244 Откуда: Н.Новгород Дата регистрации: 13.02.2008 |
Не мог найти в ИЕ обоснование про выбор номеров отводов от сдвигового регистра... А надо ли это?)
Обьясню, почему интересуюсь этой темой. Бывает, что надо сравнить 2 строки, или записать их где нибудь в БД кратко, чтобы потом искать их дубликаты (например, адрес, ФИО, или еще что-то, более обьемное). Поэтому интересуюся функцией краткого представления такого рода инфы, краткой, желательно с возможностью контроля вероятности их "псевдо"совпадения... Исправлено 1 раз(а). Последнее : of63, 13.03.09 23:34 |
Re: Генератора случайных чисел | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Ну батенька, что-ж вы так мечетесь то, от генерации ПСЕВДОслучайных чисел к алгоритмам хеширования (необратимое преобразование, с некоторой вероятностью коллизий) или возможно сжатия (обратимое преобразование, коллизии естественно исключены). Хеширование вообще нельзя применять для "поиска совпадений" - т.к. по определению к одному и тому-же хешу сводится бесконечное число "начальных строк" - другое дело, что вместо сравнения/поиска из всего миллиарда вариантов, хеш укажет 2-3 "кандидата" - которые уж придётся сравнивать по цельному значению.
Вообще-то самые простые генераторы псевдослучайных чисел получаются из банальных полиномов (отсекая старшие разряды результата) - и там действительно подбор коэффициентов полинома играет главнейшую роль в "качестве" получаемой последовательности. Тут, кстати, не только период повторения важен, но и ещё наличие других аномалий "неслучайности" - например некоторые генераторы дают такие числа, что если их рассматривать как координаты X,Y то вместо равномерного заполнения плоскости мы получим, например, семейство параллельных прямых У других генераторов "аномалии неравномерности" возникают если рассматривать уже тройки, или даже четвёрки/пятёрки чисел, или если рассматривать не прямоугольную систему координат а скажем полярную... Правда это вряд-ли представляет хоть какой-то интерес для студиозусов, особенно если это ещё и не математики ------------------ WBR, Igor |
Re: Генератора случайных чисел | |
---|---|
346 Сообщений: 142 Откуда: Ростовская обл. Дата регистрации: 08.09.2006 |
Что значит "псевдо"совпадения?
Когда поиск приблизителен? То есть, например, в БД забито "Иванав Иван" - с ошибкой при наборе, а ищется "Иванов" Правильно ли я понял? |
Re: Генератора случайных чисел | |
---|---|
346 Сообщений: 142 Откуда: Ростовская обл. Дата регистрации: 08.09.2006 |
Функция нечеткого сравнения строк БЕЗ УЧЕТА РЕГИСТРА
//------------------------------------------------------------------------------ //MaxMatching - максимальная длина подстроки (достаточно 3-4) //strInputMatching - сравниваемая строка //strInputStandart - строка-образец // Сравнивание без учета регистра // if IndistinctMatching(4, "поисковая строка", "оригинальная строка - эталон") > 40 then ... Type TRetCount = packed record lngSubRows : Word; lngCountLike : Word; end; //------------------------------------------------------------------------------ function Matching(StrInputA: WideString; StrInputB: WideString; lngLen: Integer) : TRetCount; Var TempRet : TRetCount; PosStrB : Integer; PosStrA : Integer; StrA : WideString; StrB : WideString; StrTempA : WideString; StrTempB : WideString; begin StrA := String(StrInputA); StrB := String(StrInputB); For PosStrA:= 1 To Length(strA) - lngLen + 1 do begin StrTempA:= System.Copy(strA, PosStrA, lngLen); PosStrB:= 1; For PosStrB:= 1 To Length(strB) - lngLen + 1 do begin StrTempB:= System.Copy(strB, PosStrB, lngLen); If SysUtils.AnsiCompareText(StrTempA,StrTempB) = 0 Then begin Inc(TempRet.lngCountLike); break; end; end; Inc(TempRet.lngSubRows); end; // PosStrA Matching.lngCountLike:= TempRet.lngCountLike; Matching.lngSubRows := TempRet.lngSubRows; end; { function } //------------------------------------------------------------------------------ function IndistinctMatching(MaxMatching : Integer; strInputMatching: WideString; strInputStandart: WideString): Integer; Var gret : TRetCount; tret : TRetCount; lngCurLen: Integer ; //текущая длина подстроки begin //если не передан какой-либо параметр, то выход If (MaxMatching = 0) Or (Length(strInputMatching) = 0) Or (Length(strInputStandart) = 0) Then begin IndistinctMatching:= 0; exit; end; gret.lngCountLike:= 0; gret.lngSubRows := 0; // Цикл прохода по длине сравниваемой фразы For lngCurLen:= 1 To MaxMatching do begin //Сравниваем строку A со строкой B tret:= Matching(strInputMatching, strInputStandart, lngCurLen); gret.lngCountLike := gret.lngCountLike + tret.lngCountLike; gret.lngSubRows := gret.lngSubRows + tret.lngSubRows; //Сравниваем строку B со строкой A tret:= Matching(strInputStandart, strInputMatching, lngCurLen); gret.lngCountLike := gret.lngCountLike + tret.lngCountLike; gret.lngSubRows := gret.lngSubRows + tret.lngSubRows; end; If gret.lngSubRows = 0 Then begin IndistinctMatching:= 0; exit; end; IndistinctMatching:= Trunc((gret.lngCountLike / gret.lngSubRows) * 100); end; |
Re: Генератора случайных чисел | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Нет. То о чём ты говоришь, это нечёткий поиск. А я говорил о том, что при вычислении хеша возникают коллизии - грубо говоря у строк "Иванов" и "Черезногузадерищев" вполне может оказаться одинаковый хэш, и полагаться для сравнения ТОЛЬКО на него нельзя. Т.е. после сравнения хэшей всё равно придётся сравнивать и сами "неупакованные" значения. Преимущество хэша в этом случае состоит в существенном сокращении "дорогих" операций полного сравнения значений - т.к. для "Иванова", "Петрова", "Сидорова", "Королёва", "Шевченко" хэши будут различны, и не нужно будет сравнивать эти строки друг с другом - т.к. НЕсовпадение хэша гарантирует "различность" и исходных строк. Вот совпадение хэша не гарантирует идентичность строк - это необходимое, но не достаточное условие. А возвращаясь к вопросам нечёткого поиска - тут есть очень много нюансов, и тема совсем не так проста как кажется. Есть разнообразные описки (пропск буквы, дубблирование буквы, перестаонвка букв), для фамилий есть ошибки созвучия (Лондон/Ландон), есть проблема сравнения слов в разных грамматических формах (Иванов/Иванову/Иванова/Ивановой - поди раздели тут 2 фамилии ). В общем случае придётся написать маленькую экспертную систему, которая оценит всю массу факторов, и в итоге даст некоторое заключение - причём тоже не категорическое "да/нет", а нечто в виде "похоже на 98%"... P.S. В фоксе есть функции DIFFERENCE() и SOUNDEX() - предназначенные как раз для нечёткого поиска. Но приемлемо работают они AFAIK только с английским текстом. ------------------ WBR, Igor |
Re: Генератора случайных чисел | |
---|---|
of63 Автор Сообщений: 25244 Откуда: Н.Новгород Дата регистрации: 13.02.2008 |
А можно дурацкий вопрос про "нечеткий поиск", существуют в математике такие преобразования набора символов (текст) в хеш-функцию (или сигнатуру, уже не знаю, как называть), которые при "похожести" текста дают "близкие" числа? При известных, конечно, возможных отклонениях, например, наложим условия на текст: a)допустимы пропуски 1 символа, b)допустимы замены символа из списка A на символы списка B?
Исправлено 1 раз(а). Последнее : of63, 23.03.09 19:09 |
Re: Генератора случайных чисел | |
---|---|
sphinx Сообщений: 31179 Откуда: Каменск-Уральски Дата регистрации: 22.11.2006 |
|
Re: Генератора случайных чисел | |
---|---|
of63 Автор Сообщений: 25244 Откуда: Н.Новгород Дата регистрации: 13.02.2008 |
Спасибо, товарищи, за ответы.
Кстати, пока для сравнений строк пока применяю следующую самопальную функцию на фоксе. Она позволяет определить похожесть строк с учетом пропуска символов, считает пропуски символов и несоответствия рядом стоящих символов, количество несравнений символов соотносит с длиной максимального текста, возвращает количество несовпадений, (или процент несовпадений по отношению к макс. длине текстов при соотв. передаче параметров) Все основано на переборе символов в FOR и, как следствие, очень медленно. Без этой ф-ии, например, при анализе ФИО при поиске подобных, или частей адреса при поиске в КЛАДР, - обойтись мне просто никак нельзя.
ПС. Начал-то, про генерацию случайных чисел, но, извините, в голове все смешалось. Мысль была такая, что задав начальную последовательность в регистре длиной выходной "хеш-функции" (или просто при начальном пустом регистре) возможно получить случайные числа при применении некоторых операций к этому регистру... Т.е случайные числа, возможно, побочный эффект этого преобразователя. Т.е Вы предлагаете "хеш-функцию" для сравнения строк? (Пробую вьехать в "алгоритм Левенштейна ") Исправлено 1 раз(а). Последнее : of63, 23.03.09 20:59 |
Re: Генератора случайных чисел | |
---|---|
sphinx Сообщений: 31179 Откуда: Каменск-Уральски Дата регистрации: 22.11.2006 |
Реализация алгоритма Левенштейна: fox.wikis.com
Сравнение строк: forum.foxclub.ru ------------------ "Veni, vidi, vici!"(с) |
© 2000-2024 Fox Club  |