Снова о неизвестном грузе
Mar. 2nd, 2012 11:38 amРуководство поставило такую задачу - нужно точно определить вес груза, о котором известно только то, что это целое число от 1 до N. Для этого нам в пользование выделены двухчашечные весы и две гири (какие попросим).
Да, такая задача неразрешима при двузначных N. Но руководство любезно согласилось по нашей просьбе (с которой можно обратиться в любой момент и сколько угодно раз) тут же менять любую гирю на вдвое более тяжелую. Например, начав с гирь массой 1 г и 5 г, мы можем сразу же сравнить вес груза со значениями 1, 5, и 4, а если он окажется меньше 4, то заменить 1 на 2 и сравнить его с 2 и 3 (=5-2).
Какие гири следует заказать вначале, чтобы решить задачу для как можно большего числа N?
Да, такая задача неразрешима при двузначных N. Но руководство любезно согласилось по нашей просьбе (с которой можно обратиться в любой момент и сколько угодно раз) тут же менять любую гирю на вдвое более тяжелую. Например, начав с гирь массой 1 г и 5 г, мы можем сразу же сравнить вес груза со значениями 1, 5, и 4, а если он окажется меньше 4, то заменить 1 на 2 и сравнить его с 2 и 3 (=5-2).
Какие гири следует заказать вначале, чтобы решить задачу для как можно большего числа N?