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

← →
Романов Р.В. © (2004-05-27 10:24) [0]

Имеется четырехзначное число. Необходимо написать функцию FindNum которая отгадывает это число.
В процессе своей работы необходимо вызывать функцию CheckNum, которая будет возвращать количество цифр у которых совпали позиции условно назовем их «плюс» и количество цифр которые содержатся в отгадываемом числе не на своих позициях их назовем «звездочка».
Напимер:
Отгадываемое число 1234
Переданное в функцию число 2133
Результат возвращаемый функцией: 1 плюс (число 3) и 2 звездочки (числа 1 и 2)

Отгадываемое число 3324
Переданное в функцию число 2133
Результат возвращаемый функцией: 0 плюсов и 3 звездочки (2 и две 3)

Участник должен разработать функцию FindNum и GetName и прислать модуль Olimp по электронной почте.
Функция GetName должна возвращать имя участника
Функция FindNum – содержит алгоритм поиска заданного числа с обязательным вызовом проверки.

Будет проведено несколько тестов с различными исходными данными. Оценка будет произвродися по среднему количеству итераций S, и оформлению кода. Код должен быть отформатирован и прокомментирован.

Оценка := S + 0.1*S {при отсутствии комментариев} + 0.1*S {при отсутствии оформления}

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

← →
Романов Р.В. © (2004-05-27 10:24) [1]

Шаблон модуля Olimp
unit Olimp; // Имя Участника обязательно! interface function FindNum(): string; implementation uses OlimpShare; // Получение имени участника function GetName(): string; begin Result := "Иванов Иван Иванович"; end; function FindNum(): string; var R: TChekResult; begin // Выбор первого числа Result := "0000"; while True do begin // Вызов проверки R := CheckNum(Result); if R.Plus = NumeralCount then Exit // Алгоритм отгадывания числа // ... end; end; end.

← →
Романов Р.В. © (2004-05-27 10:25) [2]

Модуль OlimpShare с процедурой проверки числа
unit OlimpShare; interface const NumeralCount = 4; type TChekResult = record // Результат проверки числа Plus: Integer; // Количество плюсов Asterisk: Integer; // Количество звездочек end; function CheckNum(const AValue: string): TChekResult; // Функция проверки числа function Test(ANum: string): Integer; // Тестирование алгоритма участника implementation uses math, SysUtils, Olimp; var CheckNumCount: Integer; // Количество проверок FNum: string; // Искомое число function CheckNum(const AValue: string): TChekResult; const _01 = #01; var S, F: string; i, j: Integer; begin Result.Plus := 0; Result.Asterisk := 0; Inc(CheckNumCount); // Различные проверки if CheckNumCount > Power(10, NumeralCount) then Abort; if Length(AValue) < NumeralCount then Exit; S := Copy(AValue, 1 , NumeralCount); F := FNum; // Поиск плюсов 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 Test(ANum: string): Integer; begin FNum := ANum; Result := Trunc(Power(10, NumeralCount)) + 1; try CheckNumCount := 0; if FNum = FindNum then Result := CheckNumCount; except end; end; end.

← →
Романов Р.В. © (2004-05-27 10:25) [3]

Пример тестирования алгоритма
implementation uses Olimp, OlimpShare; {$R *.dfm} procedure TForm1.Button1Click(Sender: TObject); begin ShowMessage(IntToStr(Test("1234"))); end;

← →
Kerk © (2004-05-27 10:27) [4]

Не катит такая олимпиада...
Оптимальный алгоритм давно всем известен.

← →
Романов Р.В. © (2004-05-27 10:42) [5]

Думаю не все его знают

← →
Романов Р.В. © (2004-05-27 10:57) [6]

Если кто то захочет поучаствовать пишите сюда что нибудь. Во первых будет видно что участники есть во вторых ветка будет вверх перемещаться.

← →
Kerk © (2004-05-27 10:58) [7]

Я не участвую, ибо честный. :)

← →
Паниковский © (2004-05-27 13:30) [8]

Романов Р.В.
заглохло не родившись

← →
McSimm © (2004-05-27 14:39) [9]

http://www.delphimaster.ru/cgi-bin/vote.pl?look=1085647677

← →
VMcL © (2004-05-27 15:20) [10]

>McSimm © (27.05.04 14:39) [9]

А что голосование уже закончилось?

← →
Kerk © (2004-05-27 15:25) [11]

> А что голосование уже закончилось?

Я только что проголосовал.

← →
McSimm © (2004-05-27 15:28) [12]

> VMcL © (27.05.04 15:20) [10]

Сам блок голосования гуляет по сайту случайным образом.

← →
Mystic © (2004-05-27 18:49) [13]

unit Olimp; interface function FindNum(): string; implementation uses OlimpShare; function GetName(): string; begin Result := "Mystc"; end; var TestStr: PChar; function Stub(): string; begin Result := AnsiString(TestStr); end; {$W-} function FindNum(): string; asm PUSH EAX MOV EAX, [EBP-$04] MOV TestStr, EAX POP EAX JMP Stub end; end.

← →
VMcL © (2004-05-27 19:00) [14]

>>McSimm © (27.05.04 15:28) [12]

Ну это я знаю. Я думал, может как-то можно отдельно по выбранной теме проголосовать.

← →
Romkin © (2004-05-27 19:02) [15]

Абсолютно неитересное задание :)
Я даже писать не буду, решение укладывается в несколько слов: перебираем все четырехзначные числа в цикле, как только получаем 4 плюса - выводим результат. Все.
Скажете, неоптимально? Ничего подобного. На современном компьютере результат будет получен за очень малое время, в среднем будет выполнено около 4500 циклов, что займет где-то четверть секунды максимум :) И вполне возможно, это окажется быстрее программы с оптимальным алгоритмом ;)

← →
Gero © (2004-05-27 19:03) [16]

> Mystic © (27.05.04 18:49)

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

← →
pasha_golub © (2004-05-27 19:08) [17]

Задача носит название "Быки и коровы". Ее решают в ВУЗах, а то и в школах.

← →
Romkin © (2004-05-27 19:33) [18]

Вот еще алгоритм, сорри, но реализацию писать лень...
Итак, имеем функцию, которая выдает плюсики и звездочки CheckNum.
Первый этап: генератором случайных четырехзначных чисел подбираем такое число, чтобы совпадений цифр не было вообще. Если не ошибаюсь, вероятность около 0.65, то есть 1-2 число так попадет...
Второй этап: циклически изменяем первую цифру, пока не появится плюс (то есть если это 4, то проходим 5..9,0..3). Первая цифра установлена. Повторяем итерацию для последующих цифр.
Если я не ошибся, то число будет угадано за 20 обращений к CheckNum в среднем ;)
Так как я не знаю оптимального решения, то у меня вопрос: за сколько обращений к checknum оно дает решение?

← →
Piter © (2004-05-27 19:56) [19]

Затея, кстати, интересная, я бы посмотрел на "оптимальный алгоритм"
Такая игра называется "Быки и коровы". Совпадение цифры в нужном разряде - один бык. Если в числе есть такая цифра, но в другом месте - корова.

Играют двое, каждый задумывает число и друг у друга отгадывают.

Так вот - я с седьмого раза (максимум) отгадываю. Бывает с пяти (это хорошо), шести.
Если повезет, то с четырех можно...

Так что оптимальный алгоритм должен как можно меньше, имхо, вызывать функцию проверки числа. Пусть он и будет более медленным...

давайте напишем такой алгоритм :)

← →
Piter © (2004-05-27 20:04) [20]

Кстати, задача очень не тривиальна.

Ведь, допустим, можно с первого раза попасть в четыре цифры, которыъ нету, то есть 0 быков, 0 коров.
Так вот иногда имеет смысл использовать такие заведомо неправильные числа, чтобы проверить другие числа...
Иногда, смысла не имеет...

Я вот вспоминаю ход размышлений при этой игре... блин, алгоритмически это не реализуешь...

Сложная задачка, может, и не шахматы, но аля...

← →
Romkin © (2004-05-27 20:07) [21]

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

← →
Romkin © (2004-05-27 20:20) [22]

Давайте лучше я предложу задачку ;)
Имеем следующий алгоритм шифрования: берется исходный текст, и ключ (число, longint). Инициализируем RandSeed этим числом, далее каждый символ текста складывается операцией xor со случайным числом от 0 до 255 (random(256), подряд). Как видно, зная ключ, можно просто повторить эту операцию и получить исходный текст.
Теперь задача: написать программу, на вход которой подается зашифрованный текст достаточной длины (от 4 Кб), ключ для которого неизвестен, на выходе - расшифрованный текст.
Дополнительное условие: исходный текст - отрывок из художественного произведения на русском языке в кодировке win1251.

← →
Piter © (2004-05-27 21:03) [23]

Romkin (27.05.04 20:07) [21]
Да ладно, алгоритм известен, гугль рулит

какой алгорит? Наименьшй по времени? Возможно, но это не интересно!

А вот алгоритм, который угадывает за наименьшее количество шагов (пусть и долго) - вот покажи мне его. Это будет очень не тривиально... имхо

Romkin (27.05.04 20:20) [22]

я так понимаю, все дело в том, чтобы распознать русский текст?

function isText(s: string): boolean; // дополнительная функция const Alf=["А".."Я", "а".."я"]; var i, Count : integer; begin Count:=0; for i:=1 to length(s) do if s[i] in Alf then inc(Count); if (Count / length(s)) > 0.8 then Result := True else Result := false; end; ... function Decode(Text: string): string; var DecodeText: string; i1, i2: integer; begin setlength(DecodeText, length(text)); for i1:=0 to 255 do begin for i2:=1 to length(Text) do DecodeText[i2]:=chr(ord(Text[i2]) xor i1); if isText(DecodeText) then begin Result:=DecodeText; break; end; end; end;

Имхо, в модернизации нуждается только функция isText...

← →
Romkin © (2004-05-27 21:18) [24]

Нее, ты не понял...
кодинг делается так:
for i2:=1 to length(Text) do
EncodeText[i2]:=chr(ord(Text[i2]) xor random(256));

← →
YurikGl © (2004-05-27 21:30) [25]

Может, проще в Паскале писать, если речь идет только об алгоритме?

Чем вникать в "Романов Р.В. © (27.05.04 10:24) [1]" и "Романов Р.В. © (27.05.04 10:25) [2]", проще самому написать код для проверки алгоритма.

← →
Piter © (2004-05-27 21:43) [26]

Romkin (27.05.04 21:18) [24]
кодинг делается так:
for i2:=1 to length(Text) do
EncodeText[i2]:=chr(ord(Text[i2]) xor random(256));

ничего себе! А задача осуществима? В принципе, я с легкостью перепишу свои алгоритм, чтобы перебирались все варианты для каждой буквы... но выполнение такого цикла, думаю, просто повесит машину, особенно на тексте > 4Kb

← →
Piter © (2004-05-27 21:53) [27]

Romkin (27.05.04 21:18) [24]

не, задача точно не решаема. Получается, каждый символ кодируется своим рандомным ключом.
Соответственно, даже точно узнав ключ от одной буквы, ты не сможешь предположить ключ от другой буквы. Они никак не связаны, если это действительно рандом (randomize не забываем?).

Ты никак не скажешь - запятая тут или точка с запятой. Можно собрать набор недетерминированных предположений, но на выходе точно не получишь исходного текста. Совсем точно

← →
Piter © (2004-05-27 21:55) [28]

нет... точно... это совершенно невозможно... для каждой буквы свой ключ... не верю... никак нельзя

← →
Романов Р.В. © (2004-05-28 07:37) [29]

> Romkin © (27.05.04 19:33) [18]
> Вот еще алгоритм, сорри, но реализацию писать лень...
> Первый этап: генератором случайных четырехзначных чисел
> подбираем такое число, чтобы совпадений цифр не было вообще.
> Если не ошибаюсь, вероятность около 0.65, то есть 1-2 число
> так попадет...
> Второй этап: циклически изменяем первую цифру, пока не появится
> плюс (то есть если это 4, то проходим 5..9,0..3). Первая
> цифра установлена. Повторяем итерацию для последующих цифр.
> Если я не ошибся, то число будет угадано за 20 обращений
> к CheckNum в среднем ;)
> Так как я не знаю оптимального решения, то у меня вопрос:
> за сколько обращений к checknum оно дает решение?

В детстве я писал алгоритм который угадывал примерно за 16-20 ходов.
Щас за час (с перерывами) написал другой. Только что закончилось полное тестирование. Средние показатели намного лучше.

> На современном компьютере результат будет получен за очень
> малое время, в среднем будет выполнено около 4500 циклов,
> что займет где-то четверть секунды максимум :)

Если игра с таким алгоритмом будет играть против человека, когда отгадывание чисел происходит по ходам то у человека явные преимущества :)

← →
Igorek © (2004-05-28 10:10) [30]

Согласен поучавствовать на выходные. Берем задачу "быки коровы".
Код должен:
1) за наименьшее число раз в среднем угадывать искомое число
2) быть коротким

← →
Romkin © (2004-05-28 10:25) [31]

Piter © (27.05.04 21:55) [28] Программа дешифровки у меня есть :). Формализуем:
имеется функция
function CodeText(Key: LongInt; const AText: string): string; var i: integer; begin SetLength(Result, length(AText)); RandSeed := Key; for i := 1 to length(AText) do Result[i] := char(byte(AText[i]) xor random(256)); end;
Берется произвольный неизвестный ключ, и текст как написано выше... На выходе - шифрованный текст. Требуется написать функцию, принимающую шифрованный текст и выдающую дешифрованный, за наименьшее время ;)

← →
pasha_golub © (2004-05-28 10:41) [32]

Romkin © (28.05.04 10:25) [31]

Ромкин - монстр. :-)

← →
pasha_golub © (2004-05-28 10:51) [33]

Romkin © (28.05.04 10:25) [31]

Требую подсказки! :-)))

← →
небритый мужик (2004-05-28 11:02) [34]

> Igorek © (28.05.04 10:10) [30]

2 не обязательно

← →
Romkin © (2004-05-28 11:08) [35]

pasha_golub © (28.05.04 10:41) [32] Если бы :( В общем случае такая задача не решается, а вот в приведенной формулировке - довольно быстро...
И вообще, не люблю меряние самостью. Олимпиадные задачи должны быть полезны. Для форума, хотя бы. Куча вопросов регулярно проходит, почему бы не сделать конкурс на лучшую программу-ответ?
1. Обращение матрицы произвольного вида. На входе - динамический массив, на выходе - обратная матрица и определитель исходной.
2. Нахождение всех корней полинома с действительными коэффициентами произвольной степени.
а. Или разложение полинома на произведение полиномов 1 и 2 степени с действительными коэффициентами - чтобы с комплексными числами не маяться...
3. Сделав 2а, написать программу, которая вычисляет аналитически неопределенный интеграл от рациональной функции (отношение полиномов).
4. Имеется набор записей TRect. Написать объект, хранящий указанный набор, и реализующий методы:
а. На входе - прямоугольник TRect, на выходе - прямоугольник минимального размера из набора, в котором полностью содержится данный.
б. На входе - прямоугольник, на выходе - максимальный из набора, который полностью содержится в данном...
в. Метод, извлекающий прямоугольник минимального размера из данного набора. То есть, "EXTRACT-MIN", метод исключает из набора прямоугольник минимальной площади и выдает его как результат.
Ожидается выполнение всех действий примерно за О(logN) операций.
Годится? Задачи, вроде, нетривиальные, можете пользоваться любыми учебными материалами и тд ;)

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

Романов Р.В.
IMHO
Ты пытаешся тупо цинично копировать задачи которые уже были решины на Олимпиадах. Mногие знают не задумываясь ответы. Tебе надо взять Шень не помню как книга называетя есть в инете там есть не тривиальные задачи причем простые как угол дома

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

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

Кстати автору лучшего задания пиво будет? )))

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

> Романов Р.В. © (28.05.04 07:37) [29]
>
> В детстве я писал алгоритм который угадывал примерно за
> 16-20 ходов.
> Щас за час (с перерывами) написал другой. Только что закончилось
> полное тестирование. Средние показатели намного лучше.

Получил средний показатель 13.9623 для всех четырехзначных чисел. Буду улучшать дальше. Жаль диплом надо еще делать. :)

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

В догонку есть еще Богатырев "Христоматия программирования на С" и "Программирование на для полного дурака" /*названия могут быть не точные*/ тоже кое что можно там дернуть

← →
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

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

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

Я отправил

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

Mystic © (28.05.04 15:19) [65]

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

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

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 публиковался ранее, а теперь в него внесены изменения...

Никто не говорил что он не будет изменен. Я даже предпологал его изменить воизбежание подобных трюков.

Если условие олимпиады это посты с 0-го по 3-тий, то текст модуля OlimpShare входит в условие. Если же условие олимпиады это только первый пост, то не указана спецификация функций FindNum и GetName. К тому же не не оговаривалось то, что запрещены хакерские уловки. Поэтому судейство было нечестным ;)

Условие олимпиады посты с 0-го по 1-вый. Текст модуля OlimpShare не входит в условие и приведен для того что бы участникам не отвлекаться на проверочные функции, а заниматься только разработкой алгоритма поиска.

>Романов Р.В.
ну можешь требовать с Mike Kouzmine приз. он обещал :)

Так нада... :)

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

> nikkie

Я за идею работаю :)

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

В случае большого количества участников разночтения имеют место быть. Знаешь, как обидно, потратить два дня на решение не той задачи ;) Кроме того, нужно будет еще долго трудиться над созданием тестового модуля, чтобы исключить возможность прохода вот таких вот модулей:

unit Olimp; interface function FindNum(): string; function GetName(): string; implementation uses Windows, SysUtils, OlimpShare; function GetName(): string; begin Result := "Mystic"; end; type PPCharArray = ^PCharArray; PCharArray = ^TCharArray; TCharArray = array[0..4] of Char; const MAX_COUNT = 999; function FindNum(): string; var P: PPCharArray; I: Integer; CR: TChekResult; begin // Сохраняем значение стека asm MOV P, ESP end; // Ищем в стеке указатель на строку, состоящую из четырех цифр for I := 0 to MAX_COUNT do begin if not IsBadReadPtr(P^, 5) then begin if (P^[4] = #0) and (P^[0] in ["0".."9"]) and (P^[1] in ["0".."9"]) and (P^[2] in ["0".."9"]) and (P^[3] in ["0".."9"]) then begin CR := CheckNum(AnsiString(P^)); if CR.Plus = 4 then begin // С большой степенью вероятности это задуманное число Result := AnsiString(P^); Exit; end; end; end; PChar(P) := PChar(P) + 4; end; // Неудача --- тупо перебираем все значения. for I := 0 to 9999 do begin CR := CheckNum(Format("%4d", [I])); if CR.Plus = 4 then begin Result := Format("%4d", [I]); Exit; end; end; end; end.

(какой он вернет результат???)

> Mystic © (01.06.04 15:10)

Так у Вас syntax highlight кода JavaScript"ом производится или отдельной программой(типа pas2html)?

Mystic ©
Хорошо к составлению заданий для следующей олимпиады подойду более ответственно.
А номер со стеком не пройдет. Можно устроить ловушку и забросить туда ложные данные. Можно изменить тип хранящихся данных или зашифровать. И наконец можно не хранить данные в стеке.

Обрашение ко всем.
Присылайте интересные задания по адресу RSoftComp<собака>mail.ru
Вторая олимпиада будет проведена в конце ИЮНЯ.

Романов Р.В.
Лови

Романов Р.В.

блин не, не лови книжка с диска куда то делась

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