-ѕоиск по дневнику

ѕоиск сообщений в akry

 -ѕодписка по e-mail

 

 -—татистика

—татистика LiveInternet.ru: показано количество хитов и посетителей
—оздан: 21.08.2007
«аписей: 4917
 омментариев: 25572
Ќаписано: 40060


«адачка о швыр€нии шаров

—реда, 05 Ќо€бр€ 2008 г. 00:11 + в цитатник

ƒва Ўара

Kavychka подкинула мне интересную задачку.

” вас есть небоскрЄб в 100 этажей. ≈сть 2 биллиардных шара. » 19 попыток, чтобы вы€снить, брошенные начина€ с какого этажа шары будут разбиватьс€ вдребезги. Ётаж может быть любым, задача — разработать алгоритм определени€ этажа с учЄтом вводной.

Kavychka передала мне, что есть три варианта решени€, из которых только один €вл€етс€ оптимальным.

¬ простом виде задача решаетс€ за несколько минут. ѕредлагаю вам тоже развлечьс€.

ј дальше начинаетс€ интересное. ѕохоже, что решений не три, а гораздо больше.

 то решил задачу или замучалс€ еЄ решать, загл€дывайте под кат. ќбсудим.

»так, простейший вариант решени€. Ќа него наводит волшебное число 19 = 10+9. Ѕросаем шары каждые 10 этажей, начина€ с 10-го.  ак шар разбиваетс€, откатываемс€ на -9 этажей и бросаем шары, поднима€сь каждый раз на один этаж. »того, в самом крайнем случае, дл€ 99-го этажа у нас уходит как раз 19 бросков. » два шара.

–ешение, которое возможно оптимально. Ѕросаем с 19 этажа, наращива€ каждый раз по 10 этажей.  ак шар разбиваетс€, возвращаемс€ на -9 этажей и как в предыдущем пункте. ¬озможно € не догон€ю, но мне не вполне €сно, оптимальное ли это решение, и если да, то почему.  онечно веро€тность того, что нужный этаж окажетс€ в промежутке 1-19 примерно равна 1/5, ну и что? »ли дело в экономии электроэнергии лифта, потому что спускатьс€ легче, чем подниматьс€? ¬ общем, кто знает, просветите.

¬от мы и подошли к интересному. Ќесложные расчЄты показывают, что мы можем бросать и по 9 шаров, начина€ с 9 этажа. » по 8, начина€ с 8-го. » бросать по сложным схемам с шагом между этажами типа 19 - 18 - 17 - 16… ј начинать бросать можем с этажа в диапазоне от 7-го по 19 этаж.

¬ общем, принцип похоже такой:

  1. ƒл€ каждого следующего броска количество оставшихс€ «больших» шагов и количество «малых» (по 1 этажу) должно быть меньше оставшегос€ числа попыток. Ёто верно дл€ любого количества этажей и любого количества попыток.
  2.  идаем сначала «большими шагами» по F этажей, как только шар разбиваетс€, возвращаемс€ на F-1 этаж и бросаем шары, увеличива€ этаж на один с каждым броском.
  3. ѕервый самый высокий этаж, с которого можно начинать бросать, равен количеству попыток (в силу п.1).
  4. ѕервый самый малый этаж, с которого можно начинать бросать — не знаю какой. UPD. «атмение нашло — конечно см. п1.
  5. ѕредел попыток дл€ N этажей (и двух шаров) будет равен сумме дес€тков (округлЄнной в меньшую сторону) + 9 дл€ N >= 10. “о есть, в случае 105 этажей, попыток должно быть 10+9 = 19. ј дл€ 128 этажей — 12 + 9 = 21 попытка.

¬ случае если мы используем больше двух шаров, тоже возможны разные варианты стратегий кидани€. ћожно сделать не две, а три «нарезки». Ќапример, вначале бросать каждые 30 этажей, потом каждые 7 этажей, потом по одному этажу. ѕринцип остаЄтс€ тот же.

ћне кажетс€ выгодным каждый дополнительный шар использовать дл€ того, чтобы поделить искомое пространство пополам. Ќапример, в случае со 100 этажами и 3 шарами, первый шар бросаем с 50-го этажа. ќн или разбиваетс€, или нет. ≈сли разбиваетс€, значит наша половина — от 1 по 49 этаж. ≈сли не разбиваетс€, то ищем уже в диапазоне от 51 до 100 этажа.

≈сли по€вл€етс€ ещЄ один, четвЄртый шар, просто делим пространство этажей пополам два раза. ¬ пределе у нас будет log2(N) попыток. Ќужный этаж дл€ стоэтажного небоскрЄбика мы найдЄм максимум за 7 бросков. » 6 шаров.

¬ итоге, даже дл€ вводных в начале задачки (100 этажей, 19 попыток и 2 шара) возможно больше трЄх вариантов решени€.  акой из них самый оптимальный, и как определить оптимальность, € не знаю.

UPD. ЌашЄл оптимальное решение — за 14 попыток. Ѕросать с N=14 этажа с шагом N-1.

–убрики:  »нтересное
»деи и мысли
ћетки:  

paillette   обратитьс€ по имени —реда, 05 Ќо€бр€ 2008 г. 13:53 (ссылка)
ѕрикольно) Ёта задачка была в этом году на школьной олимпиаде в 8-ых классах))
“олько там шары метала макака. ƒа и не шары, а кокосы...
ќтветить — цитатой ¬ цитатник
 

ƒобавить комментарий:
“екст комментари€: смайлики

ѕроверка орфографии: (найти ошибки)

ѕрикрепить картинку:

 ѕереводить URL в ссылку
 ѕодписатьс€ на комментарии
 ѕодписать картинку