|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Типа log(x+1) ? ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 18:12 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
BarloneА вы попробуйте доказать, что за 7 невозможно :) для 15 ? Первая попытка, схематично. 1) для измерения разбиваем на 2 мн-ва 2) разбиение на большее кол-во не уменьшит резалт (доказывать отдельно). (А не потому, что никто не сумел быстрее ..) 1) Матем-ской индукцией по меньшему слагаемому Имеем решение за 8. Например (8+7)--(4+4,4+3)--(2+2,2+2)--(1+1,1+1) Уменьшение 7 до 6,5,...4 (т.е. до (10+5)) не уменьшает резальт. А переход от 8 к 9, наоборот увеличит. 2) ждём-с ... (просто слагаемые будут мельче, и добавляется новый ручеёк для проверки) А насчёт помехоустойчивого кодирования (Хэмминга) ... боюсь, что сам код не оптимальный для С(N,2) вариантов, что не доказывает саму минимальность решения. И, блин, кто сюда принесёт типовые раскладки для Хэмминга с 2мя .... вот непонятно, обнаружениями или исправленями (ставлю на исправления). ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 18:14 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
maytonТипа log(x+1) ? Нет. Когда N = 2 к формула вроде как точная. Поправка должна учитывать некратность аргумента. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 18:43 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
exp98, первое моё наивное решение содержало матрицу шаров типа 3х5 где я должен бы прикладывать измеритель к столбцам и строкам. Неоптимально. Но очень похоже на выявление ошибок четности в старых системах связи. Матричное кодирование типа. Отсюда пошла и мысль о Хемминге как о более математически верном пути. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 18:53 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
mayton, а я оч давно слышал вскользь, что колич-во измерений в похожих логических задачах можно дать ответ, построив оптимальный код (для хода измерений). Но как их строить и к чему применять, хз. Даже в этой задаче не могу решить, по какому принципу разбивать мн-во. Например (8+1) ответ 5, (7+2)=6, (5+4)=7 ... С другой стороны, есть задачи типа о выявлении лжеца, там больше самокоррекция напрашивается. Во всяк было что-то похожее на форуме в 12-13 г. Но загвоздка в том, какой код и с какими параметрами. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 19:14 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Я подобные задачи обычно решаю отходя два шага назад. Тоесть чтобы глянуть как задача выглядит не на 15 шарах а на 1500 например. И тогда будут более очевидны. Или более "гладки". И "непрерывны" наши оценки. Ситуация с 1 шаром - тривиальна. Дихотомия. Два шара - сбивают с толку. Они дают некий эффект который ломает дихтомию. Но не настолько чтоб сломать формулу. Скорее просто вносит путаницу со старта для человека который решает шары на малых значениях N. По повод скриншота который я привел для 14 шаров. Я не удержался и заглянул вконец. Пишут что 7 шагов достаточно. Это я не ради троллинга. А просто пишу видя что интерес угас. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 19:30 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
ИМХО mayton напутал и заставил искать подвох там где его нет, т.е. вместо нездорового числа 14 21824356 , которое решается за 7 измерений 21824574 вопреки общим оценкам, назвал число 15 где все банально и прозрачно. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 19:30 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Ну... прошу прощения. Эту задачу мне задал лет 15 назад один математик. И в той постановке звучало 15 шаров. Вообще наверное суть не в этом. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 19:45 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Я свожу к случаям 2-х мн-в и в каждом по 1метке. Каждая метка тогда стандартно находится делением/2, или даже можно сразу формулой. Поэтому я думаю, что общая формула д.б. 2-х ступенчатой, т.е. с 2-мя логарифмами. Но разбиение пополам есть редко, а бОльшее слагаемое можно менять в больших пределах [2^k; 2*2^k), чем меньшее слагаемое. Тогда при подборе слагаемых результат для меньшего слаг-го меняется чаще, т.к. степень для него м.б. меньше. Поэтому мне видится 2-х ступенчатость общей суммы. Это так, общие соображения. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 19:58 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
exp98, проблема в том что формулы заточены на поиск одного [шара], а на два нет классических алгоритмов. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 20:29 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
maytonНу... прошу прощения. Эту задачу мне задал лет 15 назад один математик. И в той постановке звучало 15 шаров. Вообще наверное суть не в этом. Может в этом есть верх троллинга над студентами: найди подвох там где его нет. Сложно признать что подвоха нет если ты участник олимпиад и привык искать (и находить) подвох. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 20:34 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Кажется, найти 2 из 15 таки можно за 7 измерений. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 20:40 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
BarloneКажется, найти 2 из 15 таки можно за 7 измерений. Можно за одно 21823737 , но не всегда. Решение огласи ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 20:43 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Dima TBarloneКажется, найти 2 из 15 таки можно за 7 измерений. Можно за одно 21823737 , но не всегда. Решение огласиНачинается с проверки первых пяти шаров. Если там пусто, то из оставшихся 10 можно найти два за 6 проверок. Если не пусто, меряем например 1,2,15. Каждый следующий шаг зависит от предшествующих результатов. Получается много веток. Я просто выписал все возможные варианты пар, и каждым измерением делил их на две равные части. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 20:57 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Челлендж: написать генератор решений. Ну то есть генератор алгоритмов в виде псевдокода или даже программы, выполняющей нужную последовательность проверок. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 21:22 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
BarloneЧеллендж: написать генератор решений. Ну то есть генератор алгоритмов в виде псевдокода или даже программы, выполняющей нужную последовательность проверок. полная проверка алгоритма 21824574 Код: 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2019, 22:39 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Поиск 2 из 15 за 7 проверок. Как уже говорил, первая проверка все 1-5. Если пусто, то вроде бы все согласны, что из оставшихся 10 можно найти 2 за 6 проверок. Эту часть расписывать не буду. У нас осталось 60 вариантов пар, в которых присутствует хотя бы один из шаров 1-5. Теперь проверяем 1,2,15. При положительном результате проверяем 1 и 6, иначе 3, 6 и 7. Получилось 4 ветки, в каждую попадают по 15 вариантов пар. В каждой за 4 проверки можно выбрать одну правильную. Сейчас все распишу. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2019, 06:34 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Первый случай. check(1,2,15)=true, check(1,6)=true Проверяем 8-15 Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9.
При отрицательном результате (справа) проверяем 3,4,5,7. Сверху + снизу -. Дальше вроде понятно. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2019, 06:35 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Второй случай. check(1,2,15)=true, check(1,6)=false Проверяем 3,4,5,7,8,9,10,11 Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9.
При отрицательном результате (справа) проверяем 15. Сверху + снизу -. Дальше понятно. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2019, 06:36 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Третий случай. check(1,2,15)=false, check(3,6,7)=true Проверяем 7-14 Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9.
При отрицательном результате (справа) проверяем 3. Сверху + снизу -. Дальше понятно. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2019, 06:36 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Последний случай. check(1,2,15)=false, check(3,6,7)=false Проверяем 4 Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
При отрицательном результате (справа) всегда 5 + один из ... Модератор: Поправил 21826905 ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2019, 06:37 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Ну вот, в самом конце опечатка. check(4) должно быть вместо check(7,8,9,10,11,12,13,14) ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2019, 06:39 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
BarloneВторой случай. check(1,2,15)=true, check(1,6)=false Проверяем 3,4,5,7,8,9,10,11 Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9.
Еще возможно 15 и один из 3,4,5. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2019, 09:00 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
21826945 Если первый один из 3,4,5, то нужен 8-й замер чтобы понять где второй: 2 или 15. В 7 замеров не уложился. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2019, 09:12 |
|
Пятничный треугольник
|
|||
---|---|---|---|
#18+
Dima TBarloneВторой случай. check(1,2,15)=true, check(1,6)=false Проверяем 3,4,5,7,8,9,10,11 Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9.
Еще возможно 15 и один из 3,4,5. Упс, косяк, исправляем... check на самом другой, запутался своих в пометках. Проверяем 12,13,14,15 Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9.
... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2019, 09:28 |
|
|
start [/forum/topic.php?fid=16&msg=39783227&tid=1339982]: |
0ms |
get settings: |
10ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
117ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
57ms |
get tp. blocked users: |
1ms |
others: | 252ms |
total: | 473ms |
0 / 0 |