Тайпе 101 и 2 билярдни топки

Петък е… отдавна не съм ви мъчил със логически загадки, така че ако сте в настроение, четете по-надолу…

Вляво е сградата „Тайпе101“, най-високата сграда в света до тази година, когато откриха Бурж Халифа в Дубай…

Та, представете си, че имате две билярдни топки и искате да разберете, кой е най-високият етаж, от който може да хвърлите билярдна топка, без тя да се счупи.

Единственият начин да го направите е емперично, тоест чрез множество опити.

Ясно е, че ако счупите двете билярдни топки преди да разберете отговора, мисията ви ще е неуспешна.

Ясно е, че ако хвърлите топката първо от 1-ви етаж, после от 2-ри, после от 3-ти и т. н., докато най-накрая се счупи, след най-много 100 опита ще знаете отговора на въпроса.

Големият въпрос е: как ще разберете отговора с две билярдни топки и минимален брой опити?

Чакам коментари.

RoboZZle – Логическа игра за програмисти

Преди да продължите четенето, длъжен съм да ви предупредя, че продуктът не съдържа тютюн и наркотични вещества, но въпреки това води до пристрастяване.
Ирина, ИТ специалист и читател на блога, ми писа за игра, наречена RoboZZle (благодаря!). Името вероятно обединява роботите (robot) и логическите загадки (puzzle), тъй като става въпрос именно за робот, който се движи по разноцветни квадратчета и е нужно да го програмирате така, че да обере всички звезди по екрана.

 

Самото програмиране се състои от няколко основни операции: напред, наляво, надясно, оцветяване, извикване на процедура, изпълнение на операция само при срещане на даден цвят…

Всички тези команди ми напомнят за добрите стари курсове по програмиране на Лого. Въпреки че наборът от операции е минимален, имате възможност под формата на игра да измислите и осмислите основни алгоритми и понятия от програмирането като:

  • Алгоритъм
  • Условен оператор
  • Цикъл с условие
  • Безкраен цикъл
  • Рекурсия
  • Подпрограма
  • Флагове
  • Оптимизиране на код

и др.

Това прави играта изключително подходяща за начално обучение по информатика за малки ученици.

За да играете ви е нужен Microsoft Silverlight, но пък след инсталация и регистрация, не вярвам да имате някакви проблеми.

RoboZZle поддържа gravatars, има форуми за дискусия и възможност да създадете собствени пъзели…

И отново да предупредя за пристрастяването към играта, но понеже съм сигурен, че ви се е доиграло – отворете

http://www.robozzle.com/

и след това споделете как ви се е отразила играта в коментар 🙂

Минимален брой пресичания

Никола, мой колега и голям приятел от Пловдив ми написа една задача, която просто нямаше как да не приема като лично предизвикателство… Само описание на алгоритми не бях вкарвал в блога, ама ето че и за това дойде момента…

Задача: Група програмисти се събират и решават да се напият възможно най-бързо. Как да свърши наздравицата най-бързо, като се „чукнат“ всеки с всеки от присъстващите, със следните уточнения:
– всички порции наздравици се извършват едновременно;
– масата е окръжност, а феновете са точки по нея;
– наздравицата е отсечка между две точки, като по същото време не може да има друга такава отсечка, която да я пресича: няма преплитане на ръце;
– броя на точките (фенове) е n.

Всъщност, това е сериозен проблем, примерно при дизайн на платки, когато без късо съединение (нежелано пресичане) трябва да се определят броя нива на платката. Важно е да споменем, че един програмист може да извършва само една наздравица в даден момент (иначе задачата е тривиална, защото на първи етап всички програмисти се чукват с No. 1, после с No. 2 и така виждаме, че броят е n; ако свързваме всеки път съседните, т.е. при връзки 1-2, 1-3, 1-4, …, 1-n можем да създадем и връзки 2-3, 3-4, 4-5, 5-6, … ще си спестим една наздравица, така че броят е де факто n-1, което е оптималното решение).

И тъй, за другия случай:
Разцъках си решенията за n=4, 6, 8 (после ще обясня защо само на четните).

n=4

n=6 

n=8

От тук нататък правим следният анализ…
За всяко четно n е достатъчно да направим връзки без свободни елементи (всички възли са свързани) и по главния диагонал (остават по 2 несвързани възела).
Общият брой е винаги n и това решение е оптимално.
Когато имаме нечетен брой елементи, обаче, един елемент винаги остава свободен, за който трябва да изпълним тези комбинации. Тогава ще имаме n.(n-1) етапа на наздравица.
Накратко:

  • ако програмист може да вдигне наздравица с няколко програмиста едновременно: n-1
  • ако програмист може да вдигне наздравица само с един човек при четно n: n
  • ако програмист може да вдигне наздравица само с един човек при нечетно n: n.(n-1)