Не скажу на счёт минимальных взвешиваний, но минимальное количество взвешиваний возможно только при условии что фальшивые монеты выпадут в первом же взвешивании.
1) за 2
2) за 2

>>1083160
>кажу на счёт минимальных взвешиваний, но минимальное количество взвешиваний возможно только при условии что фальшивые монеты выпадут в первом же взвешивании.
>1) за 2
>2) за 2
Ты не понял. Мне нужен не минимальный результат при УДАЧНОМ СТЕЧЕНИИ ОБСТОЯТЕЛЬСТВ. А грубо говоря я хочу увидеть алгоритм, который при любом входном наборе переменных, будет за минимальное число взвешиваний СТАБИЛЬНО находить нужную монетку.

Понимаешь? Если ты начнешь взвешивать каждую монетку по отдельности, и тебе выпадет фальшивая на третьем взвешивании, это не значит что твой алгоритм находит фальшивую за 3 взвешивания. Это всё равно значит, что он находит её за 79 - столько нужно в худшем случае. Это и будет сложностью в этой ситуации.

>>1083145 (OP)
1) 5 в лучшем случае, 6 в худшем
2) за 4

>>1083179
++

>>1083179
>>1083180
Хотелось бы пояснения ваши увидеть. Интересно же не цифру, а что и как вы взвешивали.

>>1083185
В первом случае
1. 40 | 40
2. 20 | 20
3. 10 | 10
4. 5 | 5
5. 2 | 2 если равенство - то монетка которую не взвешивали - фальшивая, если нет то ещё одно дополнительное взвешивание
6. 1 | 1

Во втором случае (пока писал, понял что в лучшем случае даже за 3 получается)
1. 6 золотых + 6 серебряных | 6 золотых + 6 серебряных
2. в перевешивающей группе 3 серебряные | 3 серебряные
если есть неравенство то берём перевешивающие 3 монет и последнее взвешивание 3. 1 | 1
если нет неравенства берём золотые монеты из другой группы
3 золотые монеты | 3 золотые монеты
4. 1 золотая | 1 золотая

>>1083196
>1 задача

У тебя не оптимально решена, хотя идея ок, но что если я скажу тебе, что могу ВСЕГДА ЗА МЕНЬШЕЕ КОЛИЧЕСТВО ВЗВЕШИВАНИЙ чем у тебя найти ту самую фальшивую монетку среди 80.

>2 задача.
>1. 6 золотых + 6 серебряных | 6 золотых + 6 серебряных
Поясни вот этот мув.
По условию задачи написано же, что:
>Настоящие золотые монеты весят одинаково; настоящие серебряные тоже, но неизвестно, какие тяжелее (золотые или серебряные). Фальшивая золотая монета легче настоящих золотых, а фальшивая серебряная тяжелее серебряных.

Вот ты кладешь 6 золота и 6 серебра на одну чашу, и 6 золота и 6 серебра на вторую. Какая-то чаша перевешивает - ок, но как ты определяешь в итоге, это потому что фальшивая золотая на одной чаше легче, или потому что фальшивая серебрянная на другой чаше тяжелее? По мне так это не сработает просто.

>>1083200
>ВСЕГДА ЗА МЕНЬШЕЕ КОЛИЧЕСТВО ВЗВЕШИВАНИЙ
Хммм, ну ок я ещё подумаю. Возможно можно выбрать более подходящий делитель.

>но как ты определяешь в итоге
Ну так смотри. Из условия
>Фальшивая золотая монета легче настоящих золотых
и
>фальшивая серебряная тяжелее серебряных
у нас два есть два варианта:
либо в перевешивающей чаше находится серебряная монета, либо в перешиваемой находится золотая
начинаем с первого варианта и взвешиваем серебренные монеты в перевивающей чаше 3 | 3
если там выполняется равенство, переходим к другому варианту, и взвешиваем золотые монеты в перевешиваемой чаше

>>1083208
Понял, то есть твой алгоритм расчитан на 4 взвешивания.
>(пока писал, понял что в лучшем случае даже за 3 получается)
Всё таки надо на верочку рассчитывать, что бы всегда работало.

>>1083210
В лучшем на 3, в худшем на 4, да.

>>1083211
Есть инфа, что можно всегда за 3.

как и первую задачу

>>1083288
Ясно, предлагаю тебе постирать штаны в общем.

хули вы блять всё в цифрах пишете, относительно n никак?

>>1083309
Это элемент усложнения.

>>1083145 (OP)
>За сколько минимальных взвешиваний можно вычислить фальшивую монетку.
за три только определиться с кучей из 40 монет

40/2
20/2
10/2
5/2
2/2 или 3/2

>>1083464
з.ы. 8 действий

>>1083465
нет, на 9

>>1083471
минимум за 2

1) В лучшем за 4, в худшем за 5.

разбиваем по 14/14/14/14/14
1)14/14
2)14/14 14 от первого взвешивания остается 14
разбиваем по 3/3/3/3/2
3) 3/3
4) 3*/3
5) 1/1

>>1083562
Плохо понял тебя.

Ты сначала взвешиваешь 2 пары по 14, если там нет то взвешиваешь другие две? Так за два взвешивания ты находишь ту 14-монетную кучку, в которой находится фальшивка? Это не оптимальный алгоритм пока конечно, но ты молодец и определенно на верном пути. Ведь пока что никому в треде не удавалось сузить множество монеток до 14 после двух взвешиваний, тупо все зациклены на бинарном поиске и после двух взвешиваний имеют кучку в 20 монет.

Разбиваем на 27/27/26 и получаем в лучшем 4, а в худшем 5

>>1083581
>Разбиваем на 27/27/26
>...
>Profit
Как ты в худшем то 5 получаешь?

>>1083582
а, ну я еблан, там всегда 4 будет

79+1:
1. 2 монетки откладываем, остаётся 78, и взвешиваем первый раз - 26/26
2. К 26 монеткам добавляем 1 из первых 2х, и взвешиваем второй раз - 9/9
3. Взвешиваем 3/3
4. Взвешиваем 1/1, остаются 1+1 монетки невзвешенные (Возможен РЕЗУЛЬТАТ)
5. Взвешиваем 1/1 (Точно РЕЗУЛЬТАТ)

>>1083584
Ну да, а алгоритм не распишешь?

>>1083586
Ты тоже где-то рядом ходишь, но заем ты откладываешь две? Оптимальнее постоянного деления на два, но как-то очень костыльно.

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

>>1083589
Ребятам в треде бы пояснил.

>>1083590
ладно, специально для ребят в треде
1)
27/27/26
9/9/8
3/3/2
1/1
2)
27/27/26
9/9/9
3/3/3
1/1/1
в общем суть подхода в том, что мы можем находить в какой из трех кучек монет находится фальшивая используя одно сравнение

По какому алгоритму вы решаете? Стало интересно! Что почитать, чтобы такое решать?

>>1083591
Да, можем делить на 3 околоравные кучки, две из которых должны быть равны и взвешивать их, отсеивая тем самым 2/3 монет за 1 взвешивание.

В итоге:
2-3 монетки - одно взвешивание.
4-9 монеток - два взвешивания
10 - 27 монеток - три взвешивания
28 - 81 монеток - четыре взвешивания
82 - 243 монетки - пять.

>>1083591
А если 82 монеты?
:
1. 27/27 - 28
2. 9/9 - 10
3. 3/3 - 4
4. 2/2 - 0
5. 1/1

>>1083595
Угу, идеальным количеством монет для взвешиния будет степень числа 3. Для 81 - четыре взвешиявания, тупо деля всегда на 3 и оставляя на первом взвешивании 27 монеток, на втором 9монеток, на третьем - 3монетки, и на четвертом зная точно какая фальшивая.
Если 82 монетки, то будет одна неудобная, для которой понадобится еще 1 взвешивание.

>>1083596
Можно весы придумать прост, где три или более чаш

>>1083592
Можешь про двоичный поиск почитать для начала. И вот тебе задача сразу.

Я загадал число от 1 до 1000. Ты можешь задавать мне вопросы на которые я отвечу только да или нет. За сколько таких вот уточняющих вопросов, ты сможешь точно назвать число, которое я загадал?

>>1083601

За 11

>>1083602
Как считал, почему 11?

>>1083603

Потому что можно опираться на двоичную систему и по ней спрашивать:
Больше 512?
Больше 256?
Больше 128?
:
1. >512?
2. >256?
3. >128?
4. >64?
5. >32?
6. >16?
7. >8?
8. >4?
10. >2?
11. >1?

>>1083609
у тебя там ошибка.

>>1083603

Потому что можно опираться на двоичную систему и по ней спрашивать:
Больше 512?
Больше 256?
Больше 128?
:
1. >512?
2. >256?
3. >128?
4. >64?
5. >32?
6. >16?
7. >8?
8. >4?
9. >2?
10. >1?
11. 1?

>>1083610
Текст повредился при копировании прост, исправил.

>>1083612
Так а зачем 11 вопрос нужен? После 10 можно с уверенностью сказать уже. Если ты сократил диапазон возможных чисел до двух, то можно угадать за 1 вопрос (который у тебя десятый)

>>1083615
А утвердительный вопрос?

>>1083617
А зачем? Имея два варианта, ты за 1 вопрос можешь угадать 100%, зачем масло масленное городить? Мы же не пакеты на расстоянии передаем, после получения которого неплохо бы контрольную сумму спросить.

Вот еще доказательство альтарнативное
1000 можно представить как 11 1110 1000 в двоичной системе.
Зашифровано оно в 10 битах (больше бит нужно на числа от 1024 и больше). Стало быть всегда можно точно назвать число, если задавать вопросы вида:
первый бит равен 1?
второй бит равен 1?
...
десятый бит равен 1?

На основе да или нет составляешь своё число из бит и вуаля.

Кстати вот еще тебе интересная задача.


Допустим мы всё так же угадываем число от 1 до 1000, но теперь я могу тебе соврать 1 раз в ответе, а могу и не соврать.

Как теперь ты будешь строить свои вопросы, и сколько ты их мне задашь, что бы убедиться в том то угадаешь число?

>>1083623
После каждого вопроса можно спрашивать "Ты соврал в предыдущем ответе?"
Тогда количество вопросов возрастёт в два раза, и достигнет 20, максимум.
Но!
Если в чётном вопросе моём ты ответишь "Да", то потом можно проверочный вопрос не задавать.

>>1083627
Хороший вариант, но давай представим чо нельзя такой хитростью пользоваться:
>После каждого вопроса можно спрашивать "Ты соврал в предыдущем ответе?"

Допустим я не вру, но в процессе передачи ответа от меня к тебе, он может исказиться. (лишь 1 из всех моих ответов тебе).
То есть твой вопрос не имеет смысла теперь.

>>1083627
>Если в чётном вопросе моём ты ответишь "Да", то потом можно проверочный вопрос не задавать.
Поясни, я тупенький и не понял что это всё значит.

>>1083630
Исказиться информация может в самом начале и пойдёт каскадный сбой по всему алгоритму.
Энивэй, каждый вопрос надо дублировать.
Более сложный в реализации метод - каждые три вопроса задавать контрольный и возвращаться на три шага назад, при выявлении ошибки.

>>1083630
Также, можно задать мои 11 вопросов, включая утвердительный, и если произошла ошибка, повторить уже твои 10 вопросов.

>>1083634
>>1083635
Ничего не понял.

>>1083591
>какой из трех кучек монет находится фальшивая используя одно сравнение
херня какаято

Взвешивать надо так:
38/38 и 1/1
18/18 и 1/1
8/8 и 1/1
3/3 и 1/1
1/1 и 1

В лучше случае 2, в худшем 5 взвешиваний.

>>1083591
Ну охуеть, так давай просто сделаем весы с 80 чашами.

Сравнение трех кучек требует двух взвешиваний.

>>1083145 (OP)
1. 4
2. 3
Взвешиваем 16 монет, одинаковое количество серебрянных и золотых с обоих сторон.
Если вес равен, то виноваты монеты, не включенные во взвешивание. Если одна из чаш перетянула, то причина ибо в серебрянных монетах на этой чаше, либо в золотых на другой.
В любом исходе у нас в подозреваемых осталось 4 золотых и 4 серебрянных.
Одну монету каждого типа откладываем. Оставшиеся 3 каждого типа кладём на одну чашу, на другую такое же количество монет каждого типа, которые уже были проверены.
Если веса равны то третьим взвешиванием надо проверить одну из двух исключенных из второго взвешивания монет.
Если веса разные, то круг подозреваемых сузился до 3 золотых и 3 серебрянных монет.
Из этих 3 одну откладываем, а среди оставшихся 2 устраиваем версус.

>>1083822
ты что, аутист? ладно, походу придется объяснять для самых маленьких
есть 3 кучки 27/27/26, так? затем, мы берем и кладем на весы кучки по 27, какой результат мы можем получить? либо эти кучки весят одинаково, либо одна из кучек перевешивает, верно? надеюсь до этого момента всё понятно. затем, если кучки на весах равны, ЗНАЧИТ в этих двух кучках нет фальшивой монеты, СООТВЕТСТВЕННО фальшивая монета в третьей кучке, понимаешь? далее, в случае если кучки на весах не равны, значит какая-то из кучек будет перевешивать, и та которая перевешивает и будет кучкой в которой есть фальшивая монета. В ИТОГЕ с помощью весов С ДВУМЯ ЧАШАМИ и ОДНИМ взвешиванием мы из 80 монет оставляем только либо 27 либо 26 и далее делаем всё по точно такому же принципу.
В ИТОГЕ получаем в любом случае 4 взвешивания для нахождения фальшивой монеты.
надеюсь теперь вопросов не возникнет

>>1083848
>либо одна из кучек перевешивает
как ты определьшь в какой из них фальшивая?

>>1083873
>и та которая перевешивает
пропустил твои охуительные рассуждения, вес фальшивой монеты не известен же, лол

>>1083591
>27/27/26
предположим золотая монета в третей кучке
1. 27 | 27
дальше берёшь третью кучку и будешь либо делить по два, тогда
2. 13 | 13
3. 6 | 6
4 3 | 3
5. 1 | 1
либо по три и тогда получиться ещё дольше

вообще я чёт проиграл с этого
>27/27/26
>9/9/8
>3/3/2
> 1/1
как это у тебя за один проход меняется сразу три кучки?

>>1083884

s/золотая/фальшива

>>1083885
heap.search(фальшивая)

>>1083884
это решение первой задачи, ало

>>1083875
>в общем есть кучка монет, допустим 80 штук, 1 из них поддельная, отличается только ВЕСОМ.

>>1083820
Ебало тебе набить, штоле??
Так отчаянно тупить - это ещё ухитриться надо.
По 2 взвешивания в каждой строке!
Я 8 взвешиваний насчитал, дальше сбился, бля!
Рака яичек тебе, гандон тупой, сука!

>>1083937
>это решение первой задачи, ало
ты ебать хуйни нагородил, впрочем может потому, что ты еще пятиклашка

>>1083145 (OP)
1 Задача
79 максимум раз взвесить хватит, когда на чаше будет хоть одна поддельная то она колебнется
2 Задача
впадлу читать

>>1083969
ну ты можешь обосновать? и если я правильно понял, то ОП треда подтвердил правильность решения

>>1083989
Да, ты правильно решил. Делим на максимально приближенные друг к другу кучки, что бы две из них были равны. Взвешивая две из которых, мы всегда знаем в итоге в какой из трех фальшивка и срази отсеиваем две/трети монет за 1 взвешивание.

>>1083826
Твой первый шаг мне понятен. Он хороший и отсеивает 16 монет оставляя 8, но вот как с этими 8 дальше работать что бы уложиться в 2 взвешивания, я что-то не понял.

>>1083145 (OP)
В первом на три кучки делить лучше, чем на две. Если их 80, то 26 26 28. Взвешиваем первые две, если одна из них легче - значит в ней фальшивые. Если одинаковые - значит в третьей кучке фальшивые. И так далее.

>>1084183
Ну допустим фальшиваф в той в которой 28 монет, как ты это дальше будешь разруливать за 3 взвешивания?

>>1084198
на втором взвешивании останется 9 монет, на третьем 3, при четвертом определишь фальшивую монету.

>>1084201
>на втором взвешивании останется 9 монет
Ну я разбил 28 на 9 + 9 + 10. Выпал случай с 10 монетками, твоя теория инвалид кароче и уже поплыла.

>>1083145 (OP)
1) ceil(log3(80))
2) 2ceil(log3(12))

thread

>>1084141
>как с этими 8 дальше работать
После первого взвешивания у нас остаётся 8 кандидатов. Назовём их S0 .. S3 и G0 .. G3.
Также у нас остаётся по 8 заведомо нефальшивых монет каждого типа. Назовём их просто S и G.
Второе взвешивание:
{S0, S1, S2, G0, G1, G2} vs {S, S, S, G, G, G}
8 подозрительных монет разделились на 3 группы: 3 остались на той же чаше, 3 перенесены на противоположную, 2 мы убрали.
Мы знаем в какую сторону был перевес после первого взвешивания. Если второе взвешивание дало тот же результат, то фальшивка среди монет оставшихся на той же чаше, если противоположный - то в перенесённых, если нет перевеса - в убранных.
В 3 взвешивании проделываем тот же трюк - добавляем необходимое количество заведомо настоящих монет, чтобы образовать пары с подозрительными. Треть пар оставляем на той же чаше, треть меняем местами, треть убираем (или не убираем если пар всего 2).

>>1084599
> Мы знаем в какую сторону был перевес после первого взвешивания
Не знаем, ибо его не было, так как фальшивка была среди невзвешенных в первый раз

>>1090104
Да, это ошибка. Но не фатальная, ведь мы знаем в какую сторону отличаются от настоящих монет серебрянные и золотые фальшивки, а значит мы способны интерпретировать результат взвешивания. Если половина с подозрительными монетами перевесила, то виноваты серебрянные, если недовесила то золотые.

Первая задача - бинарный поиск

Берем и кладем по 40 монет на обе чаши, если одна чаша перевесит, то в другой одна - фальшивая. Далее делим 40 на 2 чаши по двадцать монет и таким образом взвешиваем пока не останется две монеты.
Получается, что кол-во минимальных взвешиваний - это степень двойки в равенстве 80 = 2^x, то есть 7

бинарный поиск же, элементарные задачи, в чем проблема?

>>1090516
В том, что надо не "решить", а "решить за меньшее количество взвешиваний", и в этих задачах бинарный поиск не является оптимальным решением

>>1090528
значит не бинарным, а "тринарным" тогда. Делить на 3 кучки, 2 взвешить, если они равны, то фальшивая в 3-ей, если не равны - то в одной из взвешиваемых. Найденную кучку снова делить на 3 и так далее. Суть в общем от этого не меняется. Алгоритм тот же что и при бинарном.

>>1083145 (OP)
1) 6 взвешиваний (40-20-10-6(тут дополняется одной монетой из нефальшивой кучки)-4-2)
2) 4 взвешивания (6-6(тут определяется в какой куче монет фальшифка)-4-2)

>>1090536
И все равно этот алгоритм не всегда является оптимальным по количеству взвешиваний