for flooders
:: Главная :: Решения :: Статьи :: Сайт М. Дроздова :: Файловый архив :: Книга по VFP 9 :: Русский Help Online :: OFF-LINE Форум
   Л и с о в о д ы   в с е х   с т р а н,  о б ъ е д и н я й т е с ь !!!  

Список Форумов  :: Игры Разума
   :: Помощь сайту :: 

Генератора случайных чисел
of63
Автор

Сообщений: 13907
Откуда: Н.Новгород
Дата: 13.03.09 19:31:00ОтветитьЦитировать
Наверное, не из VFP. Товарищи гуру. Вот задачка, задана "институтке". Создать "генератор случайных чисел". Какие можно предложить алгоритмы генерации этого случайного числа (естественно, без RAND(), SYS(3), SYS(2015), DATATIME() и подобных).

Не в задании: Вероятно, все-таки у этого генератора есть ограничения (возможность повторения сгенерированной последовательности, наличие разрядности, нельзя ли доказать, что последовательность действительно примет все, или много, значений из набора значений заданной разрядности)
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
Mitchman
[Модератор]

Сообщений: 9675
Откуда: Николаев
Дата: 13.03.09 19:37:32ОтветитьЦитировать
если нужно обязательное присутствие любого елемента - то самый подходящий способ - колода - карт - достаточно легко реализуется и программно

т.е. пока колода / 2 / 3 / нужное задается - закончится - любое значение не может не появиться не повториться - не более и не менее раз колод


------------------
а будни - это попросту антракт
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
of63
Автор

Сообщений: 13907
Откуда: Н.Новгород
Дата: 13.03.09 19:50:03ОтветитьЦитировать
как можно реализовать повторяемость последовательности. Ну, наверное, чтобы ента функция имела параметр, от которого она и начинает последовательность (как RAND() )?



Исправлено: of63, 13.03.09 19:56
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
leonid

Сообщений: 2618
Откуда: Рига
Дата: 13.03.09 20:27:57ОтветитьЦитировать
Почитайте классику
depositfiles.com
depositfiles.com
depositfiles.com
там все это было, причем очень подробно.
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
of63
Автор

Сообщений: 13907
Откуда: Н.Новгород
Дата: 13.03.09 20:43:55ОтветитьЦитировать
Что-то не читаются у меня вышеуказанные ссылки...
А нет ли простой идеи по этому поводу?
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
XAndy

Сообщений: 3803
Откуда: Киев
Дата: 13.03.09 21:04:55ОтветитьЦитировать
Лучшее, что сейчас есть из открытого - Mersenne twister, период 2^19937
en.wikipedia.org
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
XAndy

Сообщений: 3803
Откуда: Киев
Дата: 13.03.09 21:08:49ОтветитьЦитировать
of63
А нет ли простой идеи по этому поводу?
[url]http://ru.wikipedia.org/wiki/Линейный_конгруэнтный_метод[/url]
Проще не бывает



Исправлено: XAndy, 13.03.09 21:11
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
of63
Автор

Сообщений: 13907
Откуда: Н.Новгород
Дата: 13.03.09 21:24:59ОтветитьЦитировать
Ну, ребята, вы, блин, даете, ссылки в смысле...

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



Исправлено: of63, 13.03.09 21:47
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
leonid

Сообщений: 2618
Откуда: Рига
Дата: 13.03.09 21:37:52ОтветитьЦитировать
of63
Что-то не читаются у меня вышеуказанные ссылки...
Ну вот еще то же самое
www.brain2life.com
www.brain2life.com
www.brain2life.com
Про случайные числа во втором томе.



Исправлено: leonid, 13.03.09 21:38
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
of63
Автор

Сообщений: 13907
Откуда: Н.Новгород
Дата: 13.03.09 21:38:32ОтветитьЦитировать
Товарищ Xandy, я извиняюсь про вашу ссылку, пока я не понял, я пытаюсь, может пойму...) Там числа очень болшие) Буду учиться.
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
of63
Автор

Сообщений: 13907
Откуда: Н.Новгород
Дата: 13.03.09 22:12:43ОтветитьЦитировать
Кстати, вот чтиво про сигнатурный анализ
www.uran.donetsk.ua
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
of63
Автор

Сообщений: 13907
Откуда: Н.Новгород
Дата: 13.03.09 22:23:31ОтветитьЦитировать
Не мог найти в ИЕ обоснование про выбор номеров отводов от сдвигового регистра... А надо ли это?)

Обьясню, почему интересуюсь этой темой. Бывает, что надо сравнить 2 строки, или записать их где нибудь в БД кратко, чтобы потом искать их дубликаты (например, адрес, ФИО, или еще что-то, более обьемное). Поэтому интересуюся функцией краткого представления такого рода инфы, краткой, желательно с возможностью контроля вероятности их "псевдо"совпадения...



Исправлено: of63, 13.03.09 22:34
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
Igor Korolyov

Сообщений: 32507
Дата: 15.03.09 23:44:35ОтветитьЦитировать
Ну батенька, что-ж вы так мечетесь то, от генерации ПСЕВДОслучайных чисел к алгоритмам хеширования (необратимое преобразование, с некоторой вероятностью коллизий) или возможно сжатия (обратимое преобразование, коллизии естественно исключены). Хеширование вообще нельзя применять для "поиска совпадений" - т.к. по определению к одному и тому-же хешу сводится бесконечное число "начальных строк" - другое дело, что вместо сравнения/поиска из всего миллиарда вариантов, хеш укажет 2-3 "кандидата" - которые уж придётся сравнивать по цельному значению.

Вообще-то самые простые генераторы псевдослучайных чисел получаются из банальных полиномов (отсекая старшие разряды результата) - и там действительно подбор коэффициентов полинома играет главнейшую роль в "качестве" получаемой последовательности. Тут, кстати, не только период повторения важен, но и ещё наличие других аномалий "неслучайности" - например некоторые генераторы дают такие числа, что если их рассматривать как координаты X,Y то вместо равномерного заполнения плоскости мы получим, например, семейство параллельных прямых У других генераторов "аномалии неравномерности" возникают если рассматривать уже тройки, или даже четвёрки/пятёрки чисел, или если рассматривать не прямоугольную систему координат а скажем полярную... Правда это вряд-ли представляет хоть какой-то интерес для студиозусов, особенно если это ещё и не математики


------------------
WBR, Igor
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
346

Сообщений: 133
Откуда: Ростовская обл.
Дата: 17.03.09 09:43:13ОтветитьЦитировать
Что значит "псевдо"совпадения?
Когда поиск приблизителен? То есть, например, в БД забито "Иванав Иван" - с ошибкой при наборе, а ищется "Иванов"
Правильно ли я понял?
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
346

Сообщений: 133
Откуда: Ростовская обл.
Дата: 17.03.09 09:53:06ОтветитьЦитировать
Функция нечеткого сравнения строк БЕЗ УЧЕТА РЕГИСТРА

//------------------------------------------------------------------------------
//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;
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
Igor Korolyov

Сообщений: 32507
Дата: 18.03.09 15:05:45ОтветитьЦитировать
346
Что значит "псевдо"совпадения?
Когда поиск приблизителен? То есть, например, в БД забито "Иванав Иван" - с ошибкой при наборе, а ищется "Иванов"
Правильно ли я понял?

Нет. То о чём ты говоришь, это нечёткий поиск.
А я говорил о том, что при вычислении хеша возникают коллизии - грубо говоря у строк "Иванов" и "Черезногузадерищев" вполне может оказаться одинаковый хэш, и полагаться для сравнения ТОЛЬКО на него нельзя. Т.е. после сравнения хэшей всё равно придётся сравнивать и сами "неупакованные" значения. Преимущество хэша в этом случае состоит в существенном сокращении "дорогих" операций полного сравнения значений - т.к. для "Иванова", "Петрова", "Сидорова", "Королёва", "Шевченко" хэши будут различны, и не нужно будет сравнивать эти строки друг с другом - т.к. НЕсовпадение хэша гарантирует "различность" и исходных строк. Вот совпадение хэша не гарантирует идентичность строк - это необходимое, но не достаточное условие.

А возвращаясь к вопросам нечёткого поиска - тут есть очень много нюансов, и тема совсем не так проста как кажется. Есть разнообразные описки (пропск буквы, дубблирование буквы, перестаонвка букв), для фамилий есть ошибки созвучия (Лондон/Ландон), есть проблема сравнения слов в разных грамматических формах (Иванов/Иванову/Иванова/Ивановой - поди раздели тут 2 фамилии ). В общем случае придётся написать маленькую экспертную систему, которая оценит всю массу факторов, и в итоге даст некоторое заключение - причём тоже не категорическое "да/нет", а нечто в виде "похоже на 98%"...

P.S. В фоксе есть функции DIFFERENCE() и SOUNDEX() - предназначенные как раз для нечёткого поиска. Но приемлемо работают они AFAIK только с английским текстом.


------------------
WBR, Igor
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
of63
Автор

Сообщений: 13907
Откуда: Н.Новгород
Дата: 23.03.09 18:08:54ОтветитьЦитировать
А можно дурацкий вопрос про "нечеткий поиск", существуют в математике такие преобразования набора символов (текст) в хеш-функцию (или сигнатуру, уже не знаю, как называть), которые при "похожести" текста дают "близкие" числа? При известных, конечно, возможных отклонениях, например, наложим условия на текст: a)допустимы пропуски 1 символа, b)допустимы замены символа из списка A на символы списка B?



Исправлено: of63, 23.03.09 18:09
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
sphinx

Сообщений: 23796
Откуда: Каменск-Уральски
Дата: 23.03.09 19:01:51ОтветитьЦитировать
Вот это не подойдет ru.wikipedia.org ?


------------------
"Вы поступили правильно, мой друг, но, боюсь, совершили ошибку"..."(с)
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
of63
Автор

Сообщений: 13907
Откуда: Н.Новгород
Дата: 23.03.09 19:52:17ОтветитьЦитировать
Спасибо, товарищи, за ответы.

Кстати, пока для сравнений строк пока применяю следующую самопальную функцию на фоксе. Она позволяет определить похожесть строк с учетом пропуска символов, считает пропуски символов и несоответствия рядом стоящих символов, количество несравнений символов соотносит с длиной максимального текста, возвращает количество несовпадений, (или процент несовпадений по отношению к макс. длине текстов при соотв. передаче параметров) Все основано на переборе символов в FOR и, как следствие, очень медленно. Без этой ф-ии, например, при анализе ФИО при поиске подобных, или частей адреса при поиске в КЛАДР, - обойтись мне просто никак нельзя.
  
 ***********************************************************************  
 * Возвращает количество несовпадающих непробельных символов в 2 строках (1) и (2)  
 * Перед сравнением строк производится DKOITORUS-UPPER-ALLTRIM-уд(`ЪЬЕЁИЙШЩ)  
 *    0   - Возвращает количество несовпадающих непробельных символов (умолчание)  
 *    1   - возвращает степень совпадения строк в ед.   (1-полное совп)  
 *    "%" - возвращает степень совпадения строк в проц. (100-полное совп)  
 ***********************************************************************  
  FUNCTION STRCOMP  
  PARAMETE m.parC1, m.parC2, m.parPROC  
  PRIVATE  ALL LIKE ?  
  m.p = PCOUNT()  
  m.t = IIF(m.p<3, 0, IIF(VARTYPE(m.parPROC)="N", 1, 100))  
  m.i = "`ЪЬЕЁИЙШЩ"+" /\|!'()"+'"'  && эти символы  
  m.j = "ЬЬЬЕЕИИШШ"                 && преобразовать в эти  
  m.a = CHRTRAN(ALLTRIM(UPPER(DKOITORUS(m.parC1))), m.i, m.j)  && строка 1  
  m.b = CHRTRAN(ALLTRIM(UPPER(DKOITORUS(m.parC2))), m.i, m.j)  && строка 2  
  m.l = MAX(LEN(m.a),LEN(m.b))  
  IF EMPTY(m.a) .AND. EMPTY(m.b)  && обе строки пусты - вернем ПОЛНОЕ СОВПАДЕНИЕ  
     RETURN ICASE(m.t=1, 1, m.t=100, 100, 0)  
  ENDIF  
  IF EMPTY(m.a) .OR. EMPTY(m.b)   && одна из строк пуста - вернем ПОЛНОЕ НЕСОВПАДЕНИЕ  
     RETURN ICASE(m.t=1, 0, m.t=100, 0,   m.l)  
  ENDIF  
  m.j = 0  
  m.i = LEN(m.a)-LEN(m.b)  
  IF m.i=0  && длины слов равны  
     FOR m.i=1 TO LEN(m.a)  
         m.j = m.j + IIF(SUBSTR(m.a,m.i,1)==SUBSTR(m.b,m.i,1), 0, 1)  
     ENDFOR  
  ELSE  && длины слов отличаются  
     IF m.i<0  && если строка 1 короче  
        m.s = m.a  && строка 1 д.б. самой длинной  
        m.a = m.b  
        m.b = m.s  
     ENDIF  
     m.s = ABS(m.i)  && на сколько строка 1 длинее строки 2  
     FOR m.i=0 TO m.s  && попытки сравнения на разных смещениях в строке 1  
         FOR m.j=1 TO LEN(m.b)  && сравнение на длине строки 2, она короткая  
             m.x = SUBSTR(m.a, m.j+m.i, 1)  
             IF m.x#" " .AND. m.x==SUBSTR(m.b, m.j, 1)  
                m.a = STUFF(m.a, m.j+m.i, 1, " ")  
                m.b = STUFF(m.b, m.j,     1, " ")  
             ENDIF  
             IF EMPTY(m.a) .OR. EMPTY(m.b)  
                EXIT  
             ENDIF  
         ENDFOR  
         IF EMPTY(m.a) .OR. EMPTY(m.b)  
            EXIT  
         ENDIF  
     ENDFOR  
     m.j = LEN(ALLTRIM(CHRTRAN(m.a, " ", "")))  
  ENDIF  
  RETURN ICASE(m.t=1, 1-m.j/m.l, m.t=100, 100*(1-m.j/m.l), m.j)

ПС. Начал-то, про генерацию случайных чисел, но, извините, в голове все смешалось. Мысль была такая, что задав начальную последовательность в регистре длиной выходной "хеш-функции" (или просто при начальном пустом регистре) возможно получить случайные числа при применении некоторых операций к этому регистру... Т.е случайные числа, возможно, побочный эффект этого преобразователя. Т.е Вы предлагаете "хеш-функцию" для сравнения строк? (Пробую вьехать в "алгоритм Левенштейна ")



Исправлено: of63, 23.03.09 19:59
Ratings: 0 negative/0 positive

Re: Генератора случайных чисел
sphinx

Сообщений: 23796
Откуда: Каменск-Уральски
Дата: 23.03.09 20:05:13ОтветитьЦитировать
Реализация алгоритма Левенштейна: fox.wikis.com

Сравнение строк: forum.foxclub.ru




------------------
"Вы поступили правильно, мой друг, но, боюсь, совершили ошибку"..."(с)
Ratings: 0 negative/0 positive



Извините, только зарегистрированные пользователи могут писать в этом форуме.

On-line: 17 Дмитрий Петров  and Guests: 16


© 2000-2019 Fox Club 
Яндекс.Метрика