Попробуем провести небольшую олимпиаду

← →
pasha_golub © (2004-05-28 11:18) [40]

Romkin © (28.05.04 11:08) [35]
Ну, намекни хоть.

1. Обращение матрицы произвольного вида. На входе - динамический массив, на выходе - обратная матрица и определитель исходной.
В чем полезность?

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

И все-таки про щифрацию-дешифрацию, как тама, а? Потому шо я уже полез в исходники Random"a :-)))

← →
Паниковский © (2004-05-28 11:19) [41]

Все это конечно IMHO ну и сказанное до этого.
КРОМЕ ПИВА...
И еще ты пытаешся придумать задачи на какую то предметную область то есть я читая твои посты сразу понял что задача один игроделы два криптография

← →
Романов Р.В. © (2004-05-28 11:22) [42]

> Паниковский © (28.05.04 11:08) [36]

Я не знаю какие задачи решаются на олимпиадах (был там всего один раз в 1994 году), а значит ничего не копирую, тем более тупо.
А такие простые задачки как вы приводите MBo каждую пятницу выдает.

← →
Mystic © (2004-05-28 11:26) [43]

> Сорри за оффтоп, но все же интересно, чем у Вас код парсится?

А зачем парсить код? Если кто-то вызывает функцию Test, то загаданное число уже храниться где-то в памяти. Значит нужно просто найти задуманное чисто и попробовать его ;) В среднем для приведенного выше текста теста программа угадsdftn задунное число с первой попытки. Даже для вызова

ShowMessage(IntToStr(Test("Test string ;)")));

С другой стороны я проверял только на компиляторе Delphi 5. Возможно на других версиях код ведет себя не так.

На самом деле вопрос серьезнее, так как я мог бы спрятать этот среди большой кучи кода, который бы иммитировал угадывание, но при случае подглядывал бы правильно решение ;) Или на всякий случай один раз просмотреть всю кучу на предмент нахождения последовательностей <число, число, число, число, #0>. Среди них с наибольшей вероятностью храниться задуманная ;) И т. д.

← →
Romkin © (2004-05-28 11:29) [44]

pasha_golub © (28.05.04 11:18) [40] 1. Просят люди часто. А на Delphi я этого не видел ;) Метода, чтобы было удобно и быстро...
2. Нормально, аналитически никто не просит это делать. Понятно, сложная задача. Но есть достаточно много методов, которые это делают. Понятно, практически всегда найдется полином, для которого данный метод не сработает, однако можно. Кто сказал, что будет легко?!
>И все-таки про щифрацию-дешифрацию, как тама, а? Потому шо я уже полез в исходники Random"a :-)))
Правильной дорогой идете, товарищ! Потому что у меня метод грубой силы :))) Перебираются все значения randSeed от 0 до MaxInt а потом отрицательные. Проверяются первые три десятка символов, если получается похоже на русский - весь текст дешифруется и запоминается как вариант... Потом - выбор из вариантов. Время приемлемое, несколько часов ;)

← →
Паниковский © (2004-05-28 11:33) [45]

Романов Р.В.

"тупо цинично" просто выражение которое означает "копирование чужих идей"

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

← →
pasha_golub © (2004-05-28 11:34) [46]

Правильной дорогой идете, товарищ! Потому что у меня метод грубой силы :))) Перебираются все значения randSeed от 0 до MaxInt а потом отрицательные. Проверяются первые три десятка символов, если получается похоже на русский - весь текст дешифруется и запоминается как вариант... Потом - выбор из вариантов. Время приемлемое, несколько часов ;)

Не, так не пойдет. :-) Кто сказал, что текст русский? А если смешанный, а если, допустим, компьютерный? Статья какая-нить с кодами и т.п. :-)

← →
Паниковский © (2004-05-28 11:35) [47]

Romkin
криптография < программирования

← →
Romkin © (2004-05-28 11:39) [48]

pasha_golub © (28.05.04 11:34) [46] Условие видел? Отрывок художественного произведения. Впрочем, и с компьютерным справиться можно, главное - знать, на каком языке.
В идеале, конечно, желательно сделать метод восстановления RandSeed по отрывку последовательности. Но это уже очень нетривиально, даже если метод random прост. Упор можно сделать на то, что в тексте есть цепочка пробелов, ксорить с пробелами шифрованный текст - где-то будет цепочка чистой последовательности.

← →
Паниковский © (2004-05-28 11:41) [49]

Romkin
Randomize;
...
random(...)
...

и начинаем гадать счас инфу принесу по криптографии )))

← →
pasha_golub © (2004-05-28 11:43) [50]

Отрывок из хелпа:

Note: Because the implementation of the Random function may change between compiler versions, we do not recommend using Random for encryption or other purposes that require reproducible sequences of pseudo-random numbers.

Так что
В идеале, конечно, желательно сделать метод восстановления RandSeed по отрывку последовательности. Но это уже очень нетривиально, даже если метод random прост.

не то, что не тривиально, а просто супер-нетривиально.

← →
Паниковский © (2004-05-28 11:44) [51]

Модератор дави все мои посты в этой ветке

← →
YurikGl © (2004-05-28 11:45) [52]

> Например:
> Поменять занчения двух чисел между собой. Используя только
> две переменные.

Если ничего не путаю, то
a:=a+b;
b:=a-b;
a:=a-b;

← →
Паниковский © (2004-05-28 11:47) [53]

YurikGl
угу ...
могу еще головоломок поискать

← →
YurikGl © (2004-05-28 11:49) [54]

Паниковский © (28.05.04 11:47) [53]

Это мы в школе делали.

Я сейча Романов Р.В. © (27.05.04 10:24) делаю, так что пока головоломок не надо :)

← →
Романов Р.В. © (2004-05-28 12:40) [55]

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

← →
Mystic © (2004-05-28 12:42) [56]

procedure _RandInt; asm { ->EAX Range } { <-EAX Result } IMUL EDX,RandSeed,08088405H INC EDX MOV RandSeed,EDX MUL EDX MOV EAX,EDX end;

Не очень то она и менялась...

Просто можно возпользоваться и другими генераторами ;)

← →
MBo © (2004-05-28 12:47) [57]

>Romkin © (28.05.04 11:08) [35]
>1. Обращение матрицы произвольного вида. На входе - динамический массив, на выходе - обратная матрица и определитель исходной.

Если нужно, у меня есть с использованием LU-разложения.

← →
pasha_golub © (2004-05-28 13:17) [58]

Mystic © (28.05.04 12:42) [56]
У меня Д6:
procedure RandInt;
asm
PUSH EBX
XOR EBX,EBX
IMUL EDX,[EBX+RandSeed],08088405H
INC EDX
MOV [EBX+RandSeed],EDX
MUL EDX
MOV EAX,EDX
POP EBX
RET
end;

← →
Паниковский © (2004-05-28 13:31) [59]

a:= a+b;
b:= a-b;
a := a+b;
a := b-a;

← →
Романов Р.В. © (2004-05-28 13:51) [60]

YurikGl
Участник должен разработать функцию FindNum и GetName и прислать модуль Olimp по электронной почте.

← →
Паниковский © (2004-05-28 14:05) [61]

ящик в студию!!!

← →
Романов Р.В. © (2004-05-28 14:10) [62]

Какой ящик?

← →
Паниковский © (2004-05-28 14:11) [63]

электронный почтовый ящик
e-mail

← →
Паниковский © (2004-05-28 14:26) [64]

Результаты принимаются до 1 Июля по адресу RSoftComp<собака>mail.ru

во САМ нашел!))

← →
Mystic © (2004-05-28 15:19) [65]

> pasha_golub © (28.05.04 13:17) [58]

Ну и найди 10 отличий в алгоритме генерации.

← →
YurikGl © (2004-05-28 16:11) [66]

> Романов Р.В. © (28.05.04 13:51) [60]
> YurikGl
> Участник должен разработать функцию FindNum и GetName и
> прислать модуль Olimp по электронной почте.

Я отправил

З.Ы. И тема вверх поднялась :)

← →
pasha_golub © (2004-05-28 16:23) [67]

Mystic © (28.05.04 15:19) [65]

Не могу - языкам не обучен. :-) Паки, паки, иже херувимы (с) Иван Васильевич меняет профессию

← →
Gero © (2004-05-28 23:52) [68]

> Mystic © (28.05.04 11:26)

Я имею ввиду какой инструмент Вы используете для html-sytax highlight?

Подниму тему вверх :)

Romkin (28.05.04 11:29) [44]
все значения randSeed от 0 до MaxInt а потом отрицательны

э-э-э, ну так нечестно. Метод тупого перебора... я так не играю...

Остался 1 день, а самый оптимальный алгоритм еще не написан...

> Результаты принимаются до 1 Июля по адресу RSoftComp<собака>mail.ru

Еще целый месяц что-ли?

Перепутал 1 июня :)
Подведем итоги. В первой олимпиаде приняло участие 3 человека.

Результаты:
Романов Р.В. 6.9619 YurikGL 13.8249 Mystic 10001
Публикую базовый оптимальный алгоритм. Средний результат 6.98683 из 100000 проверок. Его можно модернизировать и улучшить средний результат (у меня получилось улучшить до 6,9619).

unit Olimp; // Имя Участника обязательно! interface function FindNum(): string; implementation uses OlimpShare, SysUtils, Dialogs; // Получение имени участника function GetName(): string; begin Result := "Романов Р.В."; end; // Анализ чисел на совпадение с претендентом function Analis(const AValue, Pretend: string): TChekResult; const _01 = #01; NumeralCount = 4; var S, F: string; i, j: Integer; begin Result.Plus := 0; Result.Asterisk := 0; S := AValue; F := Pretend; // Поиск плюсов for i := 1 to NumeralCount do if F[i] = S[i] then begin Inc(Result.Plus); S[i] := _01; F[i] := _01; end; // Поиск звездочек for i := 1 to NumeralCount do for j := 1 to NumeralCount do if (S[i] <> _01) and (S[i] = F[j]) then begin inc(Result.Asterisk); S[i] := _01; F[j] := _01; end; end; // Получение числа состоящего из неповторяющихся цифр function GetFurstNumber(): string; var i, j, n: Integer; c: array[0..9] of Integer; // Массив цифр begin // Заполняем массив цифрами от 0 до 9 for i := 0 to 9 do c[i] := i; randomize; // Перемешиваем числа в массиве for i := 0 to 9 do begin j := Random(10); n := c[j]; c[j] := c[i]; c[i] := n; end; Result := ""; for i := 0 to 3 do Result := Result + IntToStr(c[i]); // ShowMessage("Первое число "+ Result); end; // Алгоритм поиска числа function FindNum(): string; var R, O: TChekResult; F: array [0..9999] of Boolean; // Массив признаков чисел претендентов i: Integer; s: string; k: Integer; begin // Если значение в массиве равно True - число с данным индексом является // претендентом. Если False - число уже отброшено. // Изначально все числа являются претендентами for i := Low(F) to High(F) do F[i] := True; // Выбор первого числа. // Первое число состоит из неповторяющихся цифр Result := GetFurstNumber(); // Поиск числа в цикле while True do begin // Вызов проверки R := CheckNum(Result); if R.Plus = NumeralCount then Exit; // Если 4 плюса - число найдено! // Алгоритм отгадывания числа s := Result; k := 0; // Счетчик показывающий сколько претендентов осталось на текущем шаге for i := Low(F) to High(F) do // Проверяем все 10000 чисел if F[i] then // Если число является претендентом begin // предполагаем что оно является искомым числом, и выполняем проверку // аналогичную CheckNum, в которой вместо искомого числа используется // число претендент O := Analis(Format("%.4d", [i]), s); // Для искомого числа результаты обоих проверок (CheckNum и Analis) // одинаковы, а значит оно остается среди претендентов. F[i] := (O.Plus = R.Plus) and (O.Asterisk = R.Asterisk); if F[i] then // Если число не отброшено begin // используем его в качестве предполагаемого искомого числа // на следующем шаге. // Если организовать более интеллектуальный выбор // этого числа, то можно еще улучшить результат. // Здесь есть над чем подумать! :) Result := Format("%.4d", [i]); Inc(k); // Увеличиваем счетчик претендентов end; end; // ShowMessage(Format("Осталось %d претендентов",[k])); end; end; end.

function Analis(const AValue, Pretend: string): TChekResult;
Разве не аналог CheckNum-a?

Романов Р.В.
Поздравляю я бы никак не додумался зделать олимпиаду для себя )))

> Разве не аналог CheckNum-a?

Аналог, только с одним большим отличаем. Analis не использует искомое число для вычисления результата.

> Паниковский © (01.06.04 09:02) [75]

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

Романов Р.В. © (01.06.04 10:38) [76]

Идею понял.

Мнда... я-то вводил вероятностную оценку наличия каждой цифры в числе.... Зато, у меня работает на порядок быстрее.

З.Ы. Если я правильно понял результаты олимпиады, ажиотаж ->0 Обидно...

Хотелось бы посмотреть программу, при помощи которой проводилось тестирование.

procedure TForm1.Button1Click(Sender: TObject); var Sum: Integer; Max, Min: Integer; i, j, k, m: Integer; begin Sum := 0; Max := 0; m := 0; Min := 20000; for k := 1 to 10 do for i := 0 to 9999 do begin j := Test(i); Sum := Sum + j; if Max < j then Max := j; if Min > j then Min := j; Inc(m); Label1.Caption := "Максимум попыток " + IntToStr(Max); Label2.Caption := "Минимум попыток " + IntToStr(Min); Label3.Caption := "Среднее количество " + FloatToStr(Sum/(m)); Label4.Caption := "Количество итераций " + IntToStr(m); Application.ProcessMessages; end; end; ... function Test(ANum: Integer): Integer; begin Result := Trunc(Power(10, NumeralCount)) + 1; try CheckNumCount := 0; if Format("%.4d", [ANum]) = FindNum then Result := CheckNumCount; except end; end;

> Романов Р.В. © (01.06.04 12:12) [79]

Нахорошо ;) текст функции Test публиковался ранее, а теперь в него внесены изменения...

Попробуем провести небольшую олимпиаду Найти похожие ветки