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

← →
umbra © (2005-09-28 15:33) [120]

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

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

← →
SergP. (2005-09-28 15:38) [121]

> palva © (28.09.05 11:10) [111]
> SergP. (27.09.05 19:17) [105]
>
> > В результате получаем некоторое кол-во приборов среди
> которых испавных больше чем неисправных...
> Это объясню потом, так как долго объяснять, но возможно
> сами поймете и мне не придется объяснять.
>
> Я начал это обдумывать и натолкнулся на такой пример: У
> нас было семь приборов. Разместим их в виде двух строчек
> и меряем прибором из нижней строчки прибор стоящий над ним.
>
>
> ++--
> ++-
>
> Все измерения дали положительный результат, но после выкидывания
> нижней строчки неисправных приборов становится столько же
> сколько и исправных. Можно построить подобный пример с большим
> числом приборов, например:
>
> +++++-----
> +++++----
>
> Может быть я что-то упустил из алгоритма?

Да. Упустил...

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

← →
SergP. (2005-09-28 15:49) [122]

Дополнение к [121]

> ++--
> ++-

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

Если же получим например:

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

то тогда берем всю верхнюю строчку (чтобы было нечетное число)

← →
Igorek © (2005-09-28 16:34) [123]

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

← →
umbra © (2005-09-28 17:01) [124]

> "худшем случае"

это максимально возможное значение минимально необходимого числа измерений.

← →
default © (2005-09-28 17:01) [125]

Igorek © (28.09.05 16:34) [123]
да, матдоказа-ва нет, но найденный алгоритм даёт теже рез-ты что и в ответе к задаче, а мы предпологаем что в ответе оптимальный алгоритм

← →
stud © (2005-09-28 17:02) [126]

> А требование в "худшем случае" - это когда невозможно
> придумать пример, когда алгоритм не сработает по
> минимуму.

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

← →
default © (2005-09-28 17:04) [127]

palva © (28.09.05 11:10) [111]
разобрались?

← →
default © (2005-09-28 17:06) [128]

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

← →
stud © (2005-09-28 17:53) [129]

>palva © (28.09.05 11:10) [111]
> разобрались?

разобрались именно для ЧАСТНОГО случая, но не для общего. решение для 3(4) приборов не применимо для большего количества

← →
default © (2005-09-28 17:56) [130]

stud © (28.09.05 17:53) [129]
[44] совсем не понятно?

← →
umbra © (2005-09-28 18:03) [131]

> default ©

44 понятно, но сомненительно, что этот способ дает минимальное количество измерений в худшем случае :))

← →
default © (2005-09-28 18:05) [132]

umbra © (28.09.05 18:03) [131]
не знаю почему сомнительно для Вас, но правда что взглянув на этот метод на ум в смысле минимальности ничего не приходит

← →
default © (2005-09-28 18:09) [133]

umbra © (28.09.05 18:03) [131]
см [125]
не будем верить ответу? конечно, хотелось бы доказать минимальность, но вероятно это за пределами наших сил:)

← →
umbra © (2005-09-28 18:16) [134]

> default ©

А откуда вообще эта задача?

← →
default © (2005-09-28 18:22) [135]

umbra © (28.09.05 18:16) [134]
MBo где-то нашёл её, ответ был, а достойного объяснения нет(это я с его слов говорю)
ответ был, как я понял, в форме формулы только
но как формула SergP начала давать такие же числа стало понятно что этот тот алгоритм какой спрашивался

← →
palva © (2005-09-28 18:22) [136]

default © (28.09.05 17:04) [127]
> разобрались?
Да теперь понятно.

← →
stud © (2005-09-28 18:44) [137]

вот случай для 5 приборов
меряем 1-2, 3-4
1-2 результат ИСПРАВЕН (значит либо неисправен 1 или неисправны оба либо оба исправны)
3-4 результат ИСПРАВЕН (неисправен 3 или неисправны оба либо оба исправны)
значит мы не можем сказать где находятся неисправные (либо в первой паре либо во второй, либо это 5 прибор)
что мы меряем дальше?

← →
default © (2005-09-28 18:53) [138]

stud © (28.09.05 18:44) [137]
дальше, согласно алгоритму, мы выкидываем приборы 1 и 3 и начинаем всё сначала

← →
stud © (2005-09-28 18:54) [139]

т.е. неисправными могут быть
1. 1,3
2. 1,2
3. 3,4
4. 1,5
5. 3,5
и как за оставшееся одно измерение найти исправный?
т.е. мы абсолютно ничего нашли, у нас после этих измерений ЛЮБОЙ прибор может быть неисправным, но какой?

← →
default © (2005-09-28 18:59) [140]

stud © (28.09.05 18:54) [139]
вы можете здесь уже не замарачиваться о том с какими комбинациями мы пришли к задаче меньше размерности чем исходная
а просто решать задачу меньшей размерности как будто первого шага Вы и не делали
"F(2*K) = F(2*K-1) = K-1+F(K)"

← →
default © (2005-09-28 19:03) [141]

stud © (28.09.05 18:54) [139]
изначально было пять приборов, два из которых неисправны
то есть изначально был инвариант: хороших больше чем плохих
далее мы пришли к 3 приборам после 2 сравнений, но инвариант сохранён: хороших больше чем плохих, стало быть плохой только один прибор, он вычисляется за одно сравнение и того приходим 2+1=3 сравнениям

← →
default © (2005-09-28 19:06) [142]

"он вычисляется за одно сравнение " всмысле вычисляется хороший прибор

← →
stud © (2005-09-28 19:18) [143]

все понятно )))) все ясно

← →
qt (2005-09-29 02:54) [144]

(n-1)*n
это в худшем случае
то есть подрубаем каждый прибор ко всем остальным по очереди и смотрим результат
если в результате теста >50 процентов других приборов говорят что прибор исправен то он исправен.

← →
stud © (2005-09-29 09:43) [145]

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

вот это уже ближе к теме. сделать вывод об исправности или неисправности прибора можно только на основании статистических данных
и F(3)=1 не будет))))) если очень интересно могу объяснить детально, хотя ответ почему содержится в

> umbra © (27.09.05 16:16) [83]

← →
Igorek © (2005-09-29 11:02) [146]

> F(3)=1 не будет))))) если очень интересно могу объяснить
> детально

очень интересно

← →
default © (2005-09-29 11:38) [147]

из [65]
меряем один прибор всем остальными
допустим что мы меряем хороший прибор, стало быть хороших измерений >= чем плохих измерений
допустим что мы меряем плохой прибор, стало быть хороших измерений< чем плохих измерений
пересечейни нет, значит достаточно n-1 измерения
F(3)=3-1=2<>1

← →
umbra © (2005-09-29 11:59) [148]

> stud ©

> F(3)=1 не будет

Количесиво измерений зависит от способа. Способ из 44 действительно дает F(3)=1 и к тому же поддается математическому выражению. Способ из 65 дает F(3)=2 и, как ни жаль, по крайней мере я, формализовать его не смог

хотя мне очень сильно кажется, что количество измерений в 65 с возрастанием количества приборов растет медленней, чем в 44.

> очень интересно

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

ой туплю...если мы получили плохой прибор в [147] то выкидываем его и решаем тем же методом для остальных приборов
" Способ из 65 дает F(3)=2 и, как ни жаль, по крайней мере я, формализовать его не смог"
так что совершенно просто он формализуется

> абсолютно ничего волшебного тут нет...

нет конечно. но согласно предложенного алгоритма объективной картины мы получить НЕ МОЖЕМ.
т.е. утверждение что достаточно одного измерения извините не убеждает! т.к. мы не получаем ОДНОЗНАЧНОГО ответа на поставленный вопрос - смысл такого алгоритма?

stud © (29.09.05 12:48) [155]
рассмотрим любое число приборов большее двух где есть 1 плохой прибор
в таких наборах можно за одно сравнение вычислить хороший прибор
согласны с этим?

> на Ваших же идеях я его придумал минуты за 3
> Вы перемудрили в [65]
>

Я мудрил потому, что в условии написано
> Проверка довольно дорогая, поэтому их количество надо минимизировать.
>

И в 65, если измеряемый прибор неисправен, убирается не 1 прибор, а 1+(все приборы, давшие ответ "исправен").

> stud © (29.09.05 12:07) [151]

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

> не понял, то есть Вы не верите что F(3)=1

верю))) но толку? мы взяли прибор А получили например результат (57) что он исправен, взяли прибор Б примнили (57) оказалось что А неисправен.
логика рассуждения вполне понятна, но если я правивльно понимаю, алгоритм должен однозначно обеспечивать рещение, независимо от того с какого прибора мы начинаем измерения. в противном случае применив один и тот же алгоритм мы с вами легко можем получить абсолютно противоположные результаты и самое смешное что каждый будет прав))) и куда такой алгоритм можно применить?
еще раз повторю - предложеный вариант логичен, НО НЕ ОБЕСПЕЧИВАЕТ ОДНОЗНАЧНОГО РЕШЕНИЯ
если вы не согласны, то объясните как один прибор может быть и исправным и неисправным в зависимости от того кто его проверял?

← →
SergP. (2005-09-29 13:24) [160]

> stud © (29.09.05 13:09) [159]
>
> > не понял, то есть Вы не верите что F(3)=1
>
> верю))) но толку? мы взяли прибор А получили например результат
> (57) что он исправен, взяли прибор Б примнили (57) оказалось
> что А неисправен.
> логика рассуждения вполне понятна, но если я правивльно
> понимаю, алгоритм должен однозначно обеспечивать рещение,
> независимо от того с какого прибора мы начинаем измерения.
> в противном случае применив один и тот же алгоритм мы с
> вами легко можем получить абсолютно противоположные результаты
> и самое смешное что каждый будет прав))) и куда такой алгоритм
> можно применить?
> еще раз повторю - предложеный вариант логичен, НО НЕ ОБЕСПЕЧИВАЕТ
> ОДНОЗНАЧНОГО РЕШЕНИЯ
> если вы не согласны, то объясните как один прибор может
> быть и исправным и неисправным в зависимости от того кто
> его проверял?

Я не совсем понимаю что в 57 Вам не ясно...

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

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