Пятничный треугольник / Программирование

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничный треугольник

188 сообщений из 188, показаны все 8 страниц

все

Пятничный треугольник

#39781228

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

ЗадачаВ равнобедренном треугольнике одна сторона больше другой на 4 см. Периметр 15 см. Определите сумму одинаковых сторон
Мы с ребенком решили, оказалось чуть раньше так же они решили в школе с учителем. Жена решила по-другому, заявила что мы не правы, но обосновать свое решение не смогла, но в итоге оказалась права: мы решили неправильно.

...

Рейтинг:

0 / 0

01.03.2019, 20:31

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781231

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Напомнило топик о золотых треугольниках.

По сабжу - нужна система типа : a + a + b = 15, a-b=4 наверное

...

Рейтинг:

0 / 0

01.03.2019, 20:41

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781233

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

mayton, 7й класс. Все тупо, просто и ... с подвохом.

...

Рейтинг:

0 / 0

01.03.2019, 20:43

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781238

Gennadiy Usov

Гость

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

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

2.
a=b-4
Тогда
3 x b = 23

...

Рейтинг:

0 / 0

01.03.2019, 20:51

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781246

Gennadiy Usov

Гость

Если разница между a и b равнялась бы 3, то были бы 2 красивых варианта.

...

Рейтинг:

0 / 0

01.03.2019, 20:59

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781291

mikhail_n

Участник

Сообщения: 1 179

Рейтинг: 0 / 0

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

19/3, 19/3, 7/3

Наверное знание этого факта именно и пытались проверить в данной задаче.

...

Рейтинг:

0 / 0

02.03.2019, 04:29

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781298

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

mikhail_nНаверное знание этого факта именно и пытались проверить в данной задаче.
Верно.

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

Это задание из билета к миниэкзамену.
Забавно то, что решали его в классе с учителем и получили два!!! ответа, т.е. учитель геометрии признал второе решение правильным.

...

Рейтинг:

0 / 0

02.03.2019, 07:49

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781324

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Учителя подменял физрук.

...

Рейтинг:

0 / 0

02.03.2019, 11:18

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781384

mikhail_n

Участник

Сообщения: 1 179

Рейтинг: 0 / 0

Дима,

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

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

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

Ответ1: 0 < d < p/4
Ответ2: p/4 < d < p/2

...

Рейтинг:

0 / 0

02.03.2019, 19:43

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781522

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Давайте я задачку подкину. Дан произвольный треугольник. И известны 3 его медианы. Найти все остальные
свойства треугольника.

Вроде из школьной олипиады. Я ее не решал. Так что ответа не знаю.

...

Рейтинг:

0 / 0

03.03.2019, 15:12

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781533

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

mayton, это легко.
Медианы треугольника пересекаются в одной точке (O) и делятся в соотношении 2:1.
Поэтому для каждого из треугольников OAB, OBC, OCA известны две стороны и медиана, а для этого случая есть стандартный метод решения (не помню).

...

Рейтинг:

0 / 0

03.03.2019, 15:50

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781557

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Ладно еще задачка. Оставляю вечно себе на десер.

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

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

...

Рейтинг:

0 / 0

03.03.2019, 16:57

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781562

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonЛадно еще задачка. Оставляю вечно себе на десер.

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

Сколько минимум измерений нужно сделать чтоб найти эти 2 шара.
Если повезет, то минимум одно: убрать два случайно выбранных шара и померить оставшиеся. )))

...

Рейтинг:

0 / 0

03.03.2019, 17:09

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781565

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Давай worst-case.

...

Рейтинг:

0 / 0

03.03.2019, 17:16

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781585

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

mayton,
Измеритель качественный или количественный?

...

Рейтинг:

0 / 0

03.03.2019, 18:03

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781586

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Неизвестно.

Измеритель говорит - да есть радиация в группе шаров. Или говорит - радиации нет.

...

Рейтинг:

0 / 0

03.03.2019, 18:05

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781587

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

mayton,
значит, качественный.
7.

...

Рейтинг:

0 / 0

03.03.2019, 18:15

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781588

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Ого

...

Рейтинг:

0 / 0

03.03.2019, 18:20

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781590

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

Точнее - 6.

...

Рейтинг:

0 / 0

03.03.2019, 18:23

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781591

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Я вот нарисовал свой тестовый пример. Можете шаг за шагом показать ваш алгоритм?

Ячейка с единичкой - радиоактивный шар.

Код: sql

1.
2.
3.

01000
00000
00100

...

Рейтинг:

0 / 0

03.03.2019, 18:24

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781593

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

Я ошибся, все-таки 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)

...

Рейтинг:

0 / 0

03.03.2019, 18:33

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781594

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Напомнило http://www.sql.ru/forum/1195739-a/iz-testovogo-zadaniya

...

Рейтинг:

0 / 0

03.03.2019, 18:34

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781596

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Если-бы шар был 1 тогда наверное 6 измерений.

...

Рейтинг:

0 / 0

03.03.2019, 18:42

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781597

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

mayton,
4

...

Рейтинг:

0 / 0

03.03.2019, 18:44

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781599

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Вы берете avg? Или max?

...

Рейтинг:

0 / 0

03.03.2019, 18:57

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781601

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

mayton,
max.
C одним шаром просто "олимпийская система": после первого измерения отсеивается 7/8, после второго - 4 и.т.д.

...

Рейтинг:

0 / 0

03.03.2019, 19:04

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781612

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonЕсли-бы шар был 1 тогда наверное 6 измерений.
Если один, то бинарный поиск в чистом виде - 4 измерения. С двумя шарами сложнее.

...

Рейтинг:

0 / 0

03.03.2019, 19:47

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781614

Gennadiy Usov

Гость

В скобках - количество измерений

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

...

Рейтинг:

0 / 0

03.03.2019, 20:06

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781624

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

Gennadiy UsovВ скобках - количество измерений
7 на 8 (1)

Это (2)
8 получается.

...

Рейтинг:

0 / 0

03.03.2019, 20:31

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781633

Gennadiy Usov

Гость

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

Это (2)
8 получается.Нет, это (1).
Ведь смотрим 7, а в 8 остаётся то, что не попало в 7

...

Рейтинг:

0 / 0

03.03.2019, 21:19

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781640

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

Gennadiy Usov,
У нас вроде как счетчик качественный, т.е. не отличает один шар положительный в образце или два.

...

Рейтинг:

0 / 0

03.03.2019, 21:55

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781681

Gennadiy Usov

Гость

Соколинский БорисGennadiy Usov,
У нас вроде как счетчик качественный, т.е. не отличает один шар положительный в образце или два.
Согласно условию задачи можно измерять любое количество шаров.

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

В результате становится известно, сколько радиактивных шаров оказалось в каждой из двух групп:
либо 0, либо 1, либо 2 шара.

...

Рейтинг:

0 / 0

04.03.2019, 06:59

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781798

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

...

Рейтинг:

0 / 0

04.03.2019, 11:45

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781842

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

Gennadiy UsovВ результате становится известно, сколько радиактивных шаров оказалось в каждой из двух групп:либо 0, либо 1, либо 2 шара. Насколько я понял условие - прибор просто детектирует наличие радиации, а сколько таких шаров в группе (1 или 2) он определить не может.

...

Рейтинг:

0 / 0

04.03.2019, 12:32

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781926

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Вот еще одна постановка. Неважно что шаров 14. Принцип тот-же.

...

Рейтинг:

0 / 0

04.03.2019, 13:56

| Ответить | Цитировать | Написать

Пятничный треугольник

#39781980

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

mayton,
тоже 7

...

Рейтинг:

0 / 0

04.03.2019, 14:36

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782046

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

У меня 8 получается.

...

Рейтинг:

0 / 0

04.03.2019, 15:26

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782072

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

Предварительные леммы. N - общее число шаров, P - число положительных, I - число итераций

Код: plaintext

1.
2.
3.
4.

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.

...

Рейтинг:

0 / 0

04.03.2019, 15:57

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782084

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

04.03.2019, 16:06

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782102

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Соколинский БорисБ. Если звонит одна группа (условно первая)
(13 14)
Б1. Звонит - находим один шар в первой группе (С2) и один в последней (С1) Всего 7.
Б2. Не звонит - находим два шара в первой группе (С3). Всего 7.
понял где последние, только в исходной задаче их было 15, поэтому в последней тоже С2, т.е. Б1 итого 8.

...

Рейтинг:

0 / 0

04.03.2019, 16:31

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782108

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Dima T,

первый шар находим половинным делением - 4 проверки достаточно
второй шар находим проверяя противоположную от ветки первого прохода, их всего 3 уровня

...

Рейтинг:

0 / 0

04.03.2019, 16:37

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782120

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Dima T,

хотя нет, всё равно 8 нужно

...

Рейтинг:

0 / 0

04.03.2019, 16:50

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782306

Gennadiy Usov

Гость

Стандартные замеры по 8и 7, по 4, по 2, по 1.

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

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

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

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

Наверное, это в задаче ситуации для 4 и 3 шаров и сравнить:
-когда в этой группе 2 заряженных шара
-когда в этой группе 1 заряженный шар.

...

Рейтинг:

0 / 0

05.03.2019, 05:51

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782436

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

Я думаю что 14 и 15 авторы ввели исключительно из троллига.

...

Рейтинг:

0 / 0

05.03.2019, 12:35

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782439

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Тьфу. 60 = 1*2*2*3*5

...

Рейтинг:

0 / 0

05.03.2019, 12:37

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782492

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

Как-то я начал слегка сомневаться в правильности алгоритма - странная зависимость от N получается (случай двух шаров)
4 35 46 57-8 69-14 715-16 8 16+ 9
По идее, должно быть нечто вроде логарифма. но точка 9-14 выпадает.

...

Рейтинг:

0 / 0

05.03.2019, 13:55

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782502

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Тут матрица. M известных шаров на N радиоактивных.

...

Рейтинг:

0 / 0

05.03.2019, 14:10

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782517

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

mayton,
Мы один столбец матрицы рассматриваем. Когда N=1 - очевидно логарифм.
Я ошибся в таблице
7-10 611-14 715-18(?) 8
Отношение N/M, сдается мне, должно к гамма-распределению (N-параметр) сводиться.

...

Рейтинг:

0 / 0

05.03.2019, 14:29

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782822

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

Надо перераскладывать шары после измерений.

...

Рейтинг:

0 / 0

06.03.2019, 11:12

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782824

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

SiemarglНадо перераскладывать шары после измерений.
+1

Я вот думаю что надо в терминах нечеткой логики после измерения группы шаров добавлять им коеффициент
радиоактивности. Допустим померяли 5 штук. И каждому накинули некое вещественное число.
После нескольких итераций с разными группами и разным составом. Шар, получивший максимальный бонус - имеет
шанс быть точно радиоактивным.

...

Рейтинг:

0 / 0

06.03.2019, 11:17

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782842

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

SiemarglНадо перераскладывать шары после измерений. -1
Задача поставлена так, что нужно оптимизировать не среднее число итераций, а максимальное. Любая перераскладка их будет увеличивать.

...

Рейтинг:

0 / 0

06.03.2019, 11:44

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782884

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

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

Возможно, это даст эффект при большем количестве шаров.

...

Рейтинг:

0 / 0

06.03.2019, 12:24

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782885

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

А в общем случае, если у нас из N шаров M радиоактивных, и мы берем какие-то K шаров, то какая вероятность, что хотя бы один из выбранных K шаров радиоактивный? Понятно, что если K > N-M, то вероятность равна 1. Если M=1, то K/N. А как в общем случае?

...

Рейтинг:

0 / 0

06.03.2019, 12:25

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782887

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

06.03.2019, 12:28

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782907

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

при особом везении можно за 4 измерения оба найти, я пока на досточность даже 7 не могу придумать
хотя всё подсказывает что так оно и есть и mayton ошибается с троллингом

...

Рейтинг:

0 / 0

06.03.2019, 12:47

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782909

Gennadiy Usov

Гость

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

...

Рейтинг:

0 / 0

06.03.2019, 12:49

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782912

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

Физика-физикой но мы на ней уедем очень далеко.

...

Рейтинг:

0 / 0

06.03.2019, 12:51

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782915

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

BarloneНижняя граница - двоичный логарифм числа сочетаний из N по M (с округлением вверх). Это неплохое приближение, но нужна какая-то поправка. В случае 2 из 11 по оценке получается 6, а реально 7.

...

Рейтинг:

0 / 0

06.03.2019, 12:53

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782920

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

06.03.2019, 12:58

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782924

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

BarloneSiemarglБез перераскладки правильный ответ 7, а вот можно ли его уменьшить перекладкой - лень придумывать )
Возможно, это даст эффект при большем количестве шаров.Нижняя граница - двоичный логарифм числа сочетаний из N по M (с округлением вверх).
Неправильная формула. Выше 21824574 решение 2 из 14 за 7 замеров, а по формуле 8.

ИМХО формула N/2 с округлением вверх.

...

Рейтинг:

0 / 0

06.03.2019, 12:59

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782940

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

естественно, второй вариант, что там нету радиоактивных отбрасываем как оптимистичный

...

Рейтинг:

0 / 0

06.03.2019, 13:21

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782947

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Для 8:7 наихудший вариант по одному в каждой группе, тогда 2 замера этих групп чтобы убедиться что в каждой по одному, затем бинарный поиск в каждой: log2(N) или по 3 замера. Итого 8 замеров.

...

Рейтинг:

0 / 0

06.03.2019, 13:27

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782949

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Dima TBarloneНижняя граница - двоичный логарифм числа сочетаний из N по M (с округлением вверх).
Неправильная формула. Выше 21824574 решение 2 из 14 за 7 замеров, а по формуле 8.

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

...

Рейтинг:

0 / 0

06.03.2019, 13:29

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782960

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

kealon(Ruslan)в каком плане "нижняя граница"?В плане "необходимое число измерений не меньше, чем..."

...

Рейтинг:

0 / 0

06.03.2019, 13:33

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782964

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

BarloneDima Tпропущено...

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

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

PS Я не считал, просто заметил что log2(91) = log2(105)

...

Рейтинг:

0 / 0

06.03.2019, 13:37

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782972

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Dima T, так это нижняя граница.

...

Рейтинг:

0 / 0

06.03.2019, 13:46

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782974

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

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

...

Рейтинг:

0 / 0

06.03.2019, 13:47

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782977

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

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

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

...

Рейтинг:

0 / 0

06.03.2019, 13:52

| Ответить | Цитировать | Написать

Пятничный треугольник

#39782997

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Меня терзают смутные сомнения. Если заменить шары на биты. Типа радиоактивные - это первёрнутые
тогда поиск шара очень похож на вычисление и проверку Кода Хемминга.

...

Рейтинг:

0 / 0

06.03.2019, 14:18

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783031

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Соколинский БорисBarloneНижняя граница - двоичный логарифм числа сочетаний из N по M (с округлением вверх). Это неплохое приближение, но нужна какая-то поправка. В случае 2 из 11 по оценке получается 6, а реально 7.Да, поправки возникают из-за невозможности поделить варианты ровно пополам. Например, 2 из 6 - 15 вариантов. Но мы не можем поделить их на 8 + 7 вариантов. Меряем 2 шара и делим на 9 вариантов если результат положительный + 6 вариантов если результат отрицательный. На 9 вариантов уже нужно 4 измерения.

...

Рейтинг:

0 / 0

06.03.2019, 15:30

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783130

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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

мои ключевые пороги для 2-х шаров - это когда одна из 2-х слагаемых достигает 2^x
Что не так?

...

Рейтинг:

0 / 0

06.03.2019, 17:08

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783140

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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

По тем же сображениям для 16 тоже 7 ...

...

Рейтинг:

0 / 0

06.03.2019, 17:24

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783142

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

exp98Итого 1 +2*3=7 сравнений
Откуда 1?
Две кучки: 7 и 8. В каждой может быть как по одному, так и два в одной. Проверять надо обе, т.е. 2 +2*3=8

...

Рейтинг:

0 / 0

06.03.2019, 17:29

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783155

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Dima T, то, что надо! Признаюсь, был в плену иллюзий.

...

Рейтинг:

0 / 0

06.03.2019, 17:48

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783159

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

BarloneДа, поправки возникают из-за невозможности поделить варианты ровно пополам. Нет, эти поправки уже учтены при округлении логарифма. Нужна поправка в его аргументе.

...

Рейтинг:

0 / 0

06.03.2019, 17:54

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783164

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Типа log(x+1) ?

...

Рейтинг:

0 / 0

06.03.2019, 18:12

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783166

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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мя .... вот непонятно, обнаружениями или исправленями (ставлю на исправления).

...

Рейтинг:

0 / 0

06.03.2019, 18:14

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783178

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

maytonТипа log(x+1) ? Нет.
Когда N = 2 ^к формула вроде как точная. Поправка должна учитывать некратность аргумента.

...

Рейтинг:

0 / 0

06.03.2019, 18:43

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783183

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

exp98, первое моё наивное решение содержало матрицу шаров типа 3х5
где я должен бы прикладывать измеритель к столбцам и строкам.
Неоптимально. Но очень похоже на выявление ошибок четности
в старых системах связи. Матричное кодирование типа.
Отсюда пошла и мысль о Хемминге как о более математически
верном пути.

...

Рейтинг:

0 / 0

06.03.2019, 18:53

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783189

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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

С другой стороны, есть задачи типа о выявлении лжеца, там больше самокоррекция напрашивается. Во всяк было что-то похожее на форуме в 12-13 г. Но загвоздка в том, какой код и с какими параметрами.

...

Рейтинг:

0 / 0

06.03.2019, 19:14

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783194

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

По повод скриншота который я привел для 14 шаров. Я не удержался и заглянул вконец.
Пишут что 7 шагов достаточно. Это я не ради троллинга. А просто пишу видя что
интерес угас.

...

Рейтинг:

0 / 0

06.03.2019, 19:30

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783195

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

ИМХО mayton напутал и заставил искать подвох там где его нет, т.е. вместо нездорового числа 14 21824356 , которое решается за 7 измерений 21824574 вопреки общим оценкам, назвал число 15 где все банально и прозрачно.

...

Рейтинг:

0 / 0

06.03.2019, 19:30

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783202

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

...

Рейтинг:

0 / 0

06.03.2019, 19:45

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783212

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Я свожу к случаям 2-х мн-в и в каждом по 1метке. Каждая метка тогда стандартно находится делением/2, или даже можно сразу формулой. Поэтому я думаю, что общая формула д.б. 2-х ступенчатой, т.е. с 2-мя логарифмами.
Но разбиение пополам есть редко, а бОльшее слагаемое можно менять в больших пределах [2^k; 2*2^k), чем меньшее слагаемое. Тогда при подборе слагаемых результат для меньшего слаг-го меняется чаще, т.к. степень для него м.б. меньше. Поэтому мне видится 2-х ступенчатость общей суммы.
Это так, общие соображения.

...

Рейтинг:

0 / 0

06.03.2019, 19:58

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783223

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

exp98, проблема в том что формулы заточены на поиск одного [шара], а на два нет классических алгоритмов.

...

Рейтинг:

0 / 0

06.03.2019, 20:29

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783225

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

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

Вообще наверное суть не в этом.
Может в этом есть верх троллинга над студентами: найди подвох там где его нет. Сложно признать что подвоха нет если ты участник олимпиад и привык искать (и находить) подвох.

...

Рейтинг:

0 / 0

06.03.2019, 20:34

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783227

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Кажется, найти 2 из 15 таки можно за 7 измерений.

...

Рейтинг:

0 / 0

06.03.2019, 20:40

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783230

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

BarloneКажется, найти 2 из 15 таки можно за 7 измерений.
Можно за одно 21823737 , но не всегда. Решение огласи

...

Рейтинг:

0 / 0

06.03.2019, 20:43

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783234

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Dima TBarloneКажется, найти 2 из 15 таки можно за 7 измерений.
Можно за одно 21823737 , но не всегда. Решение огласиНачинается с проверки первых пяти шаров. Если там пусто, то из оставшихся 10 можно найти два за 6 проверок.
Если не пусто, меряем например 1,2,15. Каждый следующий шаг зависит от предшествующих результатов. Получается много веток. Я просто выписал все возможные варианты пар, и каждым измерением делил их на две равные части.

...

Рейтинг:

0 / 0

06.03.2019, 20:57

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783239

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

06.03.2019, 21:22

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783272

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

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

полная проверка алгоритма 21824574

Код: pascal

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;

...

Рейтинг:

0 / 0

06.03.2019, 22:39

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783304

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

У нас осталось 60 вариантов пар, в которых присутствует хотя бы один из шаров 1-5.
Теперь проверяем 1,2,15. При положительном результате проверяем 1 и 6, иначе 3, 6 и 7.
Получилось 4 ветки, в каждую попадают по 15 вариантов пар.
В каждой за 4 проверки можно выбрать одну правильную. Сейчас все распишу.

...

Рейтинг:

0 / 0

07.03.2019, 06:34

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783305

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Первый случай. check(1,2,15)=true, check(1,6)=true
Проверяем 8-15

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.

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. Сверху + снизу -. Дальше вроде понятно.

...

Рейтинг:

0 / 0

07.03.2019, 06:35

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783306

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Второй случай. check(1,2,15)=true, check(1,6)=false
Проверяем 3,4,5,7,8,9,10,11

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.

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. Сверху + снизу -. Дальше понятно.

...

Рейтинг:

0 / 0

07.03.2019, 06:36

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783307

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Третий случай. check(1,2,15)=false, check(3,6,7)=true
Проверяем 7-14

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.

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. Сверху + снизу -. Дальше понятно.

...

Рейтинг:

0 / 0

07.03.2019, 06:36

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783308

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Последний случай. check(1,2,15)=false, check(3,6,7)=false
Проверяем 4

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

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

...

Рейтинг:

0 / 0

07.03.2019, 06:37

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783310

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Ну вот, в самом конце опечатка. check(4) должно быть вместо check(7,8,9,10,11,12,13,14)

...

Рейтинг:

0 / 0

07.03.2019, 06:39

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783340

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

BarloneВторой случай. check(1,2,15)=true, check(1,6)=false
Проверяем 3,4,5,7,8,9,10,11

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.

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.

...

Рейтинг:

0 / 0

07.03.2019, 09:00

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783345

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

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

В 7 замеров не уложился.

...

Рейтинг:

0 / 0

07.03.2019, 09:12

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783349

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Dima TBarloneВторой случай. check(1,2,15)=true, check(1,6)=false
Проверяем 3,4,5,7,8,9,10,11

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.

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

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.

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 шага делением пополам.

...

Рейтинг:

0 / 0

07.03.2019, 09:28

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783353

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

в третьем варианте кажется тоже накосячил

...

Рейтинг:

0 / 0

07.03.2019, 09:33

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783358

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

BarloneDima Tпропущено...

Еще возможно 15 и один из 3,4,5.
Упс, косяк, исправляем... check на самом другой, запутался своих в пометках.
Проверяем 12,13,14,15
Так 7 хватает

...

Рейтинг:

0 / 0

07.03.2019, 09:38

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783359

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Barloneв третьем варианте кажется тоже накосячил
Давай правильный. Я до него еще не добрался.

PS Как ты это изобрел? У меня от проверки мозг закипает )))

...

Рейтинг:

0 / 0

07.03.2019, 09:40

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783360

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

BarloneТретий случай. check(1,2,15)=false, check(3,6,7)=true
Проверяем 7-14

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.

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         |

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.

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)

слева отрицательный результат, справа положительный

...

Рейтинг:

0 / 0

07.03.2019, 09:41

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783364

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Dima TPS Как ты это изобрел? У меня от проверки мозг закипает )))Так выписывал все возможные пары и подбирал проверки, делящие их пополам, дальше по рекурсии каждую половину. Иногда получается, что пополам никак не хочет делиться, и приходится вернуться назад и попробовать поделить по другому на более раннем шаге :)

...

Рейтинг:

0 / 0

07.03.2019, 09:45

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783369

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

BarloneТак выписывал все возможные пары и подбирал проверки, делящие их пополам, дальше по рекурсии каждую половину. Иногда получается, что пополам никак не хочет делиться, и приходится вернуться назад и попробовать поделить по другому на более раннем шаге :)Кстати, почти готовый алгоритм для автоматической генерации 21826770

...

Рейтинг:

0 / 0

07.03.2019, 09:51

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783393

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Соколинский Борисmayton,
Мы один столбец матрицы рассматриваем. Когда N=1 - очевидно логарифм.
Я ошибся в таблице
7-10 611-14 715-18(?) 8
Отношение N/M, сдается мне, должно к гамма-распределению (N-параметр) сводиться.Ну для 7 то точно достаточно 5 тестов. Для 15 вроде после исправлений нормально за 7 шагов получается.

...

Рейтинг:

0 / 0

07.03.2019, 10:33

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783401

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

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

...

Рейтинг:

0 / 0

07.03.2019, 10:40

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783408

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Похоже работает твой алгоритм за 7 замеров, не нашел больше косяков.

...

Рейтинг:

0 / 0

07.03.2019, 10:48

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783417

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Barlone,

непонятно только как его масштабировать на общий случай

...

Рейтинг:

0 / 0

07.03.2019, 11:03

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783448

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Хм... Дельфи с формочками.

...

Рейтинг:

0 / 0

07.03.2019, 11:38

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783485

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

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

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

...

Рейтинг:

0 / 0

07.03.2019, 12:27

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783529

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Aleksandr SharahovBarloneпропущено...
Я кстати начал с того, что пытался доказать невозможность. А получилось вот так.

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

NC(2;N)steps3324635104615 5 7215828 6 9366104561155 7 12667137871491715105716120 8
Вот такая табличка пока. Для 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 измерения их не разделить.

...

Рейтинг:

0 / 0

07.03.2019, 13:24

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783530

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

maytonХм... Дельфи с формочками.

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

Дерево проверок для алгоритма Barlone 2 из 15.
1. Если после группы стоят восклицательные знаки,
то их количество точно равно количеству звенящих шаров.
2. Если после группы стоит число в скобках,
то это число точно равно максимальному количеству проверок.

Код: pascal

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.

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)

...

Рейтинг:

0 / 0

07.03.2019, 13:30

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783531

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

07.03.2019, 13:32

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783532

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Переходим к 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.
При другом числе шаров для первого измерения в одной из веток получим еще больше вариантов.

...

Рейтинг:

0 / 0

07.03.2019, 13:37

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783535

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

Barlone,

спасибо

...

Рейтинг:

0 / 0

07.03.2019, 13:41

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783536

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Dima TА как же формула?
BarloneНижняя граница - двоичный логарифм числа сочетаний из N по M (с округлением вверх).
Так нижняя же, при некоторых значениях N недостижимая (дважды уже повторял). В чем вообще ее смысл - если нашли алгоритм с таким числом шагов, то быстрее точно не получится. А если не нашли - то надо либо искать дальше, либо пытаться доказать, что это невозможно.

...

Рейтинг:

0 / 0

07.03.2019, 13:42

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783546

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Вот примерно с такого же я пытался начать доказывать, что 2 из 15 за 7 шагов нельзя, но С(2;15) - С(2;10) = 60, и эти 60 за 6 шагов получилось поделить.

...

Рейтинг:

0 / 0

07.03.2019, 13:52

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783549

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Barlone,
доказать возможность гораздо легче, чем невозможность - достаточно пример
во втором же случае неудачные примеры доказательством не являются, если конечно речь не о доказательстве какого-то конкретного алгоритма, а у нас его пока нету

например, до прошлого века вообще считали, что невозможно умножать быстрее чем O(N^2)

...

Рейтинг:

0 / 0

07.03.2019, 13:55

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783560

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

например, до прошлого века вообще считали, что невозможно умножать быстрее чем O(N^2)То есть мое доказательство 21827278 вас не убедило?

...

Рейтинг:

0 / 0

07.03.2019, 14:14

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783565

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

я так же могу доказать что "проверкой одного" в общем случае нужно провести (N-K) замеров

...

Рейтинг:

0 / 0

07.03.2019, 14:23

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783571

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

kealon(Ruslan), ну тут то количество возможных алгоритмов конечно - 2 ^N вариантов одного теста (2 ^N -2 если выкинуть явно бессмысленные варианты проверять 0 шаров или сразу все шары).

...

Рейтинг:

0 / 0

07.03.2019, 14:33

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783591

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

07.03.2019, 15:08

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783592

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Barlone,
опечатался
С(16, 2) = 120 , log2(120) = 6,90689059560852 ->7

...

Рейтинг:

0 / 0

07.03.2019, 15:09

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783597

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

Barlone,

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

...

Рейтинг:

0 / 0

07.03.2019, 15:14

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783607

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

07.03.2019, 15:30

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783620

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Aleksandr SharahovBarlone,

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

...

Рейтинг:

0 / 0

07.03.2019, 15:41

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783623

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

...

Рейтинг:

0 / 0

07.03.2019, 15:45

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783628

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

А насчет "пополам" - вот приведенный здесь алгоритм поиска 2 из 15 на первом шаге проверяя пять шаров, делит 105 вариантов на 60+45. Если проверять четыре шара, можно поделить на 50+55. Казалось бы, ближе к "пополам", но нет, эти 55 вариантов (а это найти 2 из 11) за 6 шагов не разделить.

...

Рейтинг:

0 / 0

07.03.2019, 15:50

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783633

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Dima TДля 14 шаров предлагали вариант с первым делением 4,4,4,2 21824574 Так это 3 проверки, после них мы уже как-то разделили все возможные варианты пар (91) на 8 кучек. Получилось достаточно хорошо, в каждой кучке не больше 16 вариантов, чтобы за 4 оставшихся проверки найти единственный.

...

Рейтинг:

0 / 0

07.03.2019, 15:57

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783634

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

Barlone,

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

...

Рейтинг:

0 / 0

07.03.2019, 15:57

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783637

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

Aleksandr SharahovBarlone,

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

21827486

...

Рейтинг:

0 / 0

07.03.2019, 15:59

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783639

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Aleksandr SharahovBarlone,

я как раз об этомО чем конкретно?

...

Рейтинг:

0 / 0

07.03.2019, 15:59

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783641

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

А. Ну да, это же понятно, необязательно точно пополам, но каждая часть не должна превосходить соответствующую степень двойки.

...

Рейтинг:

0 / 0

07.03.2019, 16:01

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783664

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

BarloneAleksandr SharahovBarlone,

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

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

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

...

Рейтинг:

0 / 0

07.03.2019, 16:53

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783709

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

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

путь функция откусывания 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

...

Рейтинг:

0 / 0

07.03.2019, 18:05

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783711

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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

Получили 2 ур-ния с 2-мя неизвечстными. Может они и тавтология, я не пробовал.

...

Рейтинг:

0 / 0

07.03.2019, 18:06

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783712

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Тут, кстати, 3-й угол считать необязательно,т.к. сумма 3-х=365град)
да, выше m1= АМ, m2=ВМ

...

Рейтинг:

0 / 0

07.03.2019, 18:11

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783715

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Трехмедианная задача - прекрасна. В ней что-то есть от начертательных
задач где есть циркуль и линейка и больше ничего.

...

Рейтинг:

0 / 0

07.03.2019, 18:18

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783717

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

mayton, так её надо решить циркулем? "сомневаюсь я"(С)

...

Рейтинг:

0 / 0

07.03.2019, 18:23

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783720

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Нет конешно. Не надо. Я просто подчеркиваю ее простоту и в то-же время подкапотную глубину постановки.

...

Рейтинг:

0 / 0

07.03.2019, 18:28

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783738

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

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

...

Рейтинг:

0 / 0

07.03.2019, 19:16

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783743

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

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

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

Да, делит.
Но множества-то разные.
Могут содержать шары:
- ровно 2,
- ровно 1,
- ровно 0,
- от 1 до 2,
- от 0 до 1,
- от 0 до 2.
Почему они обязаны быть равными по размеру?

...

Рейтинг:

0 / 0

07.03.2019, 19:43

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783749

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Aleksandr SharahovДа, делит.
Но множества-то разные.
Могут содержать шары:
- ровно 2,
- ровно 1,
- ровно 0,
- от 1 до 2,
- от 0 до 1,
- от 0 до 2.
Почему они обязаны быть равными по размеру?Не о тех множествах речь была.

...

Рейтинг:

0 / 0

07.03.2019, 20:09

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783753

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Barlone, миль пардон, а о каких тогда?

...

Рейтинг:

0 / 0

07.03.2019, 20:30

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783755

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

В алгоритм 15 не вникал. Но хочу похвалить Барлона за вдумчивость, к-рую лично я упустил. Если правильно понимаю, то среди прочего в методе есть идея: после первого разбиения на 2 мн-ва (а наверное и в далнейшем тоже) не обязательно безусловно проводить 2 проверки, как я к примеру. После поверки одного мн-ва принимается решение проверять второе или дробить его на части и уж потом ....
Я правильно понял этот приём?

...

Рейтинг:

0 / 0

07.03.2019, 20:36

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783761

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

А моя нечеткая логика? Не взлетит?

...

Рейтинг:

0 / 0

07.03.2019, 20:50

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783766

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

неч.логика для оценочной формулы или что иное?
Для оценки я бы подумал (не в смысле буквально думать).

...

Рейтинг:

0 / 0

07.03.2019, 21:10

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783767

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

Вот я и думаю. Нечётким зрением посмотреть на шары. Только не на 14 шаров. А на 14 тысяч
например. Как-то так.

...

Рейтинг:

0 / 0

07.03.2019, 21:14

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783834

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

Перечитал 21827271 и 21827278

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

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

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

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

Удобно сначала построить последовательности проверок для меньших
количеств шаров. Эти построения можно использовать, если окажется,
что это множество ни разу не проверялось и оба шара лежат там.

...

Рейтинг:

0 / 0

08.03.2019, 11:28

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783888

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

08.03.2019, 16:51

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783891

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Может для общего языка ссылаться на случаи согласно типовой нумерации.
типа такого:

Код: xml

1.
2.
3.
4.
5.
6.
7.
8.
9.

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.

...

Рейтинг:

0 / 0

08.03.2019, 17:01

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783893

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

08.03.2019, 17:13

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783900

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

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

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

Рассмотрим множество всевозможных пар шаров мощностью C(2,N).
Нас интерересует только один элемент этого множества - пара звенящих шаров.
Каждый тест, возвращая булевский результат, тем самым делит множество на 2 части.
И нет никакого способа найти нашу пару быстрее log(C(2,N)) ,
т.к. мы будем вредить, перенумеровывая шары перед каждым тестом,
но не нарушая результатов предыдущих тестов.

...

Рейтинг:

0 / 0

08.03.2019, 17:50

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783903

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

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

В данном случае мы пытаемся только оценить количество шагов, а не построить алгоритм.
Поэтому анализ неконструктивный.

...

Рейтинг:

0 / 0

08.03.2019, 18:11

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783906

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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

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

...

Рейтинг:

0 / 0

08.03.2019, 18:19

| Ответить | Цитировать | Написать

Пятничный треугольник

#39783933

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

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

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

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

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

З.Ы. В этой задаче такие ассоциации мне только мешают )

...

Рейтинг:

0 / 0

08.03.2019, 20:01

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784001

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

Полная проверка алгоритма Barlone (2 из 15) на Delphi без формочек:

Код: pascal

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;

...

Рейтинг:

0 / 0

09.03.2019, 00:48

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784010

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

По похожему принципу решаются задачи на взвешивания типа "найти две фальшивых монеты из 13", только делить надо на 3 части.
_{(известно что фальшивые монеты одинакового веса и тяжелее настоящих, у нас есть рычажные весы без гирь...)}

...

Рейтинг:

0 / 0

09.03.2019, 06:42

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784059

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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

Э-э, вопрос был к дельфам: а) где ж её взять или хотя бы интерпретатор;
б) недопонял это

Код: plaintext

  if IsWhite('12f',white,calls).......

и подобное.
Это повторная проверка шаров 1 и 2? для чего? ведь перед этим

Код: plaintext

  IsWhite('12345',......

Ведь судя по самой последней проверке

Код: plaintext

1.
2.
3.
4.

            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() проверяет отсутствие. Или наоборот?

...

Рейтинг:

0 / 0

09.03.2019, 14:17

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784066

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

exp98Barlone, и так же тухлые яйца,помидоры и т.п., только их не взвешивают, а вонь проверяют))

Э-э, вопрос был к дельфам: а) где ж её взять или хотя бы интерпретатор;
б) недопонял это

Код: plaintext

  if IsWhite('12f',white,calls).......

и подобное.
Это повторная проверка шаров 1 и 2? для чего? ведь перед этим

Код: plaintext

  IsWhite('12345',......

Ведь судя по самой последней проверке

Код: plaintext

1.
2.
3.
4.

            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() проверяет наличие светимости

...

Рейтинг:

0 / 0

09.03.2019, 14:45

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784071

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

интересно, что тот же алгоритм с очевидными изменениями
находит 2 шара из 20 за 8 проверок, а вот что делать дальше неясно.

...

Рейтинг:

0 / 0

09.03.2019, 15:26

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784072

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Так получилось, что сам только что заглянул, поэтому спрашиваю.
Непонятна цель повторной проверки. Скорее всего просто так родилось, ну и оставили.
Умозрительно кажется, что

Код: plaintext

  if IsWhite('12f',white,calls).......

можно заменить на проверку только "f".

...

Рейтинг:

0 / 0

09.03.2019, 15:35

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784073

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Aleksandr Sharahovдальше неясно. Дальше переходить на полный бэктрекинг и генерацию подмножеств 2^21 ...
Вообще, стоит покопаться в работах по обнаружению ошибок.

...

Рейтинг:

0 / 0

09.03.2019, 15:40

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784074

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

exp98Так получилось, что сам только что заглянул, поэтому спрашиваю.
Непонятна цель повторной проверки. Скорее всего просто так родилось, ну и оставили.
Умозрительно кажется, что

Код: plaintext

  if IsWhite('12f',white,calls).......

можно заменить на проверку только "f".

Нет, нельзя. Смысл изменится.
Там каждая циферка играет свою роль.

...

Рейтинг:

0 / 0

09.03.2019, 15:41

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784075

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

09.03.2019, 15:49

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784076

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

У меня сведения старые, по автоматическому синтезу алгоритмов можно ещё почитать. У нас давно ещё направление развивал Лупанов ОБ., ну и другие менее тогда известные.

...

Рейтинг:

0 / 0

09.03.2019, 15:59

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784077

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

09.03.2019, 16:09

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784079

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

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

тут надо узнать как можно больше про пару 12, а f подмешиваем, чтобы использовать знание о нем ниже
логика такая: если 12f не пахнут, то 12 не пахнут, и значит пахнут 345
а в нижних else-ветках мы уже знаем, что и f не пахнет

...

Рейтинг:

0 / 0

09.03.2019, 16:10

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784142

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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

Тогда "все сходится, ребёночек не наш"(с).
Спасибо за разъяснения.

...

Рейтинг:

0 / 0

09.03.2019, 20:40

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784143

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

09.03.2019, 20:43

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784173

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

09.03.2019, 22:02

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784175

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

Barlone прав, число возможных расстановок C(k,N) а значит минимально достаточно log2(C(k,N)) бит что бы описать любой из вариантов расстановки

...

Рейтинг:

0 / 0

09.03.2019, 22:05

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784187

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

вселенная с этим не согласна

...

Рейтинг:

0 / 0

09.03.2019, 23:09

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784239

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

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

...

Рейтинг:

0 / 0

10.03.2019, 11:05

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784248

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Barlonekealon(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

...

Рейтинг:

0 / 0

10.03.2019, 12:40

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784249

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Barlone,

с 4 довольно тривиально, а вот с 5 я кое как придумал

...

Рейтинг:

0 / 0

10.03.2019, 12:41

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784250

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

т.к. C(12,2) = 66 > 64

...

Рейтинг:

0 / 0

10.03.2019, 12:45

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784261

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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

П.С. ссылка хорошая, кто-то ею уже попользовался))

...

Рейтинг:

0 / 0

10.03.2019, 13:39

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784263

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

10.03.2019, 13:47

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784282

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

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

Так же )

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

...

Рейтинг:

0 / 0

10.03.2019, 17:19

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784306

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Aleksandr Sharahovexp98пропущено...
Как осуществлять поиск 1 значения в массиве знают все. А вот как быстро искать 2 значения?

Так же )

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

Верно?

...

Рейтинг:

0 / 0

10.03.2019, 21:02

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784307

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

Например, надо найти 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 проверок.

...

Рейтинг:

0 / 0

10.03.2019, 21:14

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784308

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

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 лишнюю проверку

...

Рейтинг:

0 / 0

10.03.2019, 21:23

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784309

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

Относительно средней оценки все выглядит так,
будто она мало зависит от алгоритма.
Плюс-минус одна проверка не имеет значения,
если их десятки.

...

Рейтинг:

0 / 0

10.03.2019, 21:31

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784328

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

ну вот, пришёл Александ и всё опошлил :-)

...

Рейтинг:

0 / 0

11.03.2019, 06:33

| Ответить | Цитировать | Написать

Пятничный треугольник

#39784385

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

вариант с первоначальным "откусыванием" 5 (без трививальной части )

Код: pascal

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.

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.

...

Рейтинг:

0 / 0

11.03.2019, 10:51

| Ответить | Цитировать | Написать

188 сообщений из 188, показаны все 8 страниц

все

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничный треугольник

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?all=1&fid=16&tid=1339982]:	0ms
get settings:	11ms
get forum list:	14ms
check forum access:	4ms
check topic access:	4ms
track hit:	176ms
get topic data:	12ms
get forum data:	3ms
get page messages:	181ms
get tp. blocked users:	2ms
others:	14ms

total:	421ms