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

← →
Романов Р.В. © (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]

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

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

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

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

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

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

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;
Берется произвольный неизвестный ключ, и текст как написано выше... На выходе - шифрованный текст. Требуется написать функцию, принимающую шифрованный текст и выдающую дешифрованный, за наименьшее время ;)

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

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

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

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

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

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

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

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

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

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

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

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

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