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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Откуда: Москва
Сообщений: 9979
Barlone
Да, поправки возникают из-за невозможности поделить варианты ровно пополам.
Нет, эти поправки уже учтены при округлении логарифма. Нужна поправка в его аргументе.
6 мар 19, 17:54    [21826627]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3] 4 5 6 7 8   вперед  Ctrl      все
Все форумы / Программирование Ответить