|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Перечитал 21827271 и 21827278 На время праздничное помутнением покинуло мозг, и вновь я осознал и множества, и дихотомию ) Попробую сказать то же самое своими словами. Для анализа алгоритма достаточно ограничиться рассмотрением пар чисел. Нас интересует только пара-решение, ее мы ищем. Все другие пары, даже если в них входит одно из звенящих чисел, нам безразличны. Это важный момент, и он может сбивать с толку: в процессе решения мы часто ищем каждое число из пары-решения по-отдельности, но для анализа это не важно. Изначально пара-решение входит во все множество пар. В процессе решения мы сокращаем это включающее множество. Когда размер включающего множества сократится до 1 - мы нашли решение. С этой точки зрения неважно, какие проверки мы делаем, важно лишь, как при этих проверках сокращается включающее множество. При любой проверке мы разбиваем множество пар на 2 части: включающую и не влючающую. Мы всегда предполагаем худшее, а именно, что включающее множество - большее из полученных. Очевидно, что если в х шагах от выдачи результата размер включающего множества превышает 2 х , то решение найти не удастся. В силу дискретности задачи граница лежит ниже. Удобно сначала построить последовательности проверок для меньших количеств шаров. Эти построения можно использовать, если окажется, что это множество ни разу не проверялось и оба шара лежат там. ... |
|||
:
Нравится:
Не нравится:
|
|||
08.03.2019, 11:28 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov, а можно интерпретировать это для бывших танкистов. Из такого объяснения понял только 1-й и последний абзацы. П.С. В связи с 1-м абзацем поздравляю всех наших жён с наступившей, бр-р-р, весной. В связи с отсутствием их интереса к топику, предлагаю им пожелать скорректировать вектор интересов от "kinder, cookery, show" в средней или последней части. ... |
|||
:
Нравится:
Не нравится:
|
|||
08.03.2019, 16:51 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Может для общего языка ссылаться на случаи согласно типовой нумерации. типа такого: Код: xml 1. 2. 3. 4. 5. 6. 7. 8. 9.
Вкладываю для 15. ... |
|||
:
Нравится:
Не нравится:
|
|||
08.03.2019, 17:01 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Допустим оба тухлых яйца расположились как "....10001" (случай 7), но мы пока этого не знаем. Что дальше?.. Что за пары чисел, что и когда разбивает 105 случаев на включающую и не включающую части ?... Хочется услышать как-нибудь поструктурнее. ... |
|||
:
Нравится:
Не нравится:
|
|||
08.03.2019, 17:13 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
exp98Aleksandr Sharahov, а можно интерпретировать это для бывших танкистов. Из такого объяснения понял только 1-й и последний абзацы. П.С. В связи с 1-м абзацем поздравляю всех наших жён с наступившей, бр-р-р, весной. В связи с отсутствием их интереса к топику, предлагаю им пожелать скорректировать вектор интересов от "kinder, cookery, show" в средней или последней части. Вообще-то это как раз и была интерпретация разъяснений Barlone ) Если интерпретировать интерпетацию она вырождается в нечто в роде такого: Рассмотрим множество всевозможных пар шаров мощностью C(2,N). Нас интерересует только один элемент этого множества - пара звенящих шаров. Каждый тест, возвращая булевский результат, тем самым делит множество на 2 части. И нет никакого способа найти нашу пару быстрее log(C(2,N)) , т.к. мы будем вредить, перенумеровывая шары перед каждым тестом, но не нарушая результатов предыдущих тестов. ... |
|||
:
Нравится:
Не нравится:
|
|||
08.03.2019, 17:50 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
exp98Допустим оба тухлых яйца расположились как "....10001" (случай 7), но мы пока этого не знаем. Что дальше?.. Что за пары чисел, что и когда разбивает 105 случаев на включающую и не включающую части ?... Хочется услышать как-нибудь поструктурнее. В данном случае мы пытаемся только оценить количество шагов, а не построить алгоритм. Поэтому анализ неконструктивный. ... |
|||
:
Нравится:
Не нравится:
|
|||
08.03.2019, 18:11 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov, спасибо за разъяснения. Поначалу я так же думал, что для кодирования 128 номеров необходимо 7 бит, потом у меня всё смешалось и таким остаётся. Смущает, что С(12)=11*12/2=66 между (64; 128), и у меня для 12 раз за разом ответ 7. Но может я путаю, осталось убеждение, что все говорят для 12 ответ 6 или нет? ох, как неохота выискивать на страницах ... Но с другой стороны, 7 бит - это когда номера произвольные. В задаче всё же номера имеют внутреннюю структуру ( 10101 - не м.б. и т.п.), и не все случаи равновероятны. Например при проверке кучек 6+1+1 не может получиться 002 или 111. В общем какие-то ассоциации с частотным кодированием по Хэммингу. Может здесь эти ассоциации срабатывают? Лично я уже ни в чём не уверен. ... |
|||
:
Нравится:
Не нравится:
|
|||
08.03.2019, 18:19 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
exp98Aleksandr Sharahov, спасибо за разъяснения. Поначалу я так же думал, что для кодирования 128 номеров необходимо 7 бит, потом у меня всё смешалось и таким остаётся. Смущает, что С(12)=11*12/2=66 между (64; 128), и у меня для 12 раз за разом ответ 7. Но может я путаю, осталось убеждение, что все говорят для 12 ответ 6 или нет? ох, как неохота выискивать на страницах ... Но с другой стороны, 7 бит - это когда номера произвольные. В задаче всё же номера имеют внутреннюю структуру ( 10101 - не м.б. и т.п.), и не все случаи равновероятны. Например при проверке кучек 6+1+1 не может получиться 002 или 111. В общем какие-то ассоциации с частотным кодированием по Хэммингу. Может здесь эти ассоциации срабатывают? Лично я уже ни в чём не уверен. Для 12 ответ 7, см. 21827271 . Да, у нас не все случаи равновероятны. У нас с даже хуже. Мы всегда предполагаем, что очередной тест дает результат, который требует максимального количества дальнейших проверок. З.Ы. В этой задаче такие ассоциации мне только мешают ) ... |
|||
:
Нравится:
Не нравится:
|
|||
08.03.2019, 20:01 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Полная проверка алгоритма Barlone (2 из 15) на Delphi без формочек: Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96.
... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 00:48 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
По похожему принципу решаются задачи на взвешивания типа "найти две фальшивых монеты из 13", только делить надо на 3 части. (известно что фальшивые монеты одинакового веса и тяжелее настоящих, у нас есть рычажные весы без гирь...) ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 06:42 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Barlone, и так же тухлые яйца,помидоры и т.п., только их не взвешивают, а вонь проверяют)) Э-э, вопрос был к дельфам: а) где ж её взять или хотя бы интерпретатор; б) недопонял это Код: plaintext
Это повторная проверка шаров 1 и 2? для чего? ведь перед этим Код: plaintext
Ведь судя по самой последней проверке Код: plaintext 1. 2. 3. 4.
... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 14:17 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
exp98Barlone, и так же тухлые яйца,помидоры и т.п., только их не взвешивают, а вонь проверяют)) Э-э, вопрос был к дельфам: а) где ж её взять или хотя бы интерпретатор; б) недопонял это Код: plaintext
Это повторная проверка шаров 1 и 2? для чего? ведь перед этим Код: plaintext
Ведь судя по самой последней проверке Код: plaintext 1. 2. 3. 4.
a) скачать стартовую версию бесплатно у производителя б) IsWhite('12345', '37', calls) проверяет светимость группы шаров 12345, если по условию дано, что светятся шары 37, т.е. вхождение одного из шаров 3 или 7 в группу 12345. При этом инкрементируется счетчик проверок calls Да эта проверка повторно затрагивает шары 1 и 2, таков алгоритм. IsWhite() проверяет наличие светимости ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 14:45 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
интересно, что тот же алгоритм с очевидными изменениями находит 2 шара из 20 за 8 проверок, а вот что делать дальше неясно. ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 15:26 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Так получилось, что сам только что заглянул, поэтому спрашиваю. Непонятна цель повторной проверки. Скорее всего просто так родилось, ну и оставили. Умозрительно кажется, что Код: plaintext
... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 15:35 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Aleksandr Sharahovдальше неясно. Дальше переходить на полный бэктрекинг и генерацию подмножеств 2^21 ... Вообще, стоит покопаться в работах по обнаружению ошибок. ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 15:40 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
exp98Так получилось, что сам только что заглянул, поэтому спрашиваю. Непонятна цель повторной проверки. Скорее всего просто так родилось, ну и оставили. Умозрительно кажется, что Код: plaintext
Нет, нельзя. Смысл изменится. Там каждая циферка играет свою роль. ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 15:41 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Ни фига не понимаю почему. Ведь если '12345' не пахнут, почему '12f' могут отличаться от 'f'? Ведь первые 2 ифа работают по этой логике. ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 15:49 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
У меня сведения старые, по автоматическому синтезу алгоритмов можно ещё почитать. У нас давно ещё направление развивал Лупанов ОБ., ну и другие менее тогда известные. ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 15:59 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
exp98Ни фига не понимаю почему. Ведь если '12345' не пахнут, почему '12f' могут отличаться от 'f'? Ведь первые 2 ифа работают по этой логике.нет, вторая проверка в 'true' ветке. Среди 12345 есть меченый, но это может быть и не 12. ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 16:09 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
exp98Ни фига не понимаю почему. Ведь если '12345' не пахнут, почему '12f' могут отличаться от 'f'? Ведь первые 2 ифа работают по этой логике. тут надо узнать как можно больше про пару 12, а f подмешиваем, чтобы использовать знание о нем ниже логика такая: если 12f не пахнут, то 12 не пахнут, и значит пахнут 345 а в нижних else-ветках мы уже знаем, что и f не пахнет ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 16:10 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Хорошо, вам лучше знать, IsWhite() == тру, при наличии метки IsWhite() == фолс, при отсутствии метки. Раньше я думал что IsWhite() действует наоборот. Тогда "все сходится, ребёночек не наш"(с). Спасибо за разъяснения. ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 20:40 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
exp98У меня сведения старые, по автоматическому синтезу алгоритмов ошибся, вроде д.б. по автоматическому синтезу логических схем . ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 20:43 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
exp98Э-э, вопрос был к дельфам: а) где ж её взять или хотя бы интерпретатор; тынц ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 22:02 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Aleksandr Sharahovинтересно, что тот же алгоритм с очевидными изменениями находит 2 шара из 20 за 8 проверок, а вот что делать дальше неясно.и 2 из 23 за 8 можно, должен быть масштабируемый алгоритм Barlone прав, число возможных расстановок C(k,N) а значит минимально достаточно log2(C(k,N)) бит что бы описать любой из вариантов расстановки ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2019, 22:05 |
|
|
start [/forum/topic.php?fid=16&msg=39783903&tid=1339982]: |
0ms |
get settings: |
10ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
141ms |
get topic data: |
10ms |
get forum data: |
3ms |
get page messages: |
65ms |
get tp. blocked users: |
1ms |
others: | 13ms |
total: | 264ms |
0 / 0 |