Главная страница
    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 измерения без предположения о детерминированности показаний неисправного прибора. Я исписал лист бумаги (типа полного перебора) и придумал алгоритм. Но этот алгоритм "безыдейный", его нельзя распространить на большее число приборов. Ну а полным перебором заниматься не интересно. Хотя если поставить вопрос о написании компьютерной программы, реализующей полный перебор, то может быть и можно повозиться.



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

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

Наверх




Память: 0.56 MB
Время: 0.101 c
14-1128204297
Ученик чародея
2005-10-02 02:04
2005.10.23
Как вы оцениваете баланс школьной программы?


3-1126155558
Ol
2005-09-08 08:59
2005.10.23
MSSQL+ADO+TQuery+TDBEdit


3-1126179298
SharkMan
2005-09-08 15:34
2005.10.23
Проблема со строками


14-1128316417
Ega23
2005-10-03 09:13
2005.10.23
С днем рождения! 2 октября


1-1128148095
heady
2005-10-01 10:28
2005.10.23
Скачать HTML-код странички в Memo





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
Английский Французский Немецкий Итальянский Португальский Русский Испанский