Послепятничная задачка

← →
default © (2004-11-06 20:22) [0]

Необычный клиент.
Некий человек принес в банк 1000 долларов однодолларовыми купюрами и 10 пустых мешков и, обратившись к клерку, сказал:

— Не откажите в любезности разложить эти деньги по мешкам так, чтобы любую сумму денег, которая мне понадобится, вы всегда могли бы выдать в одном или нескольких мешках, не вскрывая при этом ни одного из них.

Как нужно разложить деньги? Выдать любую требуемую сумму банк должен лишь один раз, величина ее ограничена только размером вклада. Иначе говоря, вкладчик имеет право потребовать любую сумму от 1 до 1000 долларов (число долларов должно быть целым).

← →
VID © (2004-11-06 20:36) [1]

мешок сумма 1 1 2 2 3 4 4 8 5 16 6 32 7 64 8 128 9 256 10 489

← →
Comp © (2004-11-06 21:25) [2]

> [1] VID © (06.11.04 20:36)

Хитро...

← →
default © (2004-11-06 21:25) [3]

[1]
ага, сразу в голову двоичный код пришёл?

← →
VID © (2004-11-06 21:32) [4]

default © (06.11.04 21:25) [3]
ну да, как то так сразу получилось...

← →
SergP © (2004-11-06 22:27) [5]

Задачка на аналогичную тему:
Есть чашечные весы, и ими нужно взвешивать определенный груз весом 1,2,3 ... 40 кг. Для этого нужно сделать 4 гири.
Какого веса должна быть каждая гиря?

← →
Alex_Petr © (2004-11-06 22:48) [6]

1,3,9,27

← →
SergP © (2004-11-06 22:50) [7]

ага

← →
default © (2004-11-07 02:01) [8]

Alex_Petr © (06.11.04 22:48) [6]
хм, случаем не перебор?

← →
Alex_Petr © (2004-11-07 02:13) [9]

default © (07.11.04 2:01) [8]
Нет.
Известное св-во геометрической прогрессии с основанием 3.

← →
default © (2004-11-07 02:30) [10]

[9]
такое?
3^0-->1
3^0+3^1-->1,2,3,4
3^0+3^1+3^2-->1,2,3,4,5,6,7,8,9,10,11,12,13
3^0+3^1+...+3^n-->1,2,3,4,...,3^0+3^1+...+3^n

3^n-1=2*(3^0+3^1+3^2+...+3^(n-1));

[11]
и как это свойство используется?

Вес G просят представить в виде ряда гирек.
Ясно, что сумма этих гирек равна (не меньше) G.
Т.к. просят еще и представить любой вес < G, то, интуитивно,
ясно, что наибольшая из гирек должна быть, примерно, в 2 раза
больше суммы остальных.
А это очень смахивает на нашу геометрическую прогрессию.

Вобщем если в задаче
> default © (06.11.04 20:22)

мы имели дело с двоичной системой (конкретный мешок с деньгами либо выдается клиенту либо нет,
то в
> [5] SergP © (06.11.04 22:27)

мы имеем дело с троичной системой (гиря либо ставится на чашку, либо не ставится, либо ставится на другую чашку вместе с взвешиваемым грузом), далее все просто...

SergP © (07.11.04 07:46) [14]
всё-равно, вот это "мы имеем дело с троичной системой (гиря либо ставится на чашку, либо не ставится, либо ставится на другую чашку вместе с взвешиваемым грузом)" для меня не совсем убедительно, интуитивно да, а так нет...
P.S. ну да фиг с ним

Послепятничная задачка Найти похожие ветки