Интересная задачка :)
(4 votes, average: 4 out of 5)
Loading ...Задачка, если честно, из моего дества. В школе мне попалась.
Собственно: дан грузик некоторого целого веса, аптекарские весы (с чашачками такие) и
набор грузиков с весами 1, 3, 9, 27, … (в наборе каждого веса грузик есть только в 1 экземпляре).
Требуется написать программу (скажем на руби), которая будет уравновешивать 1-й грузик грузиками
из набора, причем класть грузики можно на обе чашечки.
А для Настоящих Программистов продолжение: выяснить будет ли алгоритм конечным (доказать конечность или бесконечность).
В случае если вы считаете его конечным, оценить его сложность и кол-во необходимых грузиков (опять же с доказательством, ну или доказать невозможность такой оценки) 
Удачи в развлекаловке!
Тимур Вафин:
http://rubyquiz.com/ тема
Задачку надо решить ))
Тимур Вафин:
Задачка между прочим для математиков =)
Другое дело, что хороший программист должен обладать хорошей математической поготовкой
Артем Голубев:
Тимур, причем тут математики. Эта была задача по программированию в школе.
Там же надо составить алгоритм. А вот всякие доказательства и оценки, опять же
computer science. Каждый программист должен знать.
Артем Голубев:
Этот рубиквиз реально дурацкий сайт. Чувак там говорит, что типа посылайте все мне по почте или в куонференции. Полный маразм. Почему я не могу засабмитить задачку или решение прямо на сайте (пусть даже ничего сразу не покажется)?
Айрат Натфуллин:
Т.к. гири это степени тройки, то логично её решать в тройчной системе исчесления.
Пошел думать как…
p.s. Тимур, помнишь, как эту задачку решал Стец?) Сколько он мне не объяснял, я так и не понял тогда алгоритма)
Тимур Вафин:
А он ее решил?
Айрат Натфуллин:
да, решил.
я только не помню какие именно гири тогда были
потому что, к примеру, если 1,2,4,8… то она решается элементарно
Айрат Натфуллин:
yes! решил!
всё никак не мог понять как же использовать троичную, потом допёрло, что вместо 2 надо писать +1-1, почитал - оказалось это есть симметричная система исчисления
на примерах:
1.
67[10] = 2111[3] => 1(-1)111
минус значит что соответствующую гирю надо класть на чашу 1го грузика
получаем
81 + 9 + 3 + 1 ? 67 + 27
94 == 94
2.
43[10] = 1121[3] => 11(+1-1)1 => 1 (+1+1)(-1)1 => 12(-1)1 => 2(-1)(-1)1 => 1(-1)(-1)(-1)1
проверяем
81 + 1 ? 43 + 27 +9 + 3
82 == 82
клево! самому понравилось;)
эх, есть еще порох в пороховницах))
Артем Голубев:
Какова сложность алгоритма и максимальное кол-во необходимых грузиков?
Айрат Натфуллин:
= сложности преобразования числа из десятичной в симметричную троичную (не знаю, можно ли сразу в неё перевести)
или же, в случае как я делал: сложность алгоритма перевода из десятичной в троичную (это, если не ошибаюсь, log(3)N) + линейное преобразование = O(N)
log(3)N + O(N)
а что значит максимальное количество грузиков?
если это максимальное количество грузиков, которое может понадобиться для N, то не больше, чем K = min k : N
Айрат Натфуллин:
(формула не отобразилась в предыдущем коммента)
K = min k : N < 3^k
Артем Голубев:
Оценка сложности верна, но можно дать более точную