Задача про приборы

← →
palva © (2005-09-24 00:28) [40]

Для F(6) задача может быть решена за 3 измерения без предположения о детерминированности показаний неисправного прибора. Я исписал лист бумаги (типа полного перебора) и придумал алгоритм. Но этот алгоритм "безыдейный", его нельзя распространить на большее число приборов. Ну а полным перебором заниматься не интересно. Хотя если поставить вопрос о написании компьютерной программы, реализующей полный перебор, то может быть и можно повозиться.

← →
default © (2005-09-24 00:34) [41]

palva © (24.09.05 00:28) [40]
ясно...если исходить из того что тот алгоритм оптимальный, то из моего примера это значит что предположение всё-таки Ваше использовалось...
мда...пусть народ думает для Вашего предположения тогда, а я уже на своё предположение и так сколько бумаги извёл...
завтра утром посмотрим что народ скажет...

← →
SergP. (2005-09-24 00:35) [42]

> есть алгоритм дающий как надо F(6)=3; F(8)=4; F(10)=7

Взял конкретный случай с N=6...
Как ни старался, но вижу что 3 - это мало.

Поэтому в то что F(6)=3 я не верю...

← →
palva © (2005-09-24 01:16) [43]

Могу расписать алгоритм для 6.
Обозначим через m->n = +/- тот факт, что проверяя при помощи прибора m прибор n получаем положительный (+) или отрицательный (-) результат. Еще одно замечание: если при измерении получен минус то либо один, либо другой прибор не исправен. Теперь алгоритм.
Измеряем 1->2 и 3->4.
Если оба минуса, то уже обнаружили два неисправных прибора, поэтому немерянные 5 и 6 исправные. В случае если два плюса то разбираем варианты:
_1234 1++++ 2-+++ 3--++ 4++-+ 5-+-+ 6---+ невозможен (много минусов) 7++-- 8-+-- невозможен 9---- невозможен
Теперь меряем 2->4 Если +, то невозможна 7 строчка, поэтому 4 - исправен. Если -, то невозможна 1,2,4,5 строчки, остаются строчки 3 и 7, которые имеют два минуса, следовательно 5 и 6 исправные.

Теперь пусть один -, другой + Из двух симметричных случаев разберем случай
1->2 = -, 3->4 = +
Опять перечисляем варианты:
+1234 1--++ 2-+++ 3+-++ 4---+ невозможен 5-+-+ 6+--+ 7---- невозможен 8-+-- невозможен 9+--- невозможен
Без третьего измерения видим, что 4 исправен.

← →
SergP. (2005-09-24 06:08) [44]

> palva © (24.09.05 01:16) [43]
> Могу расписать алгоритм для 6.

Да... Я был не прав в [42]

В связи с [43] у меня появились такие мысли:

Очевидно что f(3)=1, f(4)=1, а также исходя из [43] видно что f(5)=3, f(6)=3

Далее если N четное, то проверяем попарно 1->2, 3->4 ... N-3 -> N-2

отого имеем N/2-1 сравнений.

если N нечетное, то проверяем попарно 1->2, 3->4 ... N-2 -> N-1

отого имеем (N-1)/2 сравнений.

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

В полученной групе снова кол-во исправных приборов будет больше чем неисправных.

т.е. F(2*K) = F(2*K-1) = K-1+F(K)

← →
MBo © (2005-09-24 06:23) [45]

>default
К сожалению, я сломался ;), решил, что задача мне не по зубам.
Решения я не знаю, но ответ имеется.

← →
SergP. (2005-09-24 06:44) [46]

Хмм.. Если записать в рекурсивном виде, то получается:

function F(n:integer):integer; begin n:=(n+1) div 2; if n <= 2 then result := n-1 else result := n - 1 + F(n); end;

А вот формулу для вычисления F(n) пока не могу придумать...

← →
default © (2005-09-24 11:32) [47]

MBo © (24.09.05 06:23) [45]
если интересен [35] то распишу
только там предположение [19]

← →
default © (2005-09-24 11:43) [48]

palva © (24.09.05 00:13) [38]
что-то я Ваше "n + (n-3)/2 измерений." не пойму
n понятно, потом осталось n-2 приборов казалось бы должно быть
n+(n-2)+(n-4)++(n-6)+...
или как?

← →
palva © (2005-09-24 13:35) [49]

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

← →
default © (2005-09-24 13:39) [50]

SergP. (24.09.05 06:08) [44]
ну что можно сказать - БРАВО!
похвально ухватили из [43] нужный алгоритм, хотя прямого следствия нет, но зацепка была и Вы ей воспользовались
хотелось бы более строгого обоснования, но это при необходимости может сделать каждый

← →
default © (2005-09-24 13:42) [51]

palva © (24.09.05 13:35) [49]
сейчас почитаю, но SergP уже нашёл алгоритм

← →
default © (2005-09-24 16:37) [52]

кто не понял алгоритм SergP в [44] могу расписать подробно(
пока время есть...

← →
stud © (2005-09-26 11:51) [53]

>найден линейный алгоритм который даёт:
>F(1)=0; F(2)=0;
> F(3)=1; F(4)=1;

это почему?????
если у нас 3 прибора - это значает что 1 из них неисправный.
начинаем измерять (неисправный прибор постоянно показывает ДА) и нам попадается сразу неисправный - результат нулевой, проведя 2 измерения мы не сможем точно сказать какой прибор неисправен

← →
stud © (2005-09-26 13:15) [54]

наихудший вариант в данной ситуации - все неисправные приборы дают положительный результат и при измерениях первыми попадаются именно они.
и как интересно в этой ситуации выполучите f(3)=1.
это справедливо если неисправный сразу покажет нет!

← →
Igorek © (2005-09-26 13:40) [55]

> stud © (26.09.05 13:15) [54]

Ты бы читал условие внимательно прежде чем писать.

← →
stud © (2005-09-26 13:53) [56]

> Ты бы читал условие внимательно прежде чем писать.

>default © (23.09.05 17:38) [19][Ответить]
>stud © (23.09.05 17:36) [18]
> сломаный прибор всегда показывает НЕТ или всегда ДА
> всё остальное отсюда вытекает

← →
SergP. (2005-09-26 14:33) [57]

> stud © (26.09.05 11:51) [53]
>
> >найден линейный алгоритм который даёт:
> >F(1)=0; F(2)=0;
> > F(3)=1; F(4)=1;
>
> это почему?????
> если у нас 3 прибора - это значает что 1 из них неисправный.
>
> начинаем измерять (неисправный прибор постоянно показывает
> ДА) и нам попадается сразу неисправный - результат нулевой,
> проведя 2 измерения мы не сможем точно сказать какой прибор
> неисправен

Возьмем 3 (или 4) прибора. Ясно что неисправный в данном случае будет только 1.

Прибором 1 проверяем прибор 2.
Если результат отрицательный - то значит один из первых двух - неисправный, следовательно исправный - оставшийся (либо один из оставшихся (если их всего было 4).

Если результат положительный, то прибор 2 исправный, так как если неисправный прибор всего один, и если бы он был вторым то первым был бы исправный, и мы бы получили отрицательный результат.

← →
SergP. (2005-09-26 14:39) [58]

> SergP. (24.09.05 06:44) [46]
> Хмм.. Если записать в рекурсивном виде, то получается:
>
>
> function F(n:integer):integer;
> begin
> n:=(n+1) div 2;
> if n <= 2 then result := n-1
> else result := n - 1 + F(n);
> end;
>
>
> А вот формулу для вычисления F(n) пока не могу придумать.
> ..

Пока есть формула работающая правильно только для количества приборов равного 2 в целой степени:

F(N)=N-Log2(N)-1

Для остальных количеств иногда получается сильно большая погрешность....

← →
КаПиБаРа © (2005-09-26 14:48) [59]

SergP. (26.09.05 14:39) [58]
Пока есть формула работающая правильно только для количества приборов равного 2 в целой степени
Тогда может в двоичной форме записи формулу проще будет вывести?

← →
Igorek © (2005-09-26 14:51) [60]

Я не могу понять. Зачем вы ищете линейный алгоритм? Ну найдете и что? Условие не в том.
Вот:

> Цель - найти хотя бы один исправный прибор.
> Какое минимальное количество проверок придётся сделать в
> худшем случае?

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

← →
stud © (2005-09-26 14:54) [61]

> Если результат положительный, то прибор 2 исправный

тогда в чем проблема???
мы абсолютно точно можем найти максимальное количество неисправных приборов.
тогда берем ЛЮБОЙ прибор и по очереди проводим n/2-1 измерений (если кол-во нечетное округляется в меньшую сторону) и все! в этом случае за указанное число шагов исправный находтися 100%

← →
SergP. (2005-09-26 15:02) [62]

> мы абсолютно точно можем найти максимальное количество неисправных
> приборов.

А зачем нам это нужно? Ведь цель - найти хотя бы 1 исправный...

> тогда берем ЛЮБОЙ прибор и по очереди проводим n/2-1 измерений
> (если кол-во нечетное округляется в меньшую сторону) и все!
> в этом случае за указанное число шагов исправный находтися
> 100%

А если этот "ЛЮБОЙ" прибор оказался неисправным, то он будет показывать не то что на самом деле... и мы так ничего не найдем...

← →
umbra © (2005-09-26 15:32) [63]

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

← →
stud © (2005-09-26 15:44) [64]

> А если этот "ЛЮБОЙ" прибор оказался неисправным,

по условию задачи

> Одним прибором можно проверить другой, результат
> проверки - исправен проверяемый прибор или нет.

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

> А зачем нам это нужно? Ведь цель - найти хотя бы 1
> исправный...

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

← →
umbra © (2005-09-26 15:54) [65]

исходя из того, что исправных приборов больше, то можно проделать следующее. Берем любой прибор и проверяем его исправность всеми остальными (n-1 измерение). Каких ответов будет больше, тот и верный, поскольку исправных приборов больше. Если больше ответов "исправен", то выбранный прибор действительно исправен. Если больше ответов "неисправен", то отбираем все приборы, давшие такой ответ. Среди них все исправные, и, возможно, несколько неисправных. Из них опять берем любой и повторяем процедуру. В лучшем случае надо n-1 измерений. Количество измерений в худшем случае равна x*n*(n-1), 0.5<x<1 - доля исправных приборов.

← →
umbra © (2005-09-26 15:57) [66]

> x*n*(n-1)

это бред. погорячился.

← →
stud © (2005-09-26 16:11) [67]

еще вот

> А если этот "ЛЮБОЙ" прибор оказался неисправным, то он
> будет показывать не то что на самом деле... и мы так
> ничего не найдем...

а как вы получили тогда ф(3)=1 ??

← →
SergP. (2005-09-26 19:47) [68]

> а как вы получили тогда ф(3)=1 ??

см. [57]

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

Даже у Жванецкого есть что сказать про эту задачу:

- А что это шесть часов все время?!
- Это манометр.

← →
SergP. (2005-09-26 20:47) [71]

> stud © (26.09.05 16:11) [67]
> еще вот
>
> > А если этот "ЛЮБОЙ" прибор оказался неисправным, то он
>
> > будет показывать не то что на самом деле... и мы так
> > ничего не найдем...
>
> а как вы получили тогда ф(3)=1 ??

Для ф(3) тут и думать не нужно. Ясно что за 0 проверок мы нифига не найдем, а 1 проверка согласно [57] - абсолютно достаточно для того чтобы определить исправный прибор со 100% гарантией. Поэтому ф(3)=1

Для базы рекурсии полезно даже положить
ф(1) = ф(2) = 0

SergP. (26.09.05 20:47) [71]
предлагаю Вам всё-таки популярно объяснить желающим решение задачи
всё-таки решили, но описали только алгоритмистику, не каждый видит за ней идеи к ней приведшие
а то мне как-то за Вас неохота писать:) а для завершённости обсуждения всё-таки стоит....

> [57]

Если в этом посте речь идет о задаче из поста 0, то изложенное не верно. как я понял из условия, неисправные приборы могут выдавать ЛЮБЫЕ ответы в ЛЮБОЙ последовательности при проверке ЛЮБЫХ приборов. В таком случае из единственного измерения невозможно определить состояние ни изиерителя ни измеряемого. Нет определения "отрицательного" ответа, поскольку сломанный прибор дает ЛЮБЫЕ ответы в ЛЮБОЙ последовательности

default © (27.09.05 11:11) [73]
Да, интересует главным образом доказательство индукционного шага. Может оно и не сложно, но сходу я не вижу.

umbra © (27.09.05 11:47) [74]

> В таком случае из единственного измерения невозможно определить состояние ни измерителя ни измеряемого
Но, учитывая, что исправных приборов больше, можно сделать умозаключение. Например, если приборов только три, а некоторое измерение дало отрицательный результат, можно сделать заключение, что прибор который НЕ УЧАСТВОВАЛ В ИЗМЕРЕНИИ, исправен.

> Нет определения "отрицательного" ответа
Ну наверно можно определить так, что когда мы проверяем один прибор другим, на шкале прибора или на индикаторе появляется надпись "не исправен".

самое сложное в этой задаче - это условие))) каждый понимает его как нравится
отсюда и заявления, которые противоречат друг другу

> SergP. (26.09.05 20:47) [71] [Новое
> сообщение][Ответить]

перечитайте этот пост и сделайте вывод, подсказка:

А если этот "ЛЮБОЙ" прибор оказался неисправным, то он
будет показывать не то что на самом деле... и мы
так ничего не найдем...

Для ф(3) тут и думать не нужно. Ясно что за 0 проверок
мы нифига не найдем, а 1 проверка согласно [57] - абсолютно достаточно

а вам для измерений однозначно попадается исправный прибор? зачем тогда вообще алгоритм нужен?))

> stud

> а вам для измерений однозначно попадается исправный прибор?

> palva

> Ну наверно можно определить так, что когда мы проверяем
> один прибор другим, на шкале прибора или на индикаторе появляется
> надпись "не исправен".
>

так если сам прибор, на шкале которого надпись появляется неисправен, то надпись может быть любая! "исправен", "неисправен" - какая разница! если измеряющий прибор неисправен, то надпись можно забыть. Но как раз об исправности его мы и не знаем ничего.

и я о том же.

> прибор который НЕ УЧАСТВОВАЛ В ИЗМЕРЕНИИ, исправен.

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

umbra © (27.09.05 14:24) [77]
> какая разница! если измеряющий прибор неисправен, то надпись можно забыть.
Конечно, можно забыть. Но можно и использовать, для того чтобы решить задачу.

> Но как раз об исправности его мы и не знаем ничего.
И не узнаем за одно измерение.

> и проверить высказывания конкретного измеряющего прибора невозможно
Конечно, невозможно. Но нам ведь это и не нужно. Мы хотим решить задачу, то есть найти исправный прибор.

да, если получить при первом измерении ответ "неисправен", то незадействованый прибор исправен. А если получен ответ "исправен"? тогда нужно еще одно измерение. => вывод [57] неверен. ф(3)=2

> А если получен ответ "исправен"? тогда нужно еще одно измерение.

Докажи, что второй прибор может быть неисправен.

Задача про приборы Найти похожие ветки