Имеется гирьки одинаковые по форме но попарно различные по весу.
За одну операцию можно найти средннюю по весу из 5 гирек.
За какое наименьшее число таких операций можно найти среднюю по весу из 7 гирек?
Здравствуйте, nikholas, Вы писали:
N>Имеется гирьки одинаковые по форме но попарно различные по весу. N>За одну операцию можно найти средннюю по весу из 5 гирек. N>За какое наименьшее число таких операций можно найти среднюю по весу из 7 гирек?
Здравствуйте, nikholas, Вы писали:
N>Здравствуйте, kov_serg, Вы писали:
_>>3
N>Не верю!
Тогда 7.
F функция которая возвращает медианный груз из 5 грузов,
все грузы попарно разные,
мы можем делать метки на грузах что бы их отличать
Как-то так
1. берём g1=F(первые 5) находим g1
2. берём g2=F(6-ой и первые 5 без g1) получаем g2
3. берём g3=F(7-ой и предыущую группу без g2) получаем g3
далее остаётся 4 груза назовём их r1,r2,r3,r4
4. z1=F(g1,g2,g3,r1,r2)
5. z2=F(g1,g2,g3,r1,r3) if (z1=z2) результат z2
6. z3=F(g1,g2,g3,r1,r4) if (z3=z1 или z2) результат z3
7. z4=F(g1,g2,g3,r2,r3) if (z4=z1 или z2 или z3) результат z4
1. g1 = F(первые 5). Про g1 можно утверждать, что она по весу ранжируется на 3, 4 или 5-ое место.
2. g2 = F(первые 5 — g1 + 6-ая). Про g2 можно утверждать, что она по весу ранжируется на 3, 4 или 5-ое место.
3. g3 = F(вторые 5 — g2 + 7-ая). Про g2 можно утверждать, что она по весу ранжируется на 3, 4 или 5-ое место.
G = g1, g2, g3 в отсортированной последовательности занимают места 3, 4, 5. Поэтому искомая гирька среди них.
Пусть R = r1, r2, r3, r4 — оставшиеся гирьки.
Если применить операцию к гирькам из G + любым двум из R, то результат будет в G.
Варианты:
1. r1 и r2 весят меньше/больше, чем гирьки из G. Тогда мы увидим, что три последние операции поочередно вернут все гирьки из G. Искомая гирька — на шаге 2.
2. r1 и r2 весят одна меньше, а другая больше, чем гирьки из G. Тогда мы увидим,
— либо на втором шаге результат операции не изменится и тогда искомая гирька у нас в руках.
— либо результат операции на 2-ом шаге изменится, а на 3-ем вернется обратно и тогда искомая гирька у нас в руках.
Здравствуйте, nikholas, Вы писали:
N>Здравствуйте, kov_serg, Вы писали:
_>>Тогда 7.
N>Можно и за меньшее число операций.
Точно за 5 операций можно
1. берём g1=F(первые 5) находим g1
2. берём g2=F(6-ой и первые 5 без g1) получаем g2
3. берём g3=F(7-ой и предыущую группу без g2) получаем g3
далее остаётся 4 груза назовём их r1,r2,r3,r4
4. z1=F(g1,g2,g3,r1,r2)
5. z2=F(g1,g2,g3,r3,r4) if (z1=z2) то z2
else (g1,g2,g3)-z1-z2
Здравствуйте, kov_serg, Вы писали:
_>Тогда надо всего 3+2 = 5 пераций достаточно
При такой схеме 6 надо.
1. Берем мы две гирьки из R. Мы же не знаем, как оно выпало: {r1, r2, g1, g2, g3}/{g1, g2, g3, r3, r4} или же {r1, g1, g2, g3, r2}/etc...
2. В обоих вариантах при замене гирьки на втором шаге может произойти смена результата операции. В таком сценарии понятно, что искомая гирька — это либо то, что получили на первом шаге, либо на втором.
Но пока еще нельзя различить между этими двумя гирьками.
Для этого нужна третья операция.
3. Берем еще одну гирьку и смотрим, как изменился результат:
— если это новая гирька из G, то на первом шаге у нас было что-то из {r1, r2, g1, g2, g3}/{g1, g2, g3, r3, r4}
— если это старая гирька из G, то на первом шаге у нас было что-то из {r1, g1, g2, g3, r2}/etc...
Здравствуйте, StatujaLeha, Вы писали:
SL>Здравствуйте, kov_serg, Вы писали:
_>>Тогда надо всего 3+2 = 5 пераций достаточно
SL>При такой схеме 6 надо. SL>1. Берем мы две гирьки из R. Мы же не знаем, как оно выпало: {r1, r2, g1, g2, g3}/{g1, g2, g3, r3, r4} или же {r1, g1, g2, g3, r2}/etc... SL>2. В обоих вариантах при замене гирьки на втором шаге может произойти смена результата операции. В таком сценарии понятно, что искомая гирька — это либо то, что получили на первом шаге, либо на втором. SL> Но пока еще нельзя различить между этими двумя гирьками. SL> Для этого нужна третья операция. SL>3. Берем еще одну гирьку и смотрим, как изменился результат: SL> — если это новая гирька из G, то на первом шаге у нас было что-то из {r1, r2, g1, g2, g3}/{g1, g2, g3, r3, r4} SL> — если это старая гирька из G, то на первом шаге у нас было что-то из {r1, g1, g2, g3, r2}/etc...
Вы правы
Здравствуйте, kov_serg, Вы писали:
_>Точно за 5 операций можно _>
_>1. берём g1=F(первые 5) находим g1
_>2. берём g2=F(6-ой и первые 5 без g1) получаем g2
_>3. берём g3=F(7-ой и предыущую группу без g2) получаем g3
_> далее остаётся 4 груза назовём их r1,r2,r3,r4
_>4. z1=F(g1,g2,g3,r1,r2)
_>5. z2=F(g1,g2,g3,r3,r4) if (z1=z2) то z2
_> else (g1,g2,g3)-z1-z2
_>
Это красивое решение, но может быть можно за меньшее число операций?
Я тут подумал, после первых трех надо делать не такие операции.
Мы знаем, что гирьки g1, g2, g3 находятся на 3,4 и 5 позициях. Надо выяснить, какая из них находится на позиции 4.
Так же у нас есть гирьки r1, r2, r3, r4, две из которых по весу меньше, чем gi, а две больше.
Варианты:
1. r1, r2 < g1, g2, g3 или g1, g2, g3 < r1, r2. Тогда результат первой операции будет отличаться от результата второй. Значит, искомая гирька та, которая не выпала в качестве результата.
2. r1 < g1, g2, g3 < r2 или r2 < g1, g2, g3 < r1. Тогда результат первой операции не будет отличаться от результата второй. Значит искомая гирька та, что выпала дважды в операциях.
Здравствуйте, nikholas, Вы писали:
N>Имеется гирьки одинаковые по форме но попарно различные по весу. N>За одну операцию можно найти средннюю по весу из 5 гирек. N>За какое наименьшее число таких операций можно найти среднюю по весу из 7 гирек?
Решение за 5 попыток:
1. Первыми тремя попытками определяем трех "кандидатов" (три гирьки наиболее близкие к медиане) и четырех "аутсайдеров". Думаю, алгоритм понятен: после каждой попытки отставляем очереднго "победителя" в сторону и заменяем его новой гирькой.
2. Разбиваем четверых "аутсайдеров" на две пары произвольным образом и выполняем еще две попытки, комбинируя образовавшиеся пары "аутсайдеров" с тройкой "кандидатов". Если в результате этих двух попыток избранной окажется одна и та же гирька — она и есть искомая средняя. Если же выбор пал на две разные гирьки, то искомой средней является ни та, ни другая, а третья.
--
Не можешь достичь желаемого — пожелай достигнутого.