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

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

если нужно обязательное присутствие любого елемента - то самый подходящий способ - колода - карт - достаточно легко реализуется и программно

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

как можно реализовать повторяемость последовательности. Ну, наверное, чтобы ента функция имела параметр, от которого она и начинает последовательность (как RAND() )?



Исправлено 1 раз(а). Последнее : of63, 13.03.09 20:56

Почитайте классику
depositfiles.com
depositfiles.com
depositfiles.com
там все это было, причем очень подробно.

Что-то не читаются у меня вышеуказанные ссылки...
А нет ли простой идеи по этому поводу?

Лучшее, что сейчас есть из открытого - Mersenne twister, период 2^19937
en.wikipedia.org

of63
А нет ли простой идеи по этому поводу?

[url]http://ru.wikipedia.org/wiki/Линейный_конгруэнтный_метод[/url]
Проще не бывает



Исправлено 1 раз(а). Последнее : XAndy, 13.03.09 22:11

Ну, ребята, вы, блин, даете, ссылки в смысле...

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



Исправлено 2 раз(а). Последнее : of63, 13.03.09 22:47

of63
Что-то не читаются у меня вышеуказанные ссылки...

Ну вот еще то же самое
www.brain2life.com
www.brain2life.com
www.brain2life.com
Про случайные числа во втором томе.



Исправлено 1 раз(а). Последнее : leonid, 13.03.09 22:38

Товарищ Xandy, я извиняюсь про вашу ссылку, пока я не понял, я пытаюсь, может пойму...) Там числа очень болшие) Буду учиться.

Кстати, вот чтиво про сигнатурный анализ
www.uran.donetsk.ua

Не мог найти в ИЕ обоснование про выбор номеров отводов от сдвигового регистра... А надо ли это?)

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



Исправлено 1 раз(а). Последнее : of63, 13.03.09 23:34

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

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

Что значит "псевдо"совпадения?
Когда поиск приблизителен? То есть, например, в БД забито "Иванав Иван" - с ошибкой при наборе, а ищется "Иванов"
Правильно ли я понял?

Функция нечеткого сравнения строк БЕЗ УЧЕТА РЕГИСТРА

//------------------------------------------------------------------------------
//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;

346
Что значит "псевдо"совпадения?
Когда поиск приблизителен? То есть, например, в БД забито "Иванав Иван" - с ошибкой при наборе, а ищется "Иванов"
Правильно ли я понял?

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

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

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

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



Исправлено 1 раз(а). Последнее : of63, 23.03.09 19:09

Вот это не подойдет ru.wikipedia.org ?

Спасибо, товарищи, за ответы.

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

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



Исправлено 1 раз(а). Последнее : of63, 23.03.09 20:59

Реализация алгоритма Левенштейна: fox.wikis.com

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