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

Откуда:
Сообщений: 13634
Задача
В равнобедренном треугольнике одна сторона больше другой на 4 см. Периметр 15 см. Определите сумму одинаковых сторон

Мы с ребенком решили, оказалось чуть раньше так же они решили в школе с учителем. Жена решила по-другому, заявила что мы не правы, но обосновать свое решение не смогла, но в итоге оказалась права: мы решили неправильно.
1 мар 19, 20:31    [21823085]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Напомнило топик о золотых треугольниках.

По сабжу - нужна система типа : a + a + b = 15, a-b=4 наверное
1 мар 19, 20:41    [21823088]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
mayton, 7й класс. Все тупо, просто и ... с подвохом.
1 мар 19, 20:43    [21823090]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Равнобедренный треугольник, поэтому
2 x a +b = 15

2 варианта
1.
a= b +4
тогда
3 x b = 7

2.
a=b-4
Тогда
3 x b = 23
1 мар 19, 20:51    [21823097]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Если разница между a и b равнялась бы 3, то были бы 2 красивых варианта.
1 мар 19, 20:59    [21823109]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mikhail_n
Member

Откуда:
Сообщений: 883
Вспоминая что в треугольнике сумма двух любых сторон должна быть больше третьей стороны, получаем что единственно возможный вариант:

19/3, 19/3, 7/3

Наверное знание этого факта именно и пытались проверить в данной задаче.
2 мар 19, 04:29    [21823234]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
mikhail_n
Наверное знание этого факта именно и пытались проверить в данной задаче.

Верно.

Второе решение 11/3, 11/3, 23/3 неправильное, т.к. это не треугольник.

Это задание из билета к миниэкзамену.
Забавно то, что решали его в классе с учителем и получили два!!! ответа, т.е. учитель геометрии признал второе решение правильным.
2 мар 19, 07:49    [21823248]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Учителя подменял физрук.
2 мар 19, 11:18    [21823285]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mikhail_n
Member

Откуда:
Сообщений: 883
Дима,

Чтобы "закрепить" пройденный материал, дайте сыну задачку:

Дан равнобедренный треугольник с периметром p.

Вопрос1: В каких пределах должна находиться разница длины двух сторон d, чтобы существовало два разных равнобедренных треугольника для данного p?
Вопрос2: В каких пределах должна находиться разница длины двух сторон d, чтобы существовал только один равнобедренный треугольник для данного p?

Ответ1: 0 < d < p/4
Ответ2: p/4 < d < p/2
2 мар 19, 19:43    [21823420]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Давайте я задачку подкину. Дан произвольный треугольник. И известны 3 его медианы. Найти все остальные
свойства треугольника.

Вроде из школьной олипиады. Я ее не решал. Так что ответа не знаю.
3 мар 19, 15:12    [21823690]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
mayton, это легко.
Медианы треугольника пересекаются в одной точке (O) и делятся в соотношении 2:1.
Поэтому для каждого из треугольников OAB, OBC, OCA известны две стороны и медиана, а для этого случая есть стандартный метод решения (не помню).
3 мар 19, 15:50    [21823704]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Ладно еще задачка. Оставляю вечно себе на десер.

Дано 15 шаров. 2 из них - радиоктивны. Есть прибор который меряет шары.
За раз можно измерять 1 шар или несколько сразу.

Сколько минимум измерений нужно сделать чтоб найти эти 2 шара.
3 мар 19, 16:57    [21823731]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
mayton
Ладно еще задачка. Оставляю вечно себе на десер.

Дано 15 шаров. 2 из них - радиоктивны. Есть прибор который меряет шары.
За раз можно измерять 1 шар или несколько сразу.

Сколько минимум измерений нужно сделать чтоб найти эти 2 шара.

Если повезет, то минимум одно: убрать два случайно выбранных шара и померить оставшиеся. )))
3 мар 19, 17:09    [21823737]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Давай worst-case.
3 мар 19, 17:16    [21823742]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
mayton,
Измеритель качественный или количественный?
3 мар 19, 18:03    [21823772]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Неизвестно.

Измеритель говорит - да есть радиация в группе шаров. Или говорит - радиации нет.
3 мар 19, 18:05    [21823773]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
mayton,
значит, качественный.
7.
3 мар 19, 18:15    [21823780]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Ого
3 мар 19, 18:20    [21823782]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
Точнее - 6.
3 мар 19, 18:23    [21823786]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Я вот нарисовал свой тестовый пример. Можете шаг за шагом показать ваш алгоритм?

Ячейка с единичкой - радиоактивный шар.
01000
00000
00100
3 мар 19, 18:24    [21823787]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
Я ошибся, все-таки 7
(1,2,3,4)
(5,6,7,8)
(9,10,11,12)

Остается 8 подозрительных, предположим 1-4 и 5-8
(1,2)
(5,6)
Остается 4 подозрительных
1 (или 3)
5 (или 7)
3 мар 19, 18:33    [21823796]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Напомнило https://www.sql.ru/forum/1195739-a/iz-testovogo-zadaniya
3 мар 19, 18:34    [21823797]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Если-бы шар был 1 тогда наверное 6 измерений.
3 мар 19, 18:42    [21823803]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
mayton,
4
3 мар 19, 18:44    [21823804]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Вы берете avg? Или max?
3 мар 19, 18:57    [21823807]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
mayton,
max.
C одним шаром просто "олимпийская система": после первого измерения отсеивается 7/8, после второго - 4 и.т.д.
3 мар 19, 19:04    [21823811]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
mayton
Если-бы шар был 1 тогда наверное 6 измерений.

Если один, то бинарный поиск в чистом виде - 4 измерения. С двумя шарами сложнее.
3 мар 19, 19:47    [21823827]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
В скобках - количество измерений

7 на 8 (1)

Если по 1, то 4,2,1 (3)
И ещё 4или 3,2,1 (3)
Всего 7.

Если по 2, то 4или 3(1)

Если по 1, то 2,1 и 2,1(4)
Всего 6.

Если по 2, то 2(1)

Если по 2 то окончание,
Всего 3.

Если по 1, то 1 и 1 (2)
Всего 5.

Максимум - 7
3 мар 19, 20:06    [21823833]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
Gennadiy Usov
В скобках - количество измерений
7 на 8 (1)

Это (2)
8 получается.
3 мар 19, 20:31    [21823849]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Соколинский Борис
Gennadiy Usov
В скобках - количество измерений
7 на 8 (1)

Это (2)
8 получается.
Нет, это (1).
Ведь смотрим 7, а в 8 остаётся то, что не попало в 7
3 мар 19, 21:19    [21823868]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
Gennadiy Usov,
У нас вроде как счетчик качественный, т.е. не отличает один шар положительный в образце или два.
3 мар 19, 21:55    [21823887]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Соколинский Борис
Gennadiy Usov,
У нас вроде как счетчик качественный, т.е. не отличает один шар положительный в образце или два.

Согласно условию задачи можно измерять любое количество шаров.

Измеряем 7 или 8 шаров. Это одно измерение.

В результате становится известно, сколько радиактивных шаров оказалось в каждой из двух групп:
либо 0, либо 1, либо 2 шара.
4 мар 19, 06:59    [21824003]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
mayton
Ладно еще задачка. Оставляю вечно себе на десер.

Дано 15 шаров. 2 из них - радиоктивны. Есть прибор который меряет шары.
За раз можно измерять 1 шар или несколько сразу.

Сколько минимум измерений нужно сделать чтоб найти эти 2 шара.
7
4 мар 19, 11:45    [21824162]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
Gennadiy Usov
В результате становится известно, сколько радиактивных шаров оказалось в каждой из двух групп:либо 0, либо 1, либо 2 шара.
Насколько я понял условие - прибор просто детектирует наличие радиации, а сколько таких шаров в группе (1 или 2) он определить не может.
4 мар 19, 12:32    [21824222]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Вот еще одна постановка. Неважно что шаров 14. Принцип тот-же.

К сообщению приложен файл. Размер - 19Kb
4 мар 19, 13:56    [21824356]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
mayton,
тоже 7
4 мар 19, 14:36    [21824428]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
У меня 8 получается.
4 мар 19, 15:26    [21824528]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
Предварительные леммы. N - общее число шаров, P - число положительных, I - число итераций
N P I 
2 1 1 (С1)
4 1 2 (С2)
4 2 3 (С3)

Собственно алгоритм.
(1-4)
(5-8)
(9-12)
A. Если "звонят" две группы, находим по одному шару в каждой (С2)
Всего 7.

Б. Если звонит одна группа (условно первая)
(13 14)
Б1. Звонит - находим один шар в первой группе (С2) и один в последней (С1) Всего 7.
Б2. Не звонит - находим два шара в первой группе (С3). Всего 7.
4 мар 19, 15:57    [21824574]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Соколинский Борис
Собственно алгоритм.
(1-4)
(5-8)
(9-12)
A. Если "звонят" две группы, находим по одному шару в каждой (С2)
Всего 7.

Не хватает (13-15), это будет 8-я проверка.
4 мар 19, 16:06    [21824589]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Соколинский Борис
Б. Если звонит одна группа (условно первая)
(13 14)
Б1. Звонит - находим один шар в первой группе (С2) и один в последней (С1) Всего 7.
Б2. Не звонит - находим два шара в первой группе (С3). Всего 7.

понял где последние, только в исходной задаче их было 15, поэтому в последней тоже С2, т.е. Б1 итого 8.
4 мар 19, 16:31    [21824610]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

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

первый шар находим половинным делением - 4 проверки достаточно
второй шар находим проверяя противоположную от ветки первого прохода, их всего 3 уровня
4 мар 19, 16:37    [21824618]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

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

хотя нет, всё равно 8 нужно
4 мар 19, 16:50    [21824633]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Стандартные замеры по 8и 7, по 4, по 2, по 1.

В задачке две крайние ситуации:
-в каждом замере оказывается 2 заряженых шара (кроме последнего уровня). Тогда 8 замеров
-в замерах 1-8 и 9-15 оказывается по 1 заряженному шару. Тогда 8 замеров.

Можно "смешивать" ситуации на разных уровнях, но примерно будет также.

Самый быстрый случай, это когда шары в этом алгоритме находятся на нечётном и следующем четном месте.
Тогда замеров будет 7.

Пока не понял, чем отличается 15 от 16.

Наверное, это в задаче ситуации для 4 и 3 шаров и сравнить:
-когда в этой группе 2 заряженных шара
-когда в этой группе 1 заряженный шар.
5 мар 19, 05:51    [21824994]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
16 удачнее делится на 2. Хотя здесь-бы подошла дюжина или основа Вавилонской системы счисления 60 = 1*2*3*4*5
ибо удобнее делить по всякому.

Я думаю что 14 и 15 авторы ввели исключительно из троллига.
5 мар 19, 12:35    [21825249]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Тьфу. 60 = 1*2*2*3*5
5 мар 19, 12:37    [21825253]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
Как-то я начал слегка сомневаться в правильности алгоритма - странная зависимость от N получается (случай двух шаров)
4 3
5 4
6 5
7-8 6
9-14 7
15-16 8
16+ 9

По идее, должно быть нечто вроде логарифма. но точка 9-14 выпадает.
5 мар 19, 13:55    [21825365]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Тут матрица. M известных шаров на N радиоактивных.
5 мар 19, 14:10    [21825384]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

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

Отношение N/M, сдается мне, должно к гамма-распределению (N-параметр) сводиться.
5 мар 19, 14:29    [21825415]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6161
Надо перераскладывать шары после измерений.
6 мар 19, 11:12    [21826011]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Siemargl
Надо перераскладывать шары после измерений.

+1

Я вот думаю что надо в терминах нечеткой логики после измерения группы шаров добавлять им коеффициент
радиоактивности. Допустим померяли 5 штук. И каждому накинули некое вещественное число.
После нескольких итераций с разными группами и разным составом. Шар, получивший максимальный бонус - имеет
шанс быть точно радиоактивным.
6 мар 19, 11:17    [21826016]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
Siemargl
Надо перераскладывать шары после измерений.
-1
Задача поставлена так, что нужно оптимизировать не среднее число итераций, а максимальное. Любая перераскладка их будет увеличивать.
6 мар 19, 11:44    [21826057]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6161
Соколинский Борис
Siemargl
Надо перераскладывать шары после измерений.
-1
Задача поставлена так, что нужно оптимизировать не среднее число итераций, а максимальное. Любая перераскладка их будет увеличивать.
Без перераскладки правильный ответ 7, а вот можно ли его уменьшить перекладкой - лень придумывать )

Возможно, это даст эффект при большем количестве шаров.
6 мар 19, 12:24    [21826115]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
А в общем случае, если у нас из N шаров M радиоактивных, и мы берем какие-то K шаров, то какая вероятность, что хотя бы один из выбранных K шаров радиоактивный? Понятно, что если K > N-M, то вероятность равна 1. Если M=1, то K/N. А как в общем случае?
6 мар 19, 12:25    [21826116]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Siemargl
Без перераскладки правильный ответ 7, а вот можно ли его уменьшить перекладкой - лень придумывать )
Возможно, это даст эффект при большем количестве шаров.
Нижняя граница - двоичный логарифм числа сочетаний из N по M (с округлением вверх).
6 мар 19, 12:28    [21826118]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
Barlone
Siemargl
Без перераскладки правильный ответ 7, а вот можно ли его уменьшить перекладкой - лень придумывать )
Возможно, это даст эффект при большем количестве шаров.
Нижняя граница - двоичный логарифм числа сочетаний из N по M (с округлением вверх).
в каком плане "нижняя граница"?
если воспользоваться этой формулой, то выходит что за 8 операций можно выбрать и 2 шара из 23 -> 7,98299357469431

при особом везении можно за 4 измерения оба найти, я пока на досточность даже 7 не могу придумать
хотя всё подсказывает что так оно и есть и mayton ошибается с троллингом
6 мар 19, 12:47    [21826146]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
mayton
Siemargl
Надо перераскладывать шары после измерений.
Я вот думаю что надо в терминах нечеткой логики после измерения группы шаров добавлять им коеффициент радиоактивности. Допустим померяли 5 штук. И каждому накинули некое вещественное число.
После нескольких итераций с разными группами и разным составом. Шар, получивший максимальный бонус - имеет
шанс быть точно радиоактивным.
И не надо забывать, что шары ещё между собой подвержены радиации!
6 мар 19, 12:49    [21826149]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Gennadiy Usov
mayton
пропущено...
Я вот думаю что надо в терминах нечеткой логики после измерения группы шаров добавлять им коеффициент радиоактивности. Допустим померяли 5 штук. И каждому накинули некое вещественное число.
После нескольких итераций с разными группами и разным составом. Шар, получивший максимальный бонус - имеет
шанс быть точно радиоактивным.
И не надо забывать, что шары ещё между собой подвержены радиации!

Давай пока будем брать сухую изначальную постановку.

Физика-физикой но мы на ней уедем очень далеко.
6 мар 19, 12:51    [21826153]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
Barlone
Нижняя граница - двоичный логарифм числа сочетаний из N по M (с округлением вверх).
Это неплохое приближение, но нужна какая-то поправка. В случае 2 из 11 по оценке получается 6, а реально 7.
6 мар 19, 12:53    [21826157]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

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

хм, саму идею я понял, а как найти множество для следующей итерации проверки?
6 мар 19, 12:58    [21826162]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Barlone
Siemargl
Без перераскладки правильный ответ 7, а вот можно ли его уменьшить перекладкой - лень придумывать )
Возможно, это даст эффект при большем количестве шаров.
Нижняя граница - двоичный логарифм числа сочетаний из N по M (с округлением вверх).

Неправильная формула. Выше 21824574 решение 2 из 14 за 7 замеров, а по формуле 8.

ИМХО формула N/2 с округлением вверх.
6 мар 19, 12:59    [21826167]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

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

если я правильно понимаю его идею, то он предлагает искать сразу оба шара

на первом шаге она выглядит так

всего есть C(2,15) возможных сочетаний пар, если бы их можно было эффективно бить на две группы на каждом шаге, то он прав

фактически, я пока не вижу как это сделать

пусть на первом шаге мы разделим шары 8:7 и проверим первую группу

из шаров первой группы можно составить С(2,8) пар, второй группы - С(2,7) пар
разница C(2,15) - С(2,8) - С(2,7) = 8 *7 это пары которые можно составить с применением шаров из обеих групп

т.е. если измерение покажет что эти 8 шаров содержат радиоактивный, варианты разобьются с соотношением
[C(2,15) - С(2,7)]/ С(2,7) что вряд ли "эффективно близко" к 1:1

естественно, второй вариант, что там нету радиоактивных отбрасываем как оптимистичный
6 мар 19, 13:21    [21826194]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Для 8:7 наихудший вариант по одному в каждой группе, тогда 2 замера этих групп чтобы убедиться что в каждой по одному, затем бинарный поиск в каждой: log2(N) или по 3 замера. Итого 8 замеров.
6 мар 19, 13:27    [21826209]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

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

Неправильная формула. Выше 21824574 решение 2 из 14 за 7 замеров, а по формуле 8.

ИМХО формула N/2 с округлением вверх.
Тут то все правильно: С(2,14)=91
6 мар 19, 13:29    [21826213]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
kealon(Ruslan)
в каком плане "нижняя граница"?
В плане "необходимое число измерений не меньше, чем..."
6 мар 19, 13:33    [21826231]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

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

Неправильная формула. Выше 21824574 решение 2 из 14 за 7 замеров, а по формуле 8.

ИМХО формула N/2 с округлением вверх.
Тут то все правильно: С(2,14)=91

тогда для 15 неправильно С(2,15)=105, т.е. тоже 7, а ответ 8.

PS Я не считал, просто заметил что log2(91) = log2(105)
6 мар 19, 13:37    [21826239]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Dima T, так это нижняя граница.
6 мар 19, 13:46    [21826259]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Dima T

тогда для 15 неправильно С(2,15)=105, т.е. тоже 7, а ответ 8.

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

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

PS Я не считал, просто заметил что log2(91) = log2(105)
А вы попробуйте доказать, что за 7 невозможно :)

Зачем? Выше никто не смог предложить решение за 7 измерений. Только за 8.
6 мар 19, 13:52    [21826270]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Меня терзают смутные сомнения. Если заменить шары на биты. Типа радиоактивные - это первёрнутые
тогда поиск шара очень похож на вычисление и проверку Кода Хемминга.
6 мар 19, 14:18    [21826315]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Соколинский Борис
Barlone
Нижняя граница - двоичный логарифм числа сочетаний из N по M (с округлением вверх).
Это неплохое приближение, но нужна какая-то поправка. В случае 2 из 11 по оценке получается 6, а реально 7.
Да, поправки возникают из-за невозможности поделить варианты ровно пополам. Например, 2 из 6 - 15 вариантов. Но мы не можем поделить их на 8 + 7 вариантов. Меряем 2 шара и делим на 9 вариантов если результат положительный + 6 вариантов если результат отрицательный. На 9 вариантов уже нужно 4 измерения.
6 мар 19, 15:30    [21826405]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Господа! а почему меня всё не так?
при 13-16 за 6
11-12 за 5
9-10 за 4
остальное не пробовал вроде по схеме с 17 за 7

мои ключевые пороги для 2-х шаров - это когда одна из 2-х слагаемых достигает 2^x
Что не так?
6 мар 19, 17:08    [21826567]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Ах, Семён Семёныч! первое сравнение забываю сосчитать!
Картина меняется.
Например 15ш,
(8+7)--(4+4,4+3)--(2+2,2+2)--(1+1,1+1)
Итого 1 +2*3=7 сравнений
каждый разберу худший случай, т.е. всегда неудачно разделяю мн-во так, что сразу же меченые попадают в разные подмн-ва.

По тем же сображениям для 16 тоже 7 ...
6 мар 19, 17:24    [21826589]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
exp98
Итого 1 +2*3=7 сравнений

Откуда 1?
Две кучки: 7 и 8. В каждой может быть как по одному, так и два в одной. Проверять надо обе, т.е. 2 +2*3=8
6 мар 19, 17:29    [21826595]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Dima T, то, что надо! Признаюсь, был в плену иллюзий.
6 мар 19, 17:48    [21826620]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
Barlone
Да, поправки возникают из-за невозможности поделить варианты ровно пополам.
Нет, эти поправки уже учтены при округлении логарифма. Нужна поправка в его аргументе.
6 мар 19, 17:54    [21826627]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Типа log(x+1) ?
6 мар 19, 18:12    [21826636]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
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мя .... вот непонятно, обнаружениями или исправленями (ставлю на исправления).
6 мар 19, 18:14    [21826638]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 9699
mayton
Типа log(x+1) ?
Нет.
Когда N = 2к формула вроде как точная. Поправка должна учитывать некратность аргумента.
6 мар 19, 18:43    [21826665]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
exp98, первое моё наивное решение содержало матрицу шаров типа 3х5
где я должен бы прикладывать измеритель к столбцам и строкам.
Неоптимально. Но очень похоже на выявление ошибок четности
в старых системах связи. Матричное кодирование типа.
Отсюда пошла и мысль о Хемминге как о более математически
верном пути.
6 мар 19, 18:53    [21826675]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
mayton, а я оч давно слышал вскользь, что колич-во измерений в похожих логических задачах можно дать ответ, построив оптимальный код (для хода измерений). Но как их строить и к чему применять, хз.
Даже в этой задаче не могу решить, по какому принципу разбивать мн-во. Например (8+1) ответ 5, (7+2)=6, (5+4)=7 ...

С другой стороны, есть задачи типа о выявлении лжеца, там больше самокоррекция напрашивается. Во всяк было что-то похожее на форуме в 12-13 г. Но загвоздка в том, какой код и с какими параметрами.
6 мар 19, 19:14    [21826685]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Я подобные задачи обычно решаю отходя два шага назад. Тоесть чтобы глянуть как
задача выглядит не на 15 шарах а на 1500 например. И тогда будут более
очевидны. Или более "гладки". И "непрерывны" наши оценки. Ситуация с 1
шаром - тривиальна. Дихотомия. Два шара - сбивают с толку. Они дают некий
эффект который ломает дихтомию. Но не настолько чтоб сломать формулу.
Скорее просто вносит путаницу со старта для человека который решает шары
на малых значениях N.

По повод скриншота который я привел для 14 шаров. Я не удержался и заглянул вконец.
Пишут что 7 шагов достаточно. Это я не ради троллинга. А просто пишу видя что
интерес угас.
6 мар 19, 19:30    [21826694]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
ИМХО mayton напутал и заставил искать подвох там где его нет, т.е. вместо нездорового числа 14 21824356, которое решается за 7 измерений 21824574 вопреки общим оценкам, назвал число 15 где все банально и прозрачно.
6 мар 19, 19:30    [21826695]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Ну... прошу прощения. Эту задачу мне задал лет 15 назад один математик. И в той постановке звучало 15 шаров.

Вообще наверное суть не в этом.
6 мар 19, 19:45    [21826707]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Я свожу к случаям 2-х мн-в и в каждом по 1метке. Каждая метка тогда стандартно находится делением/2, или даже можно сразу формулой. Поэтому я думаю, что общая формула д.б. 2-х ступенчатой, т.е. с 2-мя логарифмами.
Но разбиение пополам есть редко, а бОльшее слагаемое можно менять в больших пределах [2^k; 2*2^k), чем меньшее слагаемое. Тогда при подборе слагаемых результат для меньшего слаг-го меняется чаще, т.к. степень для него м.б. меньше. Поэтому мне видится 2-х ступенчатость общей суммы.
Это так, общие соображения.
6 мар 19, 19:58    [21826720]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
exp98, проблема в том что формулы заточены на поиск одного [шара], а на два нет классических алгоритмов.
6 мар 19, 20:29    [21826747]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
mayton
Ну... прошу прощения. Эту задачу мне задал лет 15 назад один математик. И в той постановке звучало 15 шаров.

Вообще наверное суть не в этом.

Может в этом есть верх троллинга над студентами: найди подвох там где его нет. Сложно признать что подвоха нет если ты участник олимпиад и привык искать (и находить) подвох.
6 мар 19, 20:34    [21826749]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Кажется, найти 2 из 15 таки можно за 7 измерений.
6 мар 19, 20:40    [21826752]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Barlone
Кажется, найти 2 из 15 таки можно за 7 измерений.

Можно за одно 21823737, но не всегда. Решение огласи
6 мар 19, 20:43    [21826755]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Dima T
Barlone
Кажется, найти 2 из 15 таки можно за 7 измерений.

Можно за одно 21823737, но не всегда. Решение огласи
Начинается с проверки первых пяти шаров. Если там пусто, то из оставшихся 10 можно найти два за 6 проверок.
Если не пусто, меряем например 1,2,15. Каждый следующий шаг зависит от предшествующих результатов. Получается много веток. Я просто выписал все возможные варианты пар, и каждым измерением делил их на две равные части.
6 мар 19, 20:57    [21826763]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Челлендж: написать генератор решений. Ну то есть генератор алгоритмов в виде псевдокода или даже программы, выполняющей нужную последовательность проверок.
6 мар 19, 21:22    [21826770]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
Barlone
Челлендж: написать генератор решений. Ну то есть генератор алгоритмов в виде псевдокода или даже программы, выполняющей нужную последовательность проверок.


полная проверка алгоритма 21824574
+
function IsWhite(p: pInteger; count: integer; var calls: integer): boolean;
begin;
  inc(calls);
  Result:=false;
  while count>0 do begin;
    Result:=Result or (p^>=0);
    inc(p);
    dec(count);
    end;
  end;

function FindOne(p: pInteger; count: integer; var calls: integer): integer;
begin;
  if count>1 then begin;
    count:=count shr 1;
    if not IsWhite(p, count, calls) then inc(p, count);
    Result:=FindOne(p, count, calls);
    end
  else Result:=p^;
  end;

procedure TForm1.Button1Click(Sender: TObject);
var
  x: array[0..13] of integer;
  sol: array[0..1] of integer;
  group: array[0..1] of integer;
  i, j, i1, i2, calls, gcount, maxcalls, maxi1, maxi2: integer;
begin;
  maxcalls:=0; maxi1:=0; maxi2:=0;
  for i2:=1 to Length(x)-1 do begin;
    for i1:=0 to i2-1 do begin;
      for i:=0 to Length(x)-1 do x[i]:=-1;
      x[i1]:=i1;
      x[i2]:=i2;
      calls:=0;
      gcount:=0;
      if IsWhite(@x[0],4,calls) then begin; group[gcount]:=0; inc(gcount); end; //0..3
      if IsWhite(@x[4],4,calls) then begin; group[gcount]:=4; inc(gcount); end; //4..7
      if (gcount<2) and IsWhite(@x[8],4,calls) then begin; group[gcount]:=8; inc(gcount); end; //8..11

      if gcount>=2 then for i:=0 to 1 do sol[i]:=FindOne(@x[group[i]],4,calls)
      else if gcount=0 then begin;
        sol[0]:=x[12];
        sol[1]:=x[13];
        end
      else begin; //gcount=1
        if IsWhite(@x[12],2,calls) then begin;
          sol[0]:=FindOne(@x[group[0]],4,calls);
          sol[1]:=FindOne(@x[12],2,calls);
          end
        else begin;
          i:=0; j:=0;
          while (i<2) and (j<3) do begin;
            if IsWhite(@x[group[0]+j],1,calls) then begin; sol[i]:=x[group[0]+j]; inc(i); end;
            inc(j);
            end;
          if i=1 then sol[1]:=x[group[0]+3];
          end;
        end;

      if maxcalls<calls then begin;
        maxcalls:=calls; maxi1:=i1; maxi2:=i2;
        end;
      if (i1<>sol[0]) or (i2<>sol[1])
      then Memo1.Lines.Add(Format('Неверное определение %d %d <> %d %d', [i1, i2, sol[0], sol[1]]));
      end;
    end;
  Memo1.Lines.Add(Format('Максимум проверок %d для шаров %d %d', [maxcalls, maxi1, maxi2]));
  end;
6 мар 19, 22:39    [21826811]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Поиск 2 из 15 за 7 проверок. Как уже говорил, первая проверка все 1-5.
Если пусто, то вроде бы все согласны, что из оставшихся 10 можно найти 2 за 6 проверок. Эту часть расписывать не буду.

У нас осталось 60 вариантов пар, в которых присутствует хотя бы один из шаров 1-5.
Теперь проверяем 1,2,15. При положительном результате проверяем 1 и 6, иначе 3, 6 и 7.
Получилось 4 ветки, в каждую попадают по 15 вариантов пар.
В каждой за 4 проверки можно выбрать одну правильную. Сейчас все распишу.
7 мар 19, 06:34    [21826899]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Первый случай. check(1,2,15)=true, check(1,6)=true
Проверяем 8-15

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

Откуда:
Сообщений: 1187
Второй случай. check(1,2,15)=true, check(1,6)=false
Проверяем 3,4,5,7,8,9,10,11

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

Откуда:
Сообщений: 1187
Третий случай. 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. Сверху + снизу -. Дальше понятно.
7 мар 19, 06:36    [21826902]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

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

check(7,8,9,10,11,12,13,14)
check(4)
4,5 | 5,8
4,8 | 5,9
4,9 | 5,10
4,10 | 5,11
4,11 | 5,12
4,12 | 5,13
4,13 | 5,14
4,14 |
При положительном результате (слева) всегда 4 + один из ... ну думаю вы поняли
При отрицательном результате (справа) всегда 5 + один из ...
Модератор: Поправил 21826905
7 мар 19, 06:37    [21826903]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Ну вот, в самом конце опечатка. check(4) должно быть вместо check(7,8,9,10,11,12,13,14)
7 мар 19, 06:39    [21826905]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Barlone
Второй случай. check(1,2,15)=true, check(1,6)=false
Проверяем 3,4,5,7,8,9,10,11

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

Еще возможно 15 и один из 3,4,5.
7 мар 19, 09:00    [21826945]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
21826945 Если первый один из 3,4,5, то нужен 8-й замер чтобы понять где второй: 2 или 15.

В 7 замеров не уложился.
7 мар 19, 09:12    [21826951]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Dima T
Barlone
Второй случай. check(1,2,15)=true, check(1,6)=false
Проверяем 3,4,5,7,8,9,10,11

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

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

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

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

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

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

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

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

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

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

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

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

Откуда:
Сообщений: 1187
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

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

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

Откуда:
Сообщений: 1187
Соколинский Борис
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

Откуда:
Сообщений: 1187
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

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

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

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

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

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


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

Откуда:
Сообщений: 1187
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

Откуда: Москва
Сообщений: 1741
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

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

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

Откуда:
Сообщений: 1187
Переходим к 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

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

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

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

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

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

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

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

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

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

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

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

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

Откуда: Нижневартовск
Сообщений: 4489
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

Откуда: Нижневартовск
Сообщений: 4489
Barlone,
опечатался
С(16, 2) = 120 , log2(120) = 6,90689059560852 ->7
7 мар 19, 15:09    [21827411]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

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

терзают смутные сомнения, что для решения не всегда требуется делить пополам,
или что невозможно проскочить "плохой" уровень при поиске решения.
7 мар 19, 15:14    [21827419]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
kealon(Ruslan)
а вот конкретно для вашего алгоритма видно из примера, что формула log2(C(N,K)) к нему не подходит, он её не имплементирует
21827282
7 мар 19, 15:30    [21827449]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Aleksandr Sharahov
Barlone,

терзают смутные сомнения, что для решения не всегда требуется делить пополам,
или что невозможно проскочить "плохой" уровень при поиске решения.
Проскочить? Можно ли одной проверкой, дающей ответ да/нет, найти один из трех шаров? У нас в результате одной проверки есть только два варианта, невозможно выдать один из трех разных ответов после одного теста. А после x тестов возможно только 2x вариантов ответа, их негде взять больше.
7 мар 19, 15:41    [21827473]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Barlone
Aleksandr Sharahov
Barlone,

терзают смутные сомнения, что для решения не всегда требуется делить пополам,
или что невозможно проскочить "плохой" уровень при поиске решения.
Проскочить? Можно ли одной проверкой, дающей ответ да/нет, найти один из трех шаров? У нас в результате одной проверки есть только два варианта, невозможно выдать один из трех разных ответов после одного теста. А после x тестов возможно только 2x вариантов ответа, их негде взять больше.

Для 14 шаров предлагали вариант с первым делением 4,4,4,2 21824574
7 мар 19, 15:45    [21827478]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
А насчет "пополам" - вот приведенный здесь алгоритм поиска 2 из 15 на первом шаге проверяя пять шаров, делит 105 вариантов на 60+45. Если проверять четыре шара, можно поделить на 50+55. Казалось бы, ближе к "пополам", но нет, эти 55 вариантов (а это найти 2 из 11) за 6 шагов не разделить.
7 мар 19, 15:50    [21827486]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Dima T
Для 14 шаров предлагали вариант с первым делением 4,4,4,2 21824574
Так это 3 проверки, после них мы уже как-то разделили все возможные варианты пар (91) на 8 кучек. Получилось достаточно хорошо, в каждой кучке не больше 16 вариантов, чтобы за 4 оставшихся проверки найти единственный.
7 мар 19, 15:57    [21827495]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

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

я как раз об этом
7 мар 19, 15:57    [21827496]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

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

я как раз об этом


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

Откуда:
Сообщений: 1187
Aleksandr Sharahov
Barlone,

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

Откуда:
Сообщений: 1187
А. Ну да, это же понятно, необязательно точно пополам, но каждая часть не должна превосходить соответствующую степень двойки.
7 мар 19, 16:01    [21827507]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

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

терзают смутные сомнения, что для решения не всегда требуется делить пополам,
или что невозможно проскочить "плохой" уровень при поиске решения.
Проскочить? Можно ли одной проверкой, дающей ответ да/нет, найти один из трех шаров? У нас в результате одной проверки есть только два варианта, невозможно выдать один из трех разных ответов после одного теста. А после x тестов возможно только 2x вариантов ответа, их негде взять больше.


У меня мысль в некотором роде обратная.

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

Откуда: Нижневартовск
Сообщений: 4489
да, "деление" неподходящий термин
назовём "метод откусывания"
я так понимаю, что можно и снизу найти коэффициенты откусывания перебором

алгоритм бы только состряпать

путь функция откусывания Z(K, N), наша целевая функция F(K,N)

для упрощения возьмём случай K<=2

F(2, N) = 1 + Max[
F(2, N - Z(N)) - в откусанном кусочке нет ничего
... - в откусанном кусочке что-то есть вот тут как поступить пока непонятно
]

известные коэффициенты снизу:
F(2,2) = 0, Z(0,2) = 0
F(1,2) = 1, Z(1,2) = 1
F(0,2) = 0, Z(0,2) = 0

F(2,3) = 2, Z(2,3) = 1
F(1,3) = 2, Z(1,3) = 1
F(0,3) = 0, Z(0,3) = 0
7 мар 19, 18:05    [21827631]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Вы пока с этим разбиритесь, а я, коль пошла такая пьянка, вернусь вопросу с пересечением медиан. Все 100, что в шлоле я такое делал, сейчас уже не вспомнить.
Насчёт типового метода, о к-ром пишет Соколинский - наверняка это различные векторные равенства, других типовых не вспоминается.
Только мне кажется, что здесь можно без векторных уравнений.
Никогда не любил формулу Герона для площади тр-ка и не знаю как доказывается.
Пусть М - т. пересечения медиан. Берём один тр-к АМВ и угол при М.
Площадь = АМ*ВМ*Sin(М)/2 = здесь ф-ла Герона
Получили 2 неизвестных угол М и АВ
По теореме косинусов (ну или через разность векторов) АВ^2= m1^2 + m2^2 - 2*m1*m2*Cos(М)

Получили 2 ур-ния с 2-мя неизвечстными. Может они и тавтология, я не пробовал.
7 мар 19, 18:06    [21827633]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Тут, кстати, 3-й угол считать необязательно,т.к. сумма 3-х=365град)
да, выше m1= АМ, m2=ВМ
7 мар 19, 18:11    [21827637]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Трехмедианная задача - прекрасна. В ней что-то есть от начертательных
задач где есть циркуль и линейка и больше ничего.
7 мар 19, 18:18    [21827640]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
mayton, так её надо решить циркулем? "сомневаюсь я"(С)
7 мар 19, 18:23    [21827643]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Нет конешно. Не надо. Я просто подчеркиваю ее простоту и в то-же время подкапотную глубину постановки.
7 мар 19, 18:28    [21827646]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Aleksandr Sharahov

У меня мысль в некотором роде обратная.

Из того, что по завершении совокупности x тестов мы должны
хотим найти 2 шара или даже из того, что хотим получить разбиение множества
на 2x примерно равных частей никак не следует, что каждый тест
последовательно делит множество на равные части.
Ну как же, каждый тест так или иначе множество делит - часть возможных пар под условие теста попадает, часть нет.
7 мар 19, 19:16    [21827670]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
Barlone
Aleksandr Sharahov
У меня мысль в некотором роде обратная.

Из того, что по завершении совокупности x тестов мы должны
хотим найти 2 шара или даже из того, что хотим получить разбиение множества
на 2x примерно равных частей никак не следует, что каждый тест
последовательно делит множество на равные части.
Ну как же, каждый тест так или иначе множество делит - часть возможных пар под условие теста попадает, часть нет.


Да, делит.
Но множества-то разные.
Могут содержать шары:
- ровно 2,
- ровно 1,
- ровно 0,
- от 1 до 2,
- от 0 до 1,
- от 0 до 2.
Почему они обязаны быть равными по размеру?
7 мар 19, 19:43    [21827687]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
Aleksandr Sharahov
Да, делит.
Но множества-то разные.
Могут содержать шары:
- ровно 2,
- ровно 1,
- ровно 0,
- от 1 до 2,
- от 0 до 1,
- от 0 до 2.
Почему они обязаны быть равными по размеру?
Не о тех множествах речь была.
7 мар 19, 20:09    [21827694]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Barlone, миль пардон, а о каких тогда?
7 мар 19, 20:30    [21827704]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
В алгоритм 15 не вникал. Но хочу похвалить Барлона за вдумчивость, к-рую лично я упустил. Если правильно понимаю, то среди прочего в методе есть идея: после первого разбиения на 2 мн-ва (а наверное и в далнейшем тоже) не обязательно безусловно проводить 2 проверки, как я к примеру. После поверки одного мн-ва принимается решение проверять второе или дробить его на части и уж потом ....
Я правильно понял этот приём?
7 мар 19, 20:36    [21827709]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
А моя нечеткая логика? Не взлетит?
7 мар 19, 20:50    [21827719]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
неч.логика для оценочной формулы или что иное?
Для оценки я бы подумал (не в смысле буквально думать).
7 мар 19, 21:10    [21827727]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Ну это как томограф. Посмотрели на одномерную тень. Повернули наблюдаемый объект.
Посмотрели еще раз на тень. Повернули.

А потом - раз. И получили двумерный срез наблюдаемого объекта. Как колбасу срезали.

Вот я и думаю. Нечётким зрением посмотреть на шары. Только не на 14 шаров. А на 14 тысяч
например. Как-то так.
7 мар 19, 21:14    [21827730]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
Перечитал 21827271 и 21827278

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

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

Изначально пара-решение входит во все множество пар. В процессе решения
мы сокращаем это включающее множество. Когда размер включающего
множества сократится до 1 - мы нашли решение.

С этой точки зрения неважно, какие проверки мы делаем,
важно лишь, как при этих проверках сокращается включающее множество.
При любой проверке мы разбиваем множество пар на 2 части: включающую
и не влючающую. Мы всегда предполагаем худшее, а именно, что включающее
множество - большее из полученных. Очевидно, что если в х шагах от выдачи
результата размер включающего множества превышает 2х,
то решение найти не удастся. В силу дискретности задачи граница лежит ниже.

Удобно сначала построить последовательности проверок для меньших
количеств шаров. Эти построения можно использовать, если окажется,
что это множество ни разу не проверялось и оба шара лежат там.
8 мар 19, 11:28    [21827856]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Aleksandr Sharahov, а можно интерпретировать это для бывших танкистов. Из такого объяснения понял только 1-й и последний абзацы.
П.С.
В связи с 1-м абзацем поздравляю всех наших жён с наступившей, бр-р-р, весной.
В связи с отсутствием их интереса к топику, предлагаю им пожелать скорректировать вектор интересов от "kinder, cookery, show" в средней или последней части.
8 мар 19, 16:51    [21828031]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Может для общего языка ссылаться на случаи согласно типовой нумерации.
типа такого:
+
degree10,nn,       code,binary,           Hex,   Count(digits)
0,0,      0,0b000000000000000,0x0000,15
1,1,     11,0b000000000000011,0x0003,15
2,2,    101,0b000000000000101,0x0005,15
2,3,    110,0b000000000000110,0x0006,15
3,4,   1001,0b000000000001001,0x0009,15
3,5,   1010,0b000000000001010,0x000A,15
3,6,   1100,0b000000000001100,0x000C,15
4,7,  10001,0b000000000010001,0x0011,15

Вкладываю для 15.

К сообщению приложен файл (CodeHex.csv - 5Kb) cкачать
8 мар 19, 17:01    [21828034]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Допустим оба тухлых яйца расположились как "....10001" (случай 7), но мы пока этого не знаем. Что дальше?.. Что за пары чисел, что и когда разбивает 105 случаев на включающую и не включающую части ?...
Хочется услышать как-нибудь поструктурнее.
8 мар 19, 17:13    [21828036]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
exp98
Aleksandr Sharahov, а можно интерпретировать это для бывших танкистов. Из такого объяснения понял только 1-й и последний абзацы.
П.С.
В связи с 1-м абзацем поздравляю всех наших жён с наступившей, бр-р-р, весной.
В связи с отсутствием их интереса к топику, предлагаю им пожелать скорректировать вектор интересов от "kinder, cookery, show" в средней или последней части.


Вообще-то это как раз и была интерпретация разъяснений Barlone )
Если интерпретировать интерпетацию она вырождается в нечто в роде такого:

Рассмотрим множество всевозможных пар шаров мощностью C(2,N).
Нас интерересует только один элемент этого множества - пара звенящих шаров.
Каждый тест, возвращая булевский результат, тем самым делит множество на 2 части.
И нет никакого способа найти нашу пару быстрее log(C(2,N)) ,
т.к. мы будем вредить, перенумеровывая шары перед каждым тестом,
но не нарушая результатов предыдущих тестов.
8 мар 19, 17:50    [21828050]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
exp98
Допустим оба тухлых яйца расположились как "....10001" (случай 7), но мы пока этого не знаем. Что дальше?.. Что за пары чисел, что и когда разбивает 105 случаев на включающую и не включающую части ?...
Хочется услышать как-нибудь поструктурнее.


В данном случае мы пытаемся только оценить количество шагов, а не построить алгоритм.
Поэтому анализ неконструктивный.
8 мар 19, 18:11    [21828057]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Aleksandr Sharahov, спасибо за разъяснения. Поначалу я так же думал, что для кодирования 128 номеров необходимо 7 бит, потом у меня всё смешалось и таким остаётся.
Смущает, что С(12)=11*12/2=66 между (64; 128), и у меня для 12 раз за разом ответ 7. Но может я путаю, осталось убеждение, что все говорят для 12 ответ 6 или нет? ох, как неохота выискивать на страницах ...

Но с другой стороны, 7 бит - это когда номера произвольные. В задаче всё же номера имеют внутреннюю структуру ( 10101 - не м.б. и т.п.), и не все случаи равновероятны. Например при проверке кучек 6+1+1 не может получиться 002 или 111.
В общем какие-то ассоциации с частотным кодированием по Хэммингу. Может здесь эти ассоциации срабатывают? Лично я уже ни в чём не уверен.
8 мар 19, 18:19    [21828064]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
exp98
Aleksandr Sharahov, спасибо за разъяснения. Поначалу я так же думал, что для кодирования 128 номеров необходимо 7 бит, потом у меня всё смешалось и таким остаётся.
Смущает, что С(12)=11*12/2=66 между (64; 128), и у меня для 12 раз за разом ответ 7. Но может я путаю, осталось убеждение, что все говорят для 12 ответ 6 или нет? ох, как неохота выискивать на страницах ...

Но с другой стороны, 7 бит - это когда номера произвольные. В задаче всё же номера имеют внутреннюю структуру ( 10101 - не м.б. и т.п.), и не все случаи равновероятны. Например при проверке кучек 6+1+1 не может получиться 002 или 111.
В общем какие-то ассоциации с частотным кодированием по Хэммингу. Может здесь эти ассоциации срабатывают? Лично я уже ни в чём не уверен.


Для 12 ответ 7, см. 21827271.

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

З.Ы. В этой задаче такие ассоциации мне только мешают )
8 мар 19, 20:01    [21828107]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
Полная проверка алгоритма Barlone (2 из 15) на Delphi без формочек:

+
function IsWhite(const balls, white: string; var calls: integer): boolean;
var
  i: integer;
begin;
  inc(calls);
  Result:=false;
  for i:=1 to Length(balls) do Result:=Result or (balls[i]=white[1]) or (balls[i]=white[2]);
  end;

function Find1(const balls, white: string; var calls: integer): char;
var
  half, count: integer;
begin;
  count:=Length(balls);
  half:=(count+1) shr 1;
  if count<=1
  then Result:=balls[1]
  else if IsWhite(copy(balls,1,half), white, calls)
       then Result:=Find1(copy(balls,1,half), white, calls)
       else Result:=Find1(copy(balls,1+half,count-half), white, calls);
  end;

function Find2(const balls, white: string; var calls: integer): string;
var
  i: integer;
begin;
  Result:='';
  for i:=1 to Length(balls)-1 do if IsWhite(balls[i], white, calls) then begin;
    Result:=Result+balls[i];
    if Length(Result)=2 then exit;
    end;
  Result:=Result+balls[Length(balls)];
  end;

function Find2From15(const balls, white: string; var calls: integer): string;
begin;
  if IsWhite('12345',white,calls)
  then if IsWhite('12f',white,calls)
       then if IsWhite('16',white,calls)
            then if IsWhite('89abcdef',white,calls)
                 then Result:='1'+Find1('89abcdef',white,calls)
                 else if IsWhite('3457',white,calls)
                      then Result:='1'+Find1('3457',white,calls)
                      else Result:=Find2('126',white,calls)
            else if IsWhite('cdef',white,calls)
                 then if IsWhite('f',white,calls)
                      then Result:=Find1('2345',white,calls)+'f'
                      else Result:='2'+Find1('cde',white,calls)
                 else Result:='2'+Find1('345789ab',white,calls)
       else if IsWhite('367',white,calls)
            then if IsWhite('4567',white,calls)
                 then if IsWhite('3',white,calls)
                      then Result:='3'+Find1('4567',white,calls)
                      else Result:=Find1('45',white,calls)+Find1('67',white,calls)
                 else Result:='3'+Find1('89abcde',white,calls)
            else if IsWhite('4',white,calls)
                 then Result:='4'+Find1('589abcde',white,calls)
                 else Result:='5'+Find1('89abcde',white,calls)
  else if IsWhite('6789',white,calls)
       then if IsWhite('abcd',white,calls)
            then Result:=Find1('6789',white,calls)+Find1('abcd',white,calls)
            else if IsWhite('ef',white,calls)
                 then Result:=Find1('6789',white,calls)+Find1('ef',white,calls)
                 else Result:=Find2('6789',white,calls)
       else if IsWhite('abcd',white,calls)
            then if IsWhite('ef',white,calls)
                 then Result:=Find1('abcd',white,calls)+Find1('ef',white,calls)
                 else Result:=Find2('abcd',white,calls)
            else Result:='ef';
  end;

function Validate: string;
const
  hex: array[0..15] of char= '0123456789abcdef';
var
  white, sol, maxsol: string;
  ch1, ch2: char;
  i, j, i1, i2, calls, maxcalls: integer;
begin;
  maxcalls:=0;
  for i2:=2 to 15 do begin;
    for i1:=1 to i2-1 do begin;
      white:=hex[i1]+hex[i2];
      calls:=0;
      sol:=Find2From15('abcd',white,calls);
      if maxcalls<calls then begin;
        maxcalls:=calls; maxsol:=sol;
        end;
      if white<>sol then begin;
        Result:=Format('Тест завален, неверное определение %s<>%s', [sol, white]);
        exit;
        end;
      end;
    end;
  Result:=Format('Тест пройден, максимум проверок %d для шаров %s', [maxcalls, maxsol]);
  end;
9 мар 19, 00:48    [21828222]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
По похожему принципу решаются задачи на взвешивания типа "найти две фальшивых монеты из 13", только делить надо на 3 части.
(известно что фальшивые монеты одинакового веса и тяжелее настоящих, у нас есть рычажные весы без гирь...)
9 мар 19, 06:42    [21828251]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Barlone, и так же тухлые яйца,помидоры и т.п., только их не взвешивают, а вонь проверяют))

Э-э, вопрос был к дельфам: а) где ж её взять или хотя бы интерпретатор;
б) недопонял это
  if IsWhite('12f',white,calls).......
и подобное.
Это повторная проверка шаров 1 и 2? для чего? ведь перед этим
  IsWhite('12345',......

Ведь судя по самой последней проверке
            then if IsWhite('ef',white,calls)
then Result:=Find1('abcd',white,calls)+Find1('ef',white,calls)
else Result:=Find2('abcd',white,calls)
else Result:='ef';
ф-ция IsWhite() проверяет отсутствие. Или наоборот?
9 мар 19, 14:17    [21828381]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
exp98
Barlone, и так же тухлые яйца,помидоры и т.п., только их не взвешивают, а вонь проверяют))

Э-э, вопрос был к дельфам: а) где ж её взять или хотя бы интерпретатор;
б) недопонял это
  if IsWhite('12f',white,calls).......
и подобное.
Это повторная проверка шаров 1 и 2? для чего? ведь перед этим
  IsWhite('12345',......

Ведь судя по самой последней проверке
            then if IsWhite('ef',white,calls)
then Result:=Find1('abcd',white,calls)+Find1('ef',white,calls)
else Result:=Find2('abcd',white,calls)
else Result:='ef';
ф-ция IsWhite() проверяет отсутствие. Или наоборот?


a) скачать стартовую версию бесплатно у производителя

б) IsWhite('12345', '37', calls) проверяет светимость группы шаров 12345,
если по условию дано, что светятся шары 37,
т.е. вхождение одного из шаров 3 или 7 в группу 12345.
При этом инкрементируется счетчик проверок calls

Да эта проверка повторно затрагивает шары 1 и 2, таков алгоритм.

IsWhite() проверяет наличие светимости
9 мар 19, 14:45    [21828392]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
интересно, что тот же алгоритм с очевидными изменениями
находит 2 шара из 20 за 8 проверок, а вот что делать дальше неясно.
9 мар 19, 15:26    [21828400]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Так получилось, что сам только что заглянул, поэтому спрашиваю.
Непонятна цель повторной проверки. Скорее всего просто так родилось, ну и оставили.
Умозрительно кажется, что
  if IsWhite('12f',white,calls).......
можно заменить на проверку только "f".
9 мар 19, 15:35    [21828403]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Aleksandr Sharahov
дальше неясно.
Дальше переходить на полный бэктрекинг и генерацию подмножеств 2^21 ...
Вообще, стоит покопаться в работах по обнаружению ошибок.
9 мар 19, 15:40    [21828405]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
exp98
Так получилось, что сам только что заглянул, поэтому спрашиваю.
Непонятна цель повторной проверки. Скорее всего просто так родилось, ну и оставили.
Умозрительно кажется, что
  if IsWhite('12f',white,calls).......
можно заменить на проверку только "f".


Нет, нельзя. Смысл изменится.
Там каждая циферка играет свою роль.
9 мар 19, 15:41    [21828406]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Ни фига не понимаю почему. Ведь если '12345' не пахнут, почему '12f' могут отличаться от 'f'? Ведь первые 2 ифа работают по этой логике.
9 мар 19, 15:49    [21828407]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
У меня сведения старые, по автоматическому синтезу алгоритмов можно ещё почитать. У нас давно ещё направление развивал Лупанов ОБ., ну и другие менее тогда известные.
9 мар 19, 15:59    [21828408]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
exp98
Ни фига не понимаю почему. Ведь если '12345' не пахнут, почему '12f' могут отличаться от 'f'? Ведь первые 2 ифа работают по этой логике.
нет, вторая проверка в 'true' ветке. Среди 12345 есть меченый, но это может быть и не 12.
9 мар 19, 16:09    [21828409]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
exp98
Ни фига не понимаю почему. Ведь если '12345' не пахнут, почему '12f' могут отличаться от 'f'? Ведь первые 2 ифа работают по этой логике.


тут надо узнать как можно больше про пару 12, а f подмешиваем, чтобы использовать знание о нем ниже
логика такая: если 12f не пахнут, то 12 не пахнут, и значит пахнут 345
а в нижних else-ветках мы уже знаем, что и f не пахнет
9 мар 19, 16:10    [21828411]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
Хорошо, вам лучше знать,
IsWhite() == тру, при наличии метки
IsWhite() == фолс, при отсутствии метки.
Раньше я думал что IsWhite() действует наоборот.

Тогда "все сходится, ребёночек не наш"(с).
Спасибо за разъяснения.
9 мар 19, 20:40    [21828501]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
exp98
У меня сведения старые, по автоматическому синтезу алгоритмов
ошибся, вроде д.б. по автоматическому синтезу логических схем.
9 мар 19, 20:43    [21828502]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
exp98
Э-э, вопрос был к дельфам: а) где ж её взять или хотя бы интерпретатор;

тынц
9 мар 19, 22:02    [21828545]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
Aleksandr Sharahov
интересно, что тот же алгоритм с очевидными изменениями
находит 2 шара из 20 за 8 проверок, а вот что делать дальше неясно.
и 2 из 23 за 8 можно, должен быть масштабируемый алгоритм

Barlone прав, число возможных расстановок C(k,N) а значит минимально достаточно log2(C(k,N)) бит что бы описать любой из вариантов расстановки
9 мар 19, 22:05    [21828547]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
вселенная с этим не согласна
9 мар 19, 23:09    [21828575]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1187
kealon(Ruslan)
Aleksandr Sharahov
интересно, что тот же алгоритм с очевидными изменениями
находит 2 шара из 20 за 8 проверок, а вот что делать дальше неясно.
и 2 из 23 за 8 можно, должен быть масштабируемый алгоритм

Barlone прав, число возможных расстановок C(k,N) а значит минимально достаточно log2(C(k,N)) бит что бы описать любой из вариантов расстановки
не, эта оценка не всегда достижима 21827278 и 2 из 23 за 8 не получится
10 мар 19, 11:05    [21828662]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
Barlone
kealon(Ruslan)
пропущено...
и 2 из 23 за 8 можно, должен быть масштабируемый алгоритм

Barlone прав, число возможных расстановок C(k,N) а значит минимально достаточно log2(C(k,N)) бит что бы описать любой из вариантов расстановки
не, эта оценка не всегда достижима 21827278 и 2 из 23 за 8 не получится


и причина тут тот же закон сохранения информации
например 2 из 16 не получится

т.к. C(16,2) = 120

C(12,2) = 66 > 64
а С(11,2) = 55 и останется 120 - 55 = 65, что тоже >64

исходя из этого же следует что в вашем алгоритме ошика, нельзя откусить первым шагом 3, только 4 или 5
10 мар 19, 12:40    [21828675]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

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

с 4 довольно тривиально, а вот с 5 я кое как придумал
10 мар 19, 12:41    [21828676]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
Barlone,
поправлю
исходя из этого же следует что в вашем алгоритме ошибка, нельзя "откусить" от 15-ти первым шагом 3, только 4 или 5

т.к. C(12,2) = 66 > 64
10 мар 19, 12:45    [21828677]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
kealon(Ruslan), дык он ад хок делал для 15/2ш. Попутно могло подойти и для нек-х других.
А вообще, в теории алгоритмов известны примеры неразрешимых массовых алгоритммических проблем, к-рые тем не менее имеют решения для частных случаев.
Это может означать к примеру, что высказанный Бароном метод построения алгоритма не универсален, но если поработать над методом (или над высказыванием), мало ли, может и получится универсальный для N/2.
Вообще же, это математическая задача, не программистская.

П.С. ссылка хорошая, кто-то ею уже попользовался))
10 мар 19, 13:39    [21828690]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1624
kealon(Ruslan)
а значит минимально достаточно log2(C(k,N)) бит что бы описать любой из вариантов
Как осуществлять поиск 1 значения в массиве знают все. А вот как быстро искать 2 значения?
10 мар 19, 13:47    [21828692]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
exp98
kealon(Ruslan)
а значит минимально достаточно log2(C(k,N)) бит что бы описать любой из вариантов
Как осуществлять поиск 1 значения в массиве знают все. А вот как быстро искать 2 значения?


Так же )

Хитрости типа 2 из 15 имеют смысл только на малых массивах,
а на больших задача "найти 2" превращается в задачу "2 раза найти 1".
10 мар 19, 17:19    [21828734]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Aleksandr Sharahov
exp98
пропущено...
Как осуществлять поиск 1 значения в массиве знают все. А вот как быстро искать 2 значения?


Так же )

Хитрости типа 2 из 15 имеют смысл только на малых массивах,
а на больших задача "найти 2" превращается в задачу "2 раза найти 1".

По сути на больших 2 из N мы можем улучшать только среднюю оценку
поиска. Но максимальную не улучшим.

Верно?
10 мар 19, 21:02    [21828788]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
Например, надо найти 2 из 32.
Рассмотрим крайние случаи.

1. Проверяем левую половину, затем правую,
и числа сразу попадают в разные части.
Сокращаем размер каждой части: 8-4-2-1.
Итого 2+4*2=10 проверок.

2. Проверяем левую половину, затем правую,
и каждый раз числа попадают в правую часть:
16-8-4-2. Итого 4*2+1=9 проверок.

С(2,32)=496~512=2^9, т.е. мы в принципе
не могли затратить меньше 9 проверок.
10 мар 19, 21:14    [21828789]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
Aleksandr Sharahov
Например, надо найти 2 из 32.
Рассмотрим крайние случаи.

1. Проверяем левую половину, затем правую,
и числа сразу попадают в разные части.
Сокращаем размер каждой части: 8-4-2-1.
Итого 2+4*2=10 проверок.

2. Проверяем левую половину, затем правую,
и каждый раз числа попадают в правую часть:
16-8-4-2. Итого 4*2+1=9 проверок.

С(2,32)=496~512=2^9, т.е. мы в принципе
не могли затратить меньше 9 проверок.


Сорри скопипастил сдуру,
во втором случае, конечно, всего 4 проверки.

В худшем случае мы тратим всего 1 лишнюю проверку
10 мар 19, 21:23    [21828790]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1741
Относительно средней оценки все выглядит так,
будто она мало зависит от алгоритма.
Плюс-минус одна проверка не имеет значения,
если их десятки.
10 мар 19, 21:31    [21828795]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
ну вот, пришёл Александ и всё опошлил :-)
11 мар 19, 06:33    [21828852]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
вариант с первоначальным "откусыванием" 5 (без трививальной части )

+
program SetTest;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  SysUtils;

type
  TSetNum = 1..15;
  TSet = set of TSetNum;

  TTest = function(A: TSet): Boolean of object;


function BinS(m: TTest; a, b: Integer): TSet;
var
  l, i: Integer;
  v: TSet;
begin
  repeat
    l := a + (b - a) div 2;
    v := [];
    for i := a to l do
      v := v + [i];
    if m(v) then begin
      b := l;
      if l = a then
        Exit([a]);
    end else
    begin
      if a = l then
        Exit([b]);
      a := l + 1;
    end;
  until False;
end;

function Alg(m: TTest): TSet;
begin
  // Всего С(2,15) = 105
  if m([1..5]) then begin
    // C(2,5) + 5 * 10 =   60
    if m([4,5,6]) then begin
      // C(2,6) - C(2,3)  + 2 * 9 = 30
      if m([8..15]) then begin
        // 2 *  8 = 16
        Result := BinS(m, 4, 5) + BinS(m, 8, 15);
      end else begin
        // C(2,6) - C(2,3)  + 2 * 1 = 14
        if m([1, 6]) then begin
          // 3 + 4 = 7
          if m([1]) then begin
            // 3
            Result := [1] + BinS(m, 4, 6);
          end else begin
            // 4
            Result :=  [6] + BinS(m, 2, 5);
          end;
        end else begin
          // C(2,4) -1 + 2 = 7
          if m([2,3]) then begin
            // C(2,3) = 4
            Result := BinS(m, 2, 3) + BinS(m, 4, 5);
          end else begin
            // 3
            if m([7]) then
              Result := [7] + BinS(m, 4, 5)
            else
              Result := [4,5];
          end;
        end;
      end;
    end else begin
      // C(2,3) + 3* 9 = 30
      if m([3,7,8]) then begin
        // C(2, 5) - 2 {без [1,2] и [7,8]} + 1 * 7 = 15
        if m([9..15]) then begin
          // 7
          Result := [3] + BinS(m, 9, 15);
        end else begin
          // C(2, 5) - 2 = 8
          if m([3]) then begin
            // 4
            if m([7,8]) then begin
              if m([7]) then
                Result := [7]
              else
                Result := [8];
            end else begin
              if m([1]) then
                Result := [1]
              else
                Result := [2];
             end;
            Result := Result + [3];
          end else begin
            // 2 * 2 = 4
            if m([1]) then
              Result := [1]
            else
              Result := [2];
            if m([7]) then
              Result := Result + [7]
            else
              Result := Result + [8]
          end;
        end;
      end else begin
        // C(2,2) + 2 * 7 = 15
        if m([12..15]) then begin
          // 2 * 4 = 8
          Result := BinS(m, 1, 2) + BinS(m, 12, 15);
        end else begin
          // C(2,2) + 2 * 3 = 7
          if m([10,11]) then begin
            // 2 * 2
            Result := BinS(m, 1, 2) + BinS(m, 10, 11);
          end else begin
            //C(2,2) + 2 * 1 = 3
            if (m([9])) then begin
              Result := BinS(m, 1, 2) + [9];
            end else begin
              Result := [1,2];
            end;
          end;
        end;
      end;
    end;
  end else begin
    // С(2, 10) = 45   - тривиальный, не буду рассматривать
    Result := [];
  end;
end;

type
  TSetTest = record
    v: TSet;
    c: Integer;
    constructor create(i,j: Integer);
    function Con(A: TSet): Boolean;
  end;

function TSetTest.Con(A: TSet): Boolean;
begin
  Inc(c);
  Result := (v * A <> []);
end;

constructor TSetTest.Create(i, j: Integer);
begin
  c := 0;
  v := [i,j];
end;

var
  i,j: Integer;
  TestM: TSetTest;
  s: TSet;
begin
  try
    for i := 1 to 5 do
      for j := i + 1 to 15 do begin
        TestM := TSetTest.create(i,j);
        s := Alg(TestM.Con);
        if (TestM.v <> s)or(TestM.c > 7) then begin


          TestM := TSetTest.Create(i,j);
          s := Alg(TestM.Con);

          raise Exception.Create('Error Message');
        end;
      end;
    Writeln('Ok');
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.
11 мар 19, 10:51    [21828949]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4 5 6 7 8      [все]
Все форумы / Программирование Ответить