Форум: "Потрепаться";
Текущий архив: 2004.01.16;
Скачать: [xml.tar.bz2];
Вниз
Нужна помощь... задача на комбинаторику... Найти похожие ветки
← →
otido (2003-12-24 00:39) [0]Здравствуйте! Очень сильно горит очень хороший человек (не я..)
задали задачку, что-то с чем-то... и никак не решить( глупо(( но больше некуда обратиться..
КРУГЛЫЙ циферблат сейфового замка состоит из ста кнопок (нумерованы 1-100), для того, чтобы открыть, надо три правильные кнопки нажать, причем между двумя любыми правильными минимум должно находиться на циферблате 10 неправильных. Найти кол-во переборов для открытия при наихудшем варианте..
причем порядок нажатия кнопок правильных неважен (т.е. 1, 20, 30 эквивалетно 1, 30, 20)
путем применения грубой силы (ТP 7.0) выяснили, что таких комбинаций по три кнопки, если первая из них постоянна, а две меняются, которые удовлетворяют условию про минимум - 2346... это с такими повторами, как показано выше.. а дальше ступор(
еще и не могу никак это 2346 доказать "на пальцах"..
в приципе, в этом и загвоздка.. дальше всё вроде как укладывается, 2346/3=782, это без вышеуказанных повторов.. и учитывая смену первой кнопки по всему циферблату, умножаем на 100...
Эни айдиас? Будем очень благодарны..
С уважением, otido.
← →
otido (2003-12-24 01:01) [1]спасибо всем, кто начал думать, и спокойной ночи))) отбой))
ЗЫ
что смешно, насчет этой задачи свои люди позвонили даже в Тель-Авивскую профессуру....))
← →
Igorek (2003-12-24 01:14) [2]
procedure TForm1.Button1Click(Sender: TObject);
var
I,J,K,Count: Integer;
begin
Count := 0;
for I:=1 to 100-22 do
for J:=I+11 to 100-11 do
for K:=J+11 to 100 do
Inc(Count);
Label1.Caption := IntToStr(Count);
end;
← →
Igorek (2003-12-24 01:20) [3]Ой, неправильно. Но думать надо в этом направлении. Лучше вообще три цикла от 1 до 100 и проверка внутри. Потом делить на 6. Тупо, но сработает.
← →
Igorek (2003-12-24 01:25) [4]
Uses Math;
...
procedure TForm1.Button1Click(Sender: TObject);
var
I,J,K,Count: Integer;
begin
Count := 0;
for I:=1 to 100-22 do
for J:=I+11 to 100-11 do
for K:=J+11 to Min(100, 100+I-11) do
Inc(Count);
Label1.Caption := IntToStr(Count);
end;
Вроде правильно, но могу с полуночи и ошибиться.
← →
Nikolay M. (2003-12-24 09:39) [5]
> отбой))
Так ты решил или забил?
2346 получается просто:
i1, i2, i3 - позиции.
фиксируем i1=1, тогда i2 может меняться от 12 до 79 (68 вариантов), i3 меняется так:
i2 = 12 => i3 = 23..90 (68 вариантов)
i2 = 13 => i3 = 24..90 (67 вариантов)
....
i2 = 79 => i3 = 90 (1 вариант)
налицо арифметическая прогрессия, сумма считается по формуле
Sn = (a1 + an) * n / 2
поэтому при фиксированном i1 = 1 получается
(68 + 1) * 68 / 2 = 2346.
Но вопрос - что значит "кол-во переборов при наихудшем варианте"? Какой предполагается алгоритм подбора кода? Фиксирование первых двух цифр, третья пробегает допустимый диапазон, сдвиг второй, третья опять бегает и тп?
← →
Bless (2003-12-24 11:28) [6]Я уже подзабыл формулы комбинаторики, поэтому поясню словами, а ты уж сам в конспект загляни.
Для вычисления общего количества комбинаций "3-х чисел из 100 исключая повторения" есть формула комбинаторики. См. конспект (если не ошибаюсь, пишется как
3
С - Цэ из ста по три
100
но я могу и ошибиться. Поэтому смотри конспект).
Из этого количества надо вычесть 1000 и получишь то, что тебе надо, как мне кажется.
P.S. Может, все вышенаписанное и неправильно, но как вариант, рассмотреть и обсудить можно.
P.P.S. Когда узнаешь правильный ответ, сообщи плз в ветку.
← →
Bless (2003-12-24 11:29) [7]Ошибка! Вычесть надо 900.
← →
Bless (2003-12-24 11:50) [8]Если c формулами комбинаторики проблема, то:
если не сильно поджимает, могу посмотреть формулы дома. Тогда скажу ответ завтра.
Если поджимает, могу попробовать их вывести сам сегодня.
>что значит "кол-во переборов при наихудшем варианте"
Ну, ведь может подфартить, и первая набранная комбинация будет правильной. Ну а худщим, соответственно, будет вариант, когда правильной оказалась последняя из возможных комбинаций.
Очевидно, что "кол-во переборов при наихудшем варианте" равно количеству комбинаций из трех чисел, удовлетворяющих условиям задачи.
← →
Bless (2003-12-24 12:15) [9]>Ошибка! Вычесть надо 900.
Вычесть надо все-таки 1000. :)
← →
otido (2003-12-24 18:54) [10]1)
> Так ты решил или забил?
решили мы)) совместно))
2)
> что значит "кол-во переборов при наихудшем варианте"?
см. [8]
===========================
так вот,
НА 78200-ой комбинации просто обязано повезти.. )) почему 78200???
2346 это число всех комбинаций. я упоминал про повторы. Циферблат круглый, порядок нажатия неважен, поэтому случаи промежутков между кнопками 10 10 77, 10 77 10, 77 10 10 - один черт. Прэтому 2346 делим на три. НО как я писал собсссно в условии, это для ОДНОГО И ТОГО ЖЕ первОГО числа кода. А таких чисел будет 100, так как это число смещаем 100 раз, по кругу.. то есть 782*100.
Вот-с.. во всяком случае это решение признали за правильное..
==============
вот что я не понял - это вычитание 1000.. куда его поставить?)))
ВСЕМ ОГРОМНОЕ СПАСИБО!!!!!!
← →
Vilmo4ka (2003-12-24 19:41) [11]Спасибо всем кто "попотел" над этой задачкой;) Собсна, задачка задавалась мне, ну я ее совместно с автором топика и решила)
То что результатов 2346\3=782 это было относительно сложно))) но сложнее было не это - оказалось, что вся задача свелась к тому чтоб не с помощью "грубой силы", а "на пальцах"..
Николай М. респект это как раз то=), что меня осенило к полуночи..
Всем спасибо еще раз - тренируйте мозги;)
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2004.01.16;
Скачать: [xml.tar.bz2];
Память: 0.48 MB
Время: 0.01 c
