powered by simpleCommunicator - 2.0.50     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничный треугольник
25 сообщений из 188, страница 2 из 8
Пятничный треугольник
    #39781601
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
max.
C одним шаром просто "олимпийская система": после первого измерения отсеивается 7/8, после второго - 4 и.т.д.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39781612
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЕсли-бы шар был 1 тогда наверное 6 измерений.
Если один, то бинарный поиск в чистом виде - 4 измерения. С двумя шарами сложнее.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #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
Пятничный треугольник
    #39781624
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovВ скобках - количество измерений
7 на 8 (1)

Это (2)
8 получается.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39781633
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Соколинский БорисGennadiy UsovВ скобках - количество измерений
7 на 8 (1)

Это (2)
8 получается.Нет, это (1).
Ведь смотрим 7, а в 8 остаётся то, что не попало в 7
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39781640
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov,
У нас вроде как счетчик качественный, т.е. не отличает один шар положительный в образце или два.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39781681
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Соколинский БорисGennadiy Usov,
У нас вроде как счетчик качественный, т.е. не отличает один шар положительный в образце или два.
Согласно условию задачи можно измерять любое количество шаров.

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

В результате становится известно, сколько радиактивных шаров оказалось в каждой из двух групп:
либо 0, либо 1, либо 2 шара.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39781798
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЛадно еще задачка. Оставляю вечно себе на десер.

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

Сколько минимум измерений нужно сделать чтоб найти эти 2 шара.7
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39781842
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovВ результате становится известно, сколько радиактивных шаров оказалось в каждой из двух групп:либо 0, либо 1, либо 2 шара. Насколько я понял условие - прибор просто детектирует наличие радиации, а сколько таких шаров в группе (1 или 2) он определить не может.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39781926
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот еще одна постановка. Неважно что шаров 14. Принцип тот-же.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39781980
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
тоже 7
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39782046
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
У меня 8 получается.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39782072
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Предварительные леммы. 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
Пятничный треугольник
    #39782084
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Соколинский БорисСобственно алгоритм.
(1-4)
(5-8)
(9-12)
A. Если "звонят" две группы, находим по одному шару в каждой (С2)
Всего 7.
Не хватает (13-15), это будет 8-я проверка.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39782102
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Соколинский БорисБ. Если звонит одна группа (условно первая)
(13 14)
Б1. Звонит - находим один шар в первой группе (С2) и один в последней (С1) Всего 7.
Б2. Не звонит - находим два шара в первой группе (С3). Всего 7.
понял где последние, только в исходной задаче их было 15, поэтому в последней тоже С2, т.е. Б1 итого 8.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39782108
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T,

первый шар находим половинным делением - 4 проверки достаточно
второй шар находим проверяя противоположную от ветки первого прохода, их всего 3 уровня
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39782120
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T,

хотя нет, всё равно 8 нужно
...
Рейтинг: 0 / 0
Пятничный треугольник
    #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
Пятничный треугольник
    #39782436
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
16 удачнее делится на 2. Хотя здесь-бы подошла дюжина или основа Вавилонской системы счисления 60 = 1*2*3*4*5
ибо удобнее делить по всякому.

Я думаю что 14 и 15 авторы ввели исключительно из троллига.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39782439
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тьфу. 60 = 1*2*2*3*5
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39782492
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Как-то я начал слегка сомневаться в правильности алгоритма - странная зависимость от N получается (случай двух шаров)
4 35 46 57-8 69-14 715-16 8 16+ 9
По идее, должно быть нечто вроде логарифма. но точка 9-14 выпадает.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39782502
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тут матрица. M известных шаров на N радиоактивных.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39782517
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
Мы один столбец матрицы рассматриваем. Когда N=1 - очевидно логарифм.
Я ошибся в таблице
7-10 611-14 715-18(?) 8
Отношение N/M, сдается мне, должно к гамма-распределению (N-параметр) сводиться.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39782822
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Надо перераскладывать шары после измерений.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39782824
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SiemarglНадо перераскладывать шары после измерений.
+1

Я вот думаю что надо в терминах нечеткой логики после измерения группы шаров добавлять им коеффициент
радиоактивности. Допустим померяли 5 штук. И каждому накинули некое вещественное число.
После нескольких итераций с разными группами и разным составом. Шар, получивший максимальный бонус - имеет
шанс быть точно радиоактивным.
...
Рейтинг: 0 / 0
25 сообщений из 188, страница 2 из 8
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничный треугольник
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]