Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5] 6 7 8   вперед  Ctrl      все
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1160
в третьем варианте кажется тоже накосячил
7 мар 19, 09:33    [21826960]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13367
Barlone
Dima T
пропущено...

Еще возможно 15 и один из 3,4,5.

Упс, косяк, исправляем... check на самом другой, запутался своих в пометках.
Проверяем 12,13,14,15

Так 7 хватает
7 мар 19, 09:38    [21826965]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13367
Barlone
в третьем варианте кажется тоже накосячил

Давай правильный. Я до него еще не добрался.

PS Как ты это изобрел? У меня от проверки мозг закипает )))
7 мар 19, 09:40    [21826967]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1160
Barlone
Третий случай. check(1,2,15)=false, check(3,6,7)=true
Проверяем 7-14

check(7,8,9,10,11,12,13,14)
3,7 |
3,8 | (3,4) (3,5) (3,6)
3,9 |
3,10 |---check(3)---
3,11 |
3,12 | (4,6) (4,7)
3,13 | (5,6) (5,7)
3,14 |
При положительном результате (слева) всегда 3 + один из 7-14, который выберем за 3 шага делением пополам.
При отрицательном результате (справа) проверяем 3. Сверху + снизу -. Дальше понятно.

Это неправильно, на самом деле так: проверяем 4,5,6,7

check(4,5,6,7)
3,8 | (3,4) (3,5)
3,9 | (3,6) (3,7)
3,10 |
3,11 |---check(3)---
3,12 |
3,13 | (5,6) (5,7)
3,14 | (4,6) (4,7)
слева отрицательный результат, справа положительный
7 мар 19, 09:41    [21826968]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1160
Dima T
PS Как ты это изобрел? У меня от проверки мозг закипает )))
Так выписывал все возможные пары и подбирал проверки, делящие их пополам, дальше по рекурсии каждую половину. Иногда получается, что пополам никак не хочет делиться, и приходится вернуться назад и попробовать поделить по другому на более раннем шаге :)
7 мар 19, 09:45    [21826974]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1160
Barlone
Так выписывал все возможные пары и подбирал проверки, делящие их пополам, дальше по рекурсии каждую половину. Иногда получается, что пополам никак не хочет делиться, и приходится вернуться назад и попробовать поделить по другому на более раннем шаге :)
Кстати, почти готовый алгоритм для автоматической генерации 21826770
7 мар 19, 09:51    [21826981]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1160
Соколинский Борис
mayton,
Мы один столбец матрицы рассматриваем. Когда N=1 - очевидно логарифм.
Я ошибся в таблице
7-10 6
11-14 7
15-18(?) 8

Отношение N/M, сдается мне, должно к гамма-распределению (N-параметр) сводиться.
Ну для 7 то точно достаточно 5 тестов. Для 15 вроде после исправлений нормально за 7 шагов получается.
7 мар 19, 10:33    [21827020]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1160
Barlone
Dima T
тогда для 15 неправильно С(2,15)=105, т.е. тоже 7, а ответ 8.

PS Я не считал, просто заметил что log2(91) = log2(105)
А вы попробуйте доказать, что за 7 невозможно :)
Я кстати начал с того, что пытался доказать невозможность. А получилось вот так.
7 мар 19, 10:40    [21827030]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13367
Похоже работает твой алгоритм за 7 замеров, не нашел больше косяков.
7 мар 19, 10:48    [21827042]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4254
Barlone,

непонятно только как его масштабировать на общий случай
7 мар 19, 11:03    [21827055]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 39266
Хм... Дельфи с формочками.
7 мар 19, 11:38    [21827114]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Barlone
Barlone
пропущено...
А вы попробуйте доказать, что за 7 невозможно :)
Я кстати начал с того, что пытался доказать невозможность. А получилось вот так.


Теперь можно начать с того, что попытаться доказать невозможность для 2 из 16 )
7 мар 19, 12:27    [21827183]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1160
Aleksandr Sharahov
Barlone
пропущено...
Я кстати начал с того, что пытался доказать невозможность. А получилось вот так.


Теперь можно начать с того, что попытаться доказать невозможность для 2 из 16 )
Ну на 2 из 16 точно нужно 8 шагов.

NC(2;N)steps
332
463
5104
6155
7215
8286
9366
10456
11557
12667
13787
14917
151057
161208

Вот такая табличка пока. Для N = 6, 8, 11, 16 получается необходимое число измерений больше, чем округление вверх двоичного логарифма числа сочетаний по 2 из N.
Как вообще такое можно доказать? Ну примерно так:
До первого измерения все равноправны, поэтому тут важно только количество шаров, от выбора номеров ничего не зависит. Изначальное число вариантов C(2;N). Если у нас N шаров и на первом тесте мы проверяем K из них, то при отрицательном результате мы получаем задачу меньшей размерности: с N-K шарами. А при положительном результате первого теста ситуация получается более сложная, но общее количество оставшихся вариантов получается C(2;N)-C(2;N-K).
Для 6 я уже писал почему недостаточно 4 измерений, ну давайте еще раз напишу. Если на первом шаге измерять один шар, то при отрицательном ответе мы остались с 5 шарами, на которые надо 4 измерения. А если на первом шаге измерять 2 шара, то при отрицательном ответе у нас остается 4 шара (тут 3 измерений достаточно), но при положительном ответе у нас остается С(2;6) - С(2;4) = 15-6 = 9 вариантов, за 3 измерения их не разделить.
7 мар 19, 13:24    [21827271]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
mayton
Хм... Дельфи с формочками.


Ну, вот вам иначе.

Дерево проверок для алгоритма Barlone 2 из 15.
1. Если после группы стоят восклицательные знаки,
то их количество точно равно количеству звенящих шаров.
2. Если после группы стоит число в скобках,
то это число точно равно максимальному количеству проверок.
1)  1..5 +
2)  1,2,15 +
3)  1,6 +
4)  8..15 +
    1!(0) 8..15!(3)
4)  8..15 -
5)  1 +
6)  2 +
    1,2!!(0)
6)  2 -
    1,6!!(0)
5)  1 -
    2,6!!(0)
3)  1,6 -
4)  3..5,7..11 +
    2!(0) 3..5,7..11!(3)
4)  3..5,7..11 -
5)  2 +
    2!(0) 12..15!(2)
5)  2 -
    15!(0) 12..14!(2)
2)  1,2,15 -
3)  3,6,7 +
4)  4,5,6,7 +
5)  3 +
    3!(0) 4..7!(2)
5)  3 -
    4,5!(1) 6,7!(1)
4)  4,5,6,7 -
    3!(0) 8..14!(3)
3)  3,6,7 -
4)  4 +
    4!(0) 5,8..14!(3)
4)  4 -
    5!(0) 8..14!(3)
1)  1..5 -
2)  6..9 +
3)  10..13 +
    6..9!(2) 10..13!(2)
3)  10..13 -
4)  14..15 +
    6..9!(2) 14..15!(1)
4)  14..15 -
    6..9!!(3)
2)  6..9 -
3)  10..13 +
4)  14..15 +
    10..13!(2) 14..15!(1)
4)  14..15 -
    10..13!!(3)
3)  10..13 -
    14..15!!(0)
7 мар 19, 13:30    [21827273]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13367
А как же формула?
Barlone
Нижняя граница - двоичный логарифм числа сочетаний из N по M (с округлением вверх).

7 мар 19, 13:32    [21827275]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1160
Переходим к 8 шарам. Можно попробовать взять для первого измерения 2 или 3 шара (в других случаях будет только хуже).
Если возьмем 2, то при отрицательном ответе приходим к задаче 6 шаров, для которой надо 5 измерений.
Если возьмем 3, то при положительном ответе остается С(2;8) - С(2;5) = 28 - 10 > 16 и опять нужно еще 5.

Теперь 11 шаров. Если первый раз будем мерять 3 шара, при отрицательном ответе приходим к задаче 8 шаров, на которую как только что показали, нужно 6 измерений. Если первый раз меряем 4, С(2;11) - С(2;7) = 55 - 21 > 32 и опять еще 6.

Ну и 16 шаров. Первый раз меряем 5 шаров, ну и тут по 7 измерений в обоих ветках - либо 11 шаров, либо 120 - 55 > 64.
При другом числе шаров для первого измерения в одной из веток получим еще больше вариантов.
7 мар 19, 13:37    [21827278]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Barlone,

спасибо
7 мар 19, 13:41    [21827281]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1160
Dima T
А как же формула?
Barlone
Нижняя граница - двоичный логарифм числа сочетаний из N по M (с округлением вверх).

Так нижняя же, при некоторых значениях N недостижимая (дважды уже повторял). В чем вообще ее смысл - если нашли алгоритм с таким числом шагов, то быстрее точно не получится. А если не нашли - то надо либо искать дальше, либо пытаться доказать, что это невозможно.
7 мар 19, 13:42    [21827282]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1160
Вот примерно с такого же я пытался начать доказывать, что 2 из 15 за 7 шагов нельзя, но С(2;15) - С(2;10) = 60, и эти 60 за 6 шагов получилось поделить.
7 мар 19, 13:52    [21827301]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4254
Barlone,
доказать возможность гораздо легче, чем невозможность - достаточно пример
во втором же случае неудачные примеры доказательством не являются, если конечно речь не о доказательстве какого-то конкретного алгоритма, а у нас его пока нету

например, до прошлого века вообще считали, что невозможно умножать быстрее чем O(N^2)
7 мар 19, 13:55    [21827305]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1160
kealon(Ruslan)
Barlone,
доказать возможность гораздо легче, чем невозможность - достаточно пример
во втором же случае неудачные примеры доказательством не являются, если конечно речь не о доказательстве какого-то конкретного алгоритма, а у нас его пока нету

например, до прошлого века вообще считали, что невозможно умножать быстрее чем O(N^2)
То есть мое доказательство 21827278 вас не убедило?
7 мар 19, 14:14    [21827329]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4254
Barlone
То есть мое доказательство 21827278 вас не убедило?
это всего лишь доказательство невозможности с использованием конкретного алгоритма, а не общее

я так же могу доказать что "проверкой одного" в общем случае нужно провести (N-K) замеров
7 мар 19, 14:23    [21827342]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1160
kealon(Ruslan), ну тут то количество возможных алгоритмов конечно - 2N вариантов одного теста (2N-2 если выкинуть явно бессмысленные варианты проверять 0 шаров или сразу все шары).
7 мар 19, 14:33    [21827356]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4254
Barlone,

я о чём и говорю, обобщённого алгоритма пока нет

а вот конкретно для вашего алгоритма видно из примера, что формула log2(C(N,K)) к нему не подходит, он её не имплементирует

1-й пример:
если мы берём произвольные 3, и видим что в них нет радиоактивных

остаётся 12 кандидатов, С(12, 2) = 66 , log2(66) = 6,04439411935845 ->7

2-й пример:
С(116, 2) = 120 , log2(120) = 6,90689059560852 ->7
7 мар 19, 15:08    [21827410]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4254
Barlone,
опечатался
С(16, 2) = 120 , log2(120) = 6,90689059560852 ->7
7 мар 19, 15:09    [21827411]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5] 6 7 8   вперед  Ctrl      все
Все форумы / Программирование Ответить