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

← →
Igorek © (2005-09-27 15:48) [80]

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

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

← →
stud © (2005-09-27 16:03) [81]

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

господа, вы что издеваитесь??)))
если получен ответ ИСПРАВЕН - это еще не значит что измеряемый прибор исправен, т.к. неисправный ИЗМЕРЯЮЩИЙ прибор может показать ЧТО УГОДНО.
ЧТО УГОДНО = (ИСПРАВЕН на неисправном приборе,
ИСПРАВЕН на исправном приборе, НЕИСПРАВЕН на исправном приборе, НЕИСПРАВЕН на неисправном)
и объясните какой вариант вы выбираете и почему?

← →
stud © (2005-09-27 16:08) [82]

а вообще, отметьте нужное

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

2.прибор которым проверяем исправно проверяет, но может быть несиправным

а потом можно продолжать, а то на разных языках разговариваем)))

← →
umbra © (2005-09-27 16:16) [83]

> stud

Полностью согласен.

> Igorek

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

← →
Igorek © (2005-09-27 16:44) [84]

> господа, вы что издеваитесь??)))

ага :)

> если получен ответ ИСПРАВЕН - это еще не значит что измеряемый
> прибор исправен, т.к. неисправный ИЗМЕРЯЮЩИЙ прибор может
> показать ЧТО УГОДНО.

гениально! как ты додумался? :)
--
естественно, что второй прибор исправен не потому, что так показал первый, а потому, что можно сделать такой умовывод см.[57].

А вообще повторяю вопрос:> Докажи, что второй прибор может быть неисправен..

← →
Igorek © (2005-09-27 16:45) [85]

> ЧТО УГОДНО =

Одно их сообщений "исправен", "неисправен".

← →
stud © (2005-09-27 17:09) [86]

> Igorek © (27.09.05 16:45) [85] [Новое
> сообщение][Ответить]

см.

> stud © (27.09.05 16:08) [82][Ответить]

после ответа на вопрос можно что-то доказывать.

← →
stud © (2005-09-27 17:10) [87]

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

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

← →
Igorek © (2005-09-27 17:26) [88]

> с таким же успехом можно сделать умовывод что этот прибор
> неисправен)))

ну сделай! с меня пиво! :)

> stud © (27.09.05 16:08) [82]

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

1. конечно "или"
2. не может такого быть (он может дать правильный ответ, а может дать неправильный)

← →
stud © (2005-09-27 17:32) [89]

уууууу, все что нужно было - выбрать вариант 1 или 2 (т.к. это несовместимые варианты)
который соответствует условию задачи)))

← →
umbra © (2005-09-27 17:33) [90]

> не может такого быть (он может дать правильный ответ, а
> может дать неправильный)

согласно условиям - может. он что-то показывает от фонаря. В одних случаях угадывает, в других - нет

← →
stud © (2005-09-27 17:36) [91]

> 2. не может такого быть (он может дать правильный
> ответ, а может дать неправильный)

наверное я не очень понятно выразился:
прибор которым проверяем - исправно проверяет, но если проверять его самого то он может быть неисправным.

← →
stud © (2005-09-27 17:48) [92]

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

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

← →
umbra © (2005-09-27 17:53) [93]

> результат проверки - исправен проверяемый прибор или нет

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

← →
stud © (2005-09-27 17:54) [94]

вы же хотите сказать

> гениально! как ты додумался? :)

, что неисправный прибор, если мы будем им проверять другой прибор может выдать любой результат, который может не соответсвовать действительности. в этом случае (в худшем случае, который мы и рассматриваем) задача НЕ ИМЕЕТ решения. по той простой причине, что сколько бы измерений вы не производили вы никогда НЕ НАЙДЕТЕ НЕИСПРАВНЫЙ прибор - соответственно не зная какие приборы неисправны делать умовывод о том какие исправны.......

← →
umbra © (2005-09-27 17:57) [95]

> задача НЕ ИМЕЕТ решения

а как насчет поста 65?

← →
stud © (2005-09-27 18:00) [96]

> а как насчет поста 65?

если исходить из > stud © (27.09.05 17:48) [92][Ответить]
</I

то ответ был еще в

> stud © (23.09.05 16:21) [13][Ответить]

результат n/2 - округляется в меньшую сторону
и он кажется оптимальнее чем в 65))

← →
Igorek © (2005-09-27 18:12) [97]

> задача НЕ ИМЕЕТ решения. по той простой причине, что сколько
> бы измерений вы не производили вы никогда НЕ НАЙДЕТЕ НЕИСПРАВНЫЙ
> прибор

а нам это и не нужно!
--
мне уже смешно..

← →
stud © (2005-09-27 18:17) [98]

> а нам это и не нужно!

мне тоже

← →
SergP. (2005-09-27 18:21) [99]

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

Еще раз про ф(3)=1, если кто не понял....

Наша задача согласно условию : вычислить один исправный прибор, а остальные нас не интересуют....

Мы имеем три прибора: А, Б, В
так как исправных больше, то неисправных может быть не более одного...
Надеюсь с этим все согласны?

Делаем единственную проверку: Проверяем прибором А прибор Б
Если результат отрицательный, значит либо А либо Б неисправен (либо А врет, либо говорит правду что прибор Б неисправен.). Следовательно нам нужно взять прибор С. (он будет 100% исправен, так как неисправный только один и он либо А либо Б)

Если ответ положительный, то это значит что либо оба прибора А и Б исправны, либо А неисправен (но показывает правильный результат).
Т.е. прибор Б в таком случае не может быть неисправным. Значит мы выбираем Б.

Итого: для 3 приборов (как и для 4) достаточно одной проверки.

Для общего случая напишу позже... А то конект нестабильный

← →
palva © (2005-09-27 18:29) [100]

stud © (27.09.05 16:03) [81]

> господа, вы что издеваитесь??)))
если получен ответ ИСПРАВЕН - это еще не значит что измеряемый прибор исправен, т.к. неисправный ИЗМЕРЯЮЩИЙ прибор может показать ЧТО УГОДНО.
ЧТО УГОДНО = (ИСПРАВЕН на неисправном приборе,
ИСПРАВЕН на исправном приборе, НЕИСПРАВЕН на исправном приборе, НЕИСПРАВЕН на неисправном)
и объясните какой вариант вы выбираете и почему?

Значит, получен ответ ИСПРАВЕН.
Вариант ИСПРАВЕН на неисправном приборе отбрасываем, потому что в этом случае мы бы получили ответ НЕИСПРАВЕН.
Последний варинат НЕИСПРАВЕН на неисправном также отбрасываем, поскольку в этом случае неисправных приборов два, а их по условию задачи должно быть меньше исправных. Если вспомнить, что у нас всего три прибора, то неисправных может быть максимум один.
Два оставшихся варианта имеют исправный измеряемый прибор. То есть второй прибор гарантированно исправен.

← →
stud © (2005-09-27 18:29) [101]

> Делаем единственную проверку: Проверяем прибором А
>прибор Б
> Если результат отрицательный, значит либо А либо Б
> неисправен (либо А врет, либо говорит правду что
> прибор Б неисправен.).

ну наконец-то))))

> Если результат отрицательный, значит либо А либо Б
> неисправен
никак не вяжется с

> Если ответ положительный, то это значит что либо оба
> прибора А и Б исправны, либо А неисправен (но
> показывает правильный результат).
т.к. в первом случае мы однозначно знаем, что прибор В неисправен
тогда ответ для общего случая см. 96

← →
stud © (2005-09-27 18:32) [102]

> Если вспомнить, что у нас всего три прибора

а если принесли еще 10?))

← →
stud © (2005-09-27 18:35) [103]

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

← →
umbra © (2005-09-27 18:43) [104]

> выбросить все приборы кроме 2-х

трех :))

> То есть второй прибор гарантированно исправен.

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

← →
SergP. (2005-09-27 19:17) [105]

Общее решение более детальнее:

У нас есть N приборов.
Групируем их попарно, так чтобы получить несколько пар (сколько получится), и один или два прибора откладываем отдельно (1 если общее количество нечетно, 2 если четно).

Итого имеем (N-2)/2 пар (для четного N) + 2 прибора отдельно
(N-1)/2 пар (для нечетного N) + 1 прибор отдельно.

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

Возможные результаты проверки:
Положительный ответ: либо оба исправны, либо оба неисправны, либо проверяющий неисправен, хотя и показывает верный результат.

Отрицательный ответ: либо один из приборов неисправен, либо оба неисправны.

Думаю с этим все согласны.

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

Надеюсь и с этим все согласны...

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

Остальные выкидываем нафик...

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

Итого: (для четного N) мы сделали (N-2)/2 проверок (для четного N) и уменьшили количество приборов до N/2 в худшем случае, ( в лучшем остается их еще меньше) причем исправных там больше чем неисправных.
Для нечетного N почти аналогично...

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

← →
stud © (2005-09-28 09:10) [106]

> Теперь выкидываем нафик (и более не вспоминаем про
> них) все пары где получен отрицательный результат.

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

← →
Verg © (2005-09-28 09:25) [107]

Примерно так:

N-1 приборами проводим проверку N-ого

1. Большинство сказало "исправен" - прибор найден: N-ый исправен. Конец.
2. Большинство сказало "неисправен":
Относим N-ый и тех, которые сказали "исправен" к неисправным.
3. Оставшимися (кандидатами в исправные) приборами проводим тестирование любого из отнесенных к несиправным, кроме уже прошедших тестирование (N-ого в случае первой итерации) и повторяем итерацию с п.1

← →
stud © (2005-09-28 09:29) [108]

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

> Verg

нашего полку прибыло

> что у нас нет отрицательных результатов,а исключительно
> положительные

Это значит, что все исправные измеряющие приборы попали в пару с исправными измеряемыми, а все остальные исправные приборы - измеряемые. Если всего приборов N, из которых исправных k, а неисправных m, и исправных больше, то даже если все испаравные попадут в пару с исправными, а неисправные - с неисправными, то после отбрасывания измеряющих исправных будет все равно больше. тут все правильно. Непонятно только, как мы получим тот самый последний прибор. И вызывает глубокое сомнение, что общее количество измерений будет меньше, чем в способе из 65 и 107, которые могут привести к ответу на любой итерации. Насчет ответа из 13 - а где обснование?

> Это значит, что все исправные измеряющие приборы
> попали в пару с исправными измеряемыми

или неисправные попали в пару с неисправными..
ответ из 13 основывается на

> stud © (26.09.05 15:44) [64][Ответить]

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

SergP. (27.09.05 19:17) [105]

> В результате получаем некоторое кол-во приборов среди которых испавных больше чем неисправных...
Это объясню потом, так как долго объяснять, но возможно сами поймете и мне не придется объяснять.

Я начал это обдумывать и натолкнулся на такой пример: У нас было семь приборов. Разместим их в виде двух строчек и меряем прибором из нижней строчки прибор стоящий над ним.

++--
++-

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

+++++-----
+++++----

Может быть я что-то упустил из алгоритма?

umbra © (28.09.05 10:24) [109]
А в 65 и 107 разве предложен алгоритм? Пусть у меня три прибора. Я померял третий первым и вторым, получил разные результаты, дальше что делать - непонятно.

> Пусть у меня три прибора

это частный случай и его вроде уже разобрали
в

> palva © (27.09.05 18:29) [100][Ответить]

stud © (28.09.05 11:17) [112]
Случай разобрали, но я же попробую применить к этому случаю алгоритм 107, чтобы объяснить, что это не алгоритм. Там есть тупиковая ситуация, т. е. когда при первых же (n-1) измерениях мы получаем равное количество отрицательных и положительных результатов. Для того, чтобы показать что такая ситуация возможна, я и взял конкретный случай. Но можно придумать подобный случай и с пятью приборами.

> Там есть тупиковая ситуация, т. е. когда при первых же (n-
> 1) измерениях мы получаем равное количество отрицательных
> и положительных результатов.

Это зависит от того, как определить термин "большинство исправных".
Утв.:

Большинство - это когда (исправных) > N/2 + 1

> Большинство - это когда (исправных) > N/2 + 1

а разве 2<1??
большинство это (исправных) > N/2

> а разве 2<1??

Это тут при чем?

> большинство это (исправных) > N/2

Хорошо, можно и так. Теперь обратно к случаю с семью приборами. Половина приборов - это сколько? Я утверждаю, что 4 по правилам округления.

исправных д.б > 4, чтобы условия задачи выполнялись.

:)))

> Я померял третий первым и вторым, получил разные результаты,
> дальше что делать - непонятно.

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

и исправных всего на 1 больше чем неисправных

umbra © (28.09.05 12:41) [118]
Ага, теперь алгоритм стал понятным, и главное он дает правильный результат. Теперь сколько измерений потребуется в наихудшем случае. Наихудший случай, это когда мы каждый раз меряем неисправный прибор и каждое измерение говорит, что он неисправный. Мерять тогда придется до тех пор пока не выбросим половины приборов минус один, а число измерений составит
(n-1)+(n-2)+...+(n -(n/2)) т.е. где-то (3/8)*n^2
Получается, что это квадратичный алгоритм.

Тем не менее в [38] уже приводился линейный алгоритм. Число измерений там n + (n-3)/2

> (n-1)+(n-2)+...+(n -(n/2))

я невнимательно читал 107. он отличается от 65 тем, что в 65
мы отбрасываем не 1 прибор каждый раз, а 1 + (все приборы, давшие ответ "исправен"). Определить точное количество для каждого шага невозможно, поскольку оно случайным образом зависит от ответов неисправных приборов. Я не в состоянии, честно говоря, оценить общее количество измерений

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