حل مسئله کشیش ها و آدمخوارها:

سه کشیش و سه آدمخواردر یک سمت رودخانه قراردارند .چطور میشه با یک قایق که توانایی
حمل حداکثر دو نفر را دارد آنها را به سمت دیگر رودخانه انتقالدهیم که در سمتی که قایق نیست تعداد کشیش ها از آدمخوارها بیشتر و بلعکس تعداد آدمخوارها از کشیش ها بیشتر نشود. 

برگردیم سر مسالهٔ اصلی‌ خودمون. برای حل این مساله با استفاده از درختا، یه سری اومدن گفتن که بیایم یه درخت بسازیم که به جای اینکه میوش گیلاس باشه، میوش (x,y,z) باشه! (اینم یه فرق دانشمندانه انفورماتیک با آدم های معمولی‌. به جای اینکه درختشون گیلاس و‌ خرمالو و‌ این جور چیزا بده، (x,y,z) میده!!) و اما معنی (x,y,z) چیه؟ فرض کنین که رودخونه، یه سمتش اسمش هست A و سمت دیگش اسمش هست B. و فرض کنیم که همهٔ آدم ها و‌ همهٔ آدم خورها، الان سمت A قرار دارند و‌ میخوان برن سمت B.

x تعداد آدم ها رو در سمت A نمایش میده
y تعداد آدم خورها رو در سمت A نمایش میده
و z هم میتونه دو مقدار به خودش بگیره. یکی‌ صفر که نشون میده قایق سمت B هستش و دیگری یک که نشون میده قایق سمت A هستش.
توجه کنید x و y همیشه بین صفر و‌ سه هستن.

بازی همیشه در وضعیت (3,3,1) شروع می‌شه.یعنی‌ آدم ها و آدم خور ها و قایق هر سه در سمت A قرار دارن. و هدف ما از انجام بازی رسیدن به وضعیت (0,0,0) هستش. یعنی‌ آدم خورها و‌ آدم ها و‌ قایق هر سه در طرف B قرار بگیرن. از اینجا به بعد ساختن درخت برعکس! شروع می‌شه.

اجازه بدید از اینجا به بعد رو با یه شکل توضیح بدم.


همینطور که می‌بینید بالای بالا ریشهٔ درخت قرار داره. یعنی‌ وضعیت (3,3,1) که معنیش اینه که آدم خورها و‌ آد‌م ها و‌ قایق همشون سمت A قرار دارن. قدم بعدی شاخ و برگ دادن به درخته.اگر یکی از آدم ها سوار قایق بشه و بره اون طرف، وارد وضعیت (2,3,0) میشیم. اما این وضعیت قابل قبول نیست. چون تعداد آدم خورها در سمت A برابر ۳ میشه و تعداد آدم ها، برار ۲. پس آدم ها خورده می شن. از اونجایی که این وضعیت قابل قبول نیست، اون رو به رنگ قرمز در می آریم. و اما یک وضعیت قابل قبول می تونه وضعیت (3,2,0) باشه. یعنی یکی از آدم خورها سوار قایق شده و به سمت B رفته.خلاصه این کار رو ادامه می دیم تا تمامی وضعیت هایی که در بالا مشاهده می کنید، تولید بشن. این کار رو باز هم ادامه میدیم، و باز هم ادامه می دیم و انقدر ادامه میدیم تا به وضعیت (0,0,0) برسیم.