Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2005.10.23;
Скачать: CL | DM;

Вниз

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

 
Igorek ©   (2005-09-23 14:59) [0]

Я так понял нерешена и интересна кое-кому. По крайней мере мне интересна.
Позволю себе открыть ветку. Итак:

Есть N неких устройств.
Часть из них исправна, часть сломана. Известно, что исправных больше, чем сломаных.
Одним прибором можно проверить другой, результат проверки - исправен проверяемый прибор или нет.
Понятно, что сломанный прибор может выдать что угодно, и доверия ему нет. Исправный же прибор всегда даёт правильный ответ.
Проверка довольно дорогая, поэтому их количество надо минимизировать.
Цель - найти хотя бы один исправный прибор.
Какое минимальное количество проверок придётся сделать в худшем случае?


 
jack128 ©   (2005-09-23 15:05) [1]

Igorek ©   (23.09.05 14:59)
Какое минимальное количество проверок придётся сделать в худшем случае?

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


 
Igorek ©   (2005-09-23 15:09) [2]

дополнения из
http://delphimaster.net/view/14-1126841752/
(откуда оно там не знаю)

дополнения из обсуждения:
-----------------------
-Интересно. Если я проверю одним прибором другой, и получу отрицательный ответ, то оба эти прибора можно отложить в сторонку.
-Вы на правильном пути.
---------------
Подсказка
я не проверяю один и тот же прибор больше одного раза
------------------------------------------------------------
для N=8 достаточно 4-х проверок.
Для 10-ти уже нужно 7 проверок
-----------------------------------


 
jack128 ©   (2005-09-23 15:13) [3]

а, блин. что то я не понял сначала, что мы сами тестеры на исправность и проверяем..


 
Igorek ©   (2005-09-23 15:16) [4]


> Бесконечно большое

И правда..


 
default ©   (2005-09-23 15:23) [5]

подожди! ёлки я уже не первый день решаю и вот вчера похоже нащупал решение вот только увидеть систему в действиях нужно и доказать


 
default ©   (2005-09-23 15:25) [6]

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


 
default ©   (2005-09-23 15:27) [7]

есть алгоритм дающий как надо F(6)=3; F(8)=4; F(10)=7
вот только кк говорил нужно всё это обощить что похоже не так просто
теормему формулировать и доказывать видимо придётся:)


 
Igorek ©   (2005-09-23 15:35) [8]

> Igorek ©   (23.09.05 15:16) [4]
Неправда.. :)

> default ©   (23.09.05 15:23) [5]

Имхо можно рассмотреть матрицу проверок. Раскрашивать приборы в белый/черный/серый. Использовать> Известно, что исправных больше, чем сломаных.


 
SergP.   (2005-09-23 15:41) [9]


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


Если неисправный прибор всегда выдает правильный ответ, то он на самом деле исправный... :-)


 
default ©   (2005-09-23 15:42) [10]

Igorek ©   (23.09.05 15:35) [8]
давайте давайте ;)
ну что меня будем ждать или коллективный разум подключать?
я, честно говоря, сомневаюсь что кто-то быстро найдёт решение, но всё-таки не очень дорешивать когда тебя могут обогнать:)


 
default ©   (2005-09-23 15:44) [11]

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


 
Igorek ©   (2005-09-23 15:56) [12]


> default ©   (23.09.05 15:42) [10]

На выходные посижу...


 
stud ©   (2005-09-23 16:21) [13]

вот мысль, так как неизвестно на сколько больше исправных приборов, но известно что их точно больше, то исправный гарантированно найдется за N/2-1 итераций


 
stud ©   (2005-09-23 16:29) [14]

т.е. максимальное количество неисправных приборов
n/2-1 и в худшем случае нам придется их все проверить, но если нам сразу попались подряд все нисправные приборы - значит те что остались ВСЕ исправные и проверять их нужды нет.
т.е. для 10 приборов полчается необходимо провести
10/2-1=4 проверки т.к. кол-во неисправных меньше то их может быть не более 4


 
MBo ©   (2005-09-23 16:46) [15]

>default ©   (23.09.05 15:27) [7]
>есть алгоритм дающий как надо F(6)=3; F(8)=4; F(10)=7
Еще для пары чисел (числа немного побольше) приведи F по твоему алгоритму.


 
stud ©   (2005-09-23 17:02) [16]


> Понятно, что сломанный прибор может выдать что угодно,
> и доверия ему нет. Исправный же прибор всегда даёт
> правильный ответ

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


 
default ©   (2005-09-23 17:14) [17]

MBo ©   (23.09.05 16:46) [15]
пока нет алгоритма в истинном смысле этого слова, но есть дорога которая я уверен на 99% истинна, дорога весьма неразмытая, вскоре думаю я выложу истинный алгоритм, пришлю Вам на почту или ветку создам
stud ©   (23.09.05 17:02) [16]
не зацикливайтесь на этих "подсказках" ... они уж слишком далёкие


 
stud ©   (2005-09-23 17:36) [18]


> не зацикливайтесь на этих "подсказках"

какие подсказки? сие влияет на алгоритм


 
default ©   (2005-09-23 17:38) [19]

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


 
SergP.   (2005-09-23 17:53) [20]


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


ИМХО то И/ИЛИ другое...


 
stud ©   (2005-09-23 18:08) [21]

в таком случае для того чтобы убедиться что один прибор точно не исправен (если он постоянно показывает ДА) мы должны его проверить n/2+1 раз т.к. это возможное (минимальное!) количество исправных приборов. если все неисправные приборы показываеют ДА по такую опрецию нужно проделать N/2-1 (максимальное количество неисправных приборов) (результат деления округляется в большую сторону)
тогда наихудший вариант (n/2-1)*(n/2+1)


 
default ©   (2005-09-23 18:29) [22]

stud ©   (23.09.05 18:08) [21]
нужен алгоритм O(n), то есть алгоритм число шагов которого в худшем случае в зависимости от размерности задачи растёт не быстрее чем линейная функция(ну знаете определение О большого...)


 
palva ©   (2005-09-23 19:15) [23]

SergP.   (23.09.05 15:41) [9]

> Если неисправный прибор всегда выдает правильный ответ, то он на самом деле исправный... :-)

Это почему? Исправный прибор это тот, который будучи проверен исправным прибором даст положительный результат. Разве не так?


 
Igorek ©   (2005-09-23 19:38) [24]


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

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


 
palva ©   (2005-09-23 19:44) [25]

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

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


 
palva ©   (2005-09-23 19:47) [26]

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


 
palva ©   (2005-09-23 19:51) [27]

> это когда неисправный прибор один и именно его мы измеряли на последнем шаге.

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


 
palva ©   (2005-09-23 19:57) [28]

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


 
palva ©   (2005-09-23 20:09) [29]

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


 
SergP.   (2005-09-23 20:19) [30]


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


Да... Я что-то не подумал об этом...

У меня есть небольшие сомнения в том правильно ли я понял условие задачи...

Вобщем если isprav(i) - это исправность i-го прибора, то результат проверки i-тым прибором j-го это:


function proverka(i,j:integer):boolean;
begin
  if isprav(i)
       then result:=isprav(j)
       else result:=neizvestnaja_funciya(i,j);
end;


или


function proverka(i,j:integer):boolean;
begin
  if isprav(i)
       then result:=isprav(j)
       else result:=neizvestnaja_funciya(i);
end;


????


 
SergP.   (2005-09-23 20:19) [31]


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


Да... Я что-то не подумал об этом...

У меня есть небольшие сомнения в том правильно ли я понял условие задачи...

Вобщем если isprav(i) - это исправность i-го прибора, то результат проверки i-тым прибором j-го это:


function proverka(i,j:integer):boolean;
begin
  if isprav(i)
       then result:=isprav(j)
       else result:=neizvestnaja_funciya(i,j);
end;


или


function proverka(i,j:integer):boolean;
begin
  if isprav(i)
       then result:=isprav(j)
       else result:=neizvestnaja_funciya(i);
end;


????


 
palva ©   (2005-09-23 20:19) [32]

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


 
palva ©   (2005-09-23 20:23) [33]

SergP.   (23.09.05 20:19) [31]

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


 
default ©   (2005-09-23 20:50) [34]

давайте, договоримся, до понедельника решение не выкладывать если вдруг у кого оно созреет к этому сроку, дабы не сбивать интерес ищущим
"поскольку неисправный прибор при измерениях одного и того же прибора может давать разные результаты,"
неисправность постулируется как одинаковость ответа для любого прибора
см [19]


 
default ©   (2005-09-23 23:54) [35]

найден линейный алгоритм который даёт:
F(1)=0; F(2)=0;
F(3)=1; F(4)=1;
F(5)=3; F(6)=3;
F(7)=4; F(8)=4;
F(9)=6; F(10)=6;
F(11)=8; F(12)=8;
F(13)=10; F(14)=10;
и дальше идёт прирост на двойку
для F(10000)=9996, но в давней ветку про приборы тамошний алгоритм давал
F(10000)=9991; но тамошний даёт F(10)=7; а мой F(10)=6
стало быть оба сравниваемых алгоритма не оптимальны для всех размеров задач
найти оптимальный?! нужно найти теоретический минимум и к нему стремиться, но это уже без меня! просили линейный вот Вам линейный;)
если решаюшие задачу согласятся на то чтобы я сейчас показал этот алгоритм, то покажу сейчас иначе в понедельник как договаривался


 
palva ©   (2005-09-23 23:58) [36]

А линейный я уже дал в [29]. Там n + (n-3)/2 измерений. Или это не то?


 
palva ©   (2005-09-24 00:02) [37]

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

Это почему? Я такого не предполагал. A разве не может сломанный прибор показывать то ДА, то НЕТ при на одном и том же измеряемом приборе.


 
palva ©   (2005-09-24 00:13) [38]

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


 
default ©   (2005-09-24 00:16) [39]

palva ©   (24.09.05 00:02) [37]
тоже линейный, но слабоват
ибо мой всегда <n шагов, хотя тоже по всей видимости далёк от оптимального
"Это почему?"
ну мы на этом с MBo сошлись, может правы Вы, кто знает...
как известно тамошний алгоритм даёт F(6)=3; F(8)=4; F(10)= 7
попробуйте посмотреть можно ли вообще при Вашем предположении добиться такого результата(например, проверить это для самого маленького размера F(6)=3) и если нельзя то значит предположение всё-таки наше использовалось в тамошнем алгоритме что скорее всего так и есть
но как указывалось выше и тамошний при нашем предположении не оптимален...


 
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]


 
palva ©   (2005-09-26 19:58) [69]

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


 
palva ©   (2005-09-26 20:01) [70]

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

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


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


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


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


 
palva ©   (2005-09-26 21:26) [72]

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


 
default ©   (2005-09-27 11:11) [73]

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


 
umbra ©   (2005-09-27 11:47) [74]


> [57]

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


 
palva ©   (2005-09-27 12:07) [75]

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

umbra ©   (27.09.05 11:47) [74]

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

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


 
stud ©   (2005-09-27 12:09) [76]

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

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

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

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




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

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


 
umbra ©   (2005-09-27 14:24) [77]


> stud


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



> palva


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


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

и я о том же.

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


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


 
palva ©   (2005-09-27 15:23) [78]

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

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

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


 
umbra ©   (2005-09-27 15:43) [79]

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


 
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.


 
umbra ©   (2005-09-28 10:24) [109]


> Verg


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


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


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


 
stud ©   (2005-09-28 11:08) [110]


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

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

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

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


 
palva ©   (2005-09-28 11:10) [111]

SergP.   (27.09.05 19:17) [105]

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

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

++--
++-

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

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

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

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


 
stud ©   (2005-09-28 11:17) [112]


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

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

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


 
palva ©   (2005-09-28 11:31) [113]

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


 
Verg ©   (2005-09-28 11:56) [114]


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


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

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


 
stud ©   (2005-09-28 12:03) [115]


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

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


 
Verg ©   (2005-09-28 12:12) [116]


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


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


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


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

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

:)))


 
umbra ©   (2005-09-28 12:37) [117]


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

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


 
umbra ©   (2005-09-28 12:41) [118]

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


 
palva ©   (2005-09-28 13:51) [119]

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

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


 
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 и, как ни жаль, по крайней мере я, формализовать его не смог


 
umbra ©   (2005-09-29 12:01) [149]

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


 
default ©   (2005-09-29 12:03) [150]

umbra ©   (29.09.05 12:01) [149]
см [147]
на Ваших же идеях я его придумал минуты за 3
Вы перемудрили в [65]


 
stud ©   (2005-09-29 12:07) [151]


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

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


 
default ©   (2005-09-29 12:08) [152]

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


 
default ©   (2005-09-29 12:16) [153]

umbra ©   (29.09.05 12:01) [149]
почему? в [65] в лудшем случае хватит n-1 измерения
а в [44] всегда F(n)<n


 
default ©   (2005-09-29 12:38) [154]

stud ©   (29.09.05 12:07) [151]
абсолютно ничего волшебного тут нет...


 
stud ©   (2005-09-29 12:48) [155]


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

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


 
default ©   (2005-09-29 12:54) [156]

stud ©   (29.09.05 12:48) [155]
не понял, то есть Вы не верите что F(3)=1? объяснения SergP не убеждают?([57])


 
default ©   (2005-09-29 12:58) [157]

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


 
umbra ©   (2005-09-29 13:04) [158]


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


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

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


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

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


 
stud ©   (2005-09-29 13:09) [159]


> не понял, то есть Вы не верите что 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, и проверяемый тогда не может быть неисправным


 
default ©   (2005-09-29 13:33) [161]

stud ©   (29.09.05 13:09) [159]
что-то мне кажется тут с алгоритмом не совсем понятно
пусть имеем набор из 6 приборов, один плохой
есть следующие варианты
ПХХХХХ 1
ХПХХХХ 2
ХХПХХХ 3
ХХХПХХ 4
ХХХХПХ 5
ХХХХХП 6
очевидно, что какой бы прибор не захотели мы проверить любым другим, то мы можем так переставить приборы что окажется что мы поверяем первым прибором второй, а вариации останутся вышевыписанными
так что алгоритм безразличен к тому какой прибор каким мы поверяем
итак, будем говорить что первым прибором мы проверяем второй
пусть получили Х; значит возможно следующие две комбинации первых двух приборов
ХХ
ПХ
то есть второй прибор хороший
(вариация 2 невозможна и вертикаль номер два слева состоит целиком их хороших приборов)
пусть получили П
возможные комбинации
ХП
ПХ
стало быть в первых двух приборах содержится плохой прибор и значит все остальные приборы хорошие
вот и всё
поэтому такого "мы взяли прибор А получили например результат (57) что он исправен, взяли прибор Б примнили (57) оказалось что А неисправен."
быть не может


 
default ©   (2005-09-29 13:45) [162]

umbra ©   (29.09.05 13:04) [158]
я уже понял, поспешил чуть...


 
umbra ©   (2005-09-29 14:09) [163]


> stud ©

Для способа из 44 F(3)=1. Но в 57 - ошибка. Если мы берем один (любой) прибор, меряем им другой и получаем ответ "исправен", то это значит, что второй наверняка исправен. Если же получаем "неисправен", то это значит, что наверняка исправен 3-й прибор (а не второй, как в 57)


 
stud ©   (2005-09-29 14:17) [164]


>Я не совсем понимаю что в 57 Вам не ясно...
>
> Но еще раз


> stud ©   (29.09.05 12:07) [151][Ответить]


 
default ©   (2005-09-29 14:40) [165]

stud ©   (29.09.05 14:17) [164]
банальная логика
1)Вы принимаете корректность алгоритма
2)принимаете что есть один плохой прибор
теперь если по опросу контор получилось что все три прибора хорошие
то исходя из 2) получаем противоречие с 1)(то есть выходит что как минимум одна контора пользуется неверным алгоритмом)  вывод: такой комбинации быть не может


 
stud ©   (2005-09-29 15:40) [166]


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

???????))))))))))
это как? тогда извините ваш алгоритм как минимум один раз неверный)) вывод: такой алгоритм неприменим)))))


 
default ©   (2005-09-29 15:45) [167]

stud ©   (29.09.05 15:40) [166]
Вы говорите: как такое может быть что три прибора могут быть хорошими
я говорю что такого быть не может если бы такое могло быть то это значило бы что какая-то контора ошиблась в выборе что означало бы некорректность алгоритма, ну а корректность, как я понял, признана была


 
stud ©   (2005-09-29 15:52) [168]


> Вы говорите: как такое может быть что три прибора
> могут быть хорошими

ну допустим это может быть

>  Известно, что исправных больше, чем сломаных

3 > 0 не противоречит условию задачи

> если бы такое могло быть то это значило бы что
> какая-то контора ошиблась в выборе что означало бы
> некорректность алгоритма

ну тогда скажите кто из 151 применил неверный алгоритм и в чем эта неверность заключается?
алгоритм - берем два ЛЮБЫХ прибора и снимаем показания и делаем вывод, или что-то еще?


 
default ©   (2005-09-29 15:57) [169]

stud ©   (29.09.05 15:52) [168]
речь шла когда один прибор плохой есть
но для общего случая никаких противоречий нет...
если добавить к алгоритму строку ХХХХХХ в [161] алгоритм не изменится нисколько
"алгоритм - берем два ЛЮБЫХ прибора и снимаем показания и делаем вывод, или что-то еще?" да
"ну тогда скажите кто из 151 применил неверный алгоритм и в чем эта неверность заключается?"
если будут пользоваться алгоритмом в [161] все дадут верный ответ, то есть укажут на хороший прибор


 
default ©   (2005-09-29 15:59) [170]

"алгоритм - берем два ЛЮБЫХ прибора и снимаем показания и делаем вывод, или что-то еще?" вернее нет, больше ничего не надо кроме 1 срав-я


 
stud ©   (2005-09-29 16:31) [171]


> вернее нет, больше ничего не надо кроме 1 срав-я

так ведь каждый делает только по одному сравнению))


 
default ©   (2005-09-29 16:34) [172]

stud ©   (29.09.05 16:31) [171]
Вы, похоже, прикалываетесь тут над нами


 
stud ©   (2005-09-29 16:37) [173]


> Вы, похоже, прикалываетесь тут над нами

простите, а сколько сравнений (которые провела каждая контора в отдельности) вы насчитали?


 
default ©   (2005-09-29 16:43) [174]

stud ©   (29.09.05 16:37) [173]
решите, пожалуйста, следующую очень простую задачу

ф-ия g определена на натуральных числах
g(x)=     x+1 если x нечётно
           x/2  если x чётно
доказать что при x>=2 g(x)=1 на некотором шаге n
(
x >=2; x - целое
while x <> 1 do
 if Odd(x) then Inc(x) else x := x div 2; )


 
oldman ©   (2005-09-29 16:57) [175]

Не минимум, но оптимум:

1) прибор  А меряем всеми.
2) Если максимум "исправен" - прибор один исправен, преходим к 5)
3) Если максимум "неисправен" - прибор А неисправен, берем прибор Б, возвращаемя к 1)
4) Если "исправен"="неисправен", переходим  к 1), оставив прибор А
5) проверяем все приборы найденным исправным

2-3 основаны на том, что исправных больше (из условия)
4 основано на том, что исправных может быть больше несправных на 1.

:)))


 
Igorek ©   (2005-09-29 17:01) [176]


> default ©   (29.09.05 16:34) [172]

Предлагаю другую задачу. Доказать ув. stud что F(3)=1. Как показала практика это далеко не такая простая задача.


 
stud ©   (2005-09-29 17:06) [177]

предлагаю
default ©
найти того - кто неправильно применил алгоритм в 151


 
default ©   (2005-09-29 17:10) [178]

stud ©   (29.09.05 17:06) [177]
Вы на тот свет согнать хотите?:)
как может кто-то ошибиться если он применяет правильный алгоритм
Вы сами себе этих контор на придумывали теперь расхлёбываете....:)


 
default ©   (2005-09-29 17:12) [179]

если кто-то неправильно применяет правильный алгоритм то фактичски он применяет неправильный алгоритм:)


 
stud ©   (2005-09-29 17:15) [180]


> если кто-то неправильно применяет правильный алгоритм
> то фактичски он применяет неправильный алгоритм

имя сестра!! имя! (с) :))


 
default ©   (2005-09-29 17:16) [181]

stud ©   (29.09.05 17:15) [180]
default:)


 
stud ©   (2005-09-29 17:57) [182]

вот и закончилась у меня инвентаризация)))
можно закрыть тему))


 
default ©   (2005-09-29 19:12) [183]

stud ©   (29.09.05 17:57) [182]
в чём инвентаризация состояла?


 
palva ©   (2005-09-29 20:52) [184]

> в чём инвентаризация состояла?
Навешивал инвентарные номера на исправные приборы.


 
default ©   (2005-09-29 21:02) [185]

palva ©   (29.09.05 20:52) [184]
ага после это задача перестала иметь смысл:)



Страницы: 1 2 3 4 5 вся ветка

Текущий архив: 2005.10.23;
Скачать: CL | DM;

Наверх




Память: 1.03 MB
Время: 0.048 c
3-1125922257
Starcom
2005-09-05 16:10
2005.10.23
Чтоб при вводе запроса небыло подвязки к регистру?


1-1128254250
Ivanov
2005-10-02 15:57
2005.10.23
добавление Item в TDXImageList


3-1126436644
alsov
2005-09-11 15:04
2005.10.23
Копирование данных из вьюхи в оракле в таблицу в Access


14-1127891653
__DATA__
2005-09-28 11:14
2005.10.23
Могут ли несколько приложений висеть на одном и том же порте?


14-1127804254
Empleado
2005-09-27 10:57
2005.10.23
Небольшие заметки. Бельгия.





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский