PDA

View Full Version : کشیشها و آدم خوارها



M@hdi
شنبه 22 فروردین 1383, 15:16 عصر
با سلام خدمت همه دوستان
آیا کسی برنامه یا الگوریتمی از معمای کشیشها و آدم خوارها داره ؟؟؟

Sepidar
شنبه 22 فروردین 1383, 17:26 عصر
میشه همینجا مساله رو طرح کنین

شاید خودمون به جواب رسیدیم 8-)

M@hdi
دوشنبه 24 فروردین 1383, 09:17 صبح
به روی چشم :shock:
مساله به قرار زیر است :
3 کشیش و 3 ادمخوار در یک طرف رودخانه قرار دارند و همچنین قایقی که قادر است یک یا دو نفر را حمل کند . راهی بیابید که همگی به طرف دیگر رودخانه بروند بدون اینکه تعداد کشیشها در یکجا کمتر از تعداد ادمخوارها بشود .
معمولا این مساله را با گرگ و گوسفند عنوان میکردند ولی خوب کتابهای خارجکی حال کردند بگن کشیش و ادم خوار :wink:

phantasm
دوشنبه 24 فروردین 1383, 12:14 عصر
اگه آدمخوارها رو با k و کشیشها رو با aنشون بدیم و left و right سمت چپ و راست رودخونه باشن, الگوریتم به این صورت میشه:



left(a1,a2,a3,k1,k2,k3); & right(null);

left(a1,a2,a3,k3); & right(k1,k2);(دوتا آدمخور از رودخونه رد میشن)

left(a1,a2,a3,k1,k3); & right(k2);(یکی از آدمخورها برمیگرده)

left(a1,a2,a3); & right(k1,k2,k3);(دوتا دیگه از ادمخورها از رودخونه رد میشن)

left(a1,a2,a3,k1); & right(k2,k3);(یکی از آدمخورها برمیگرده)

left(a3,k1); & right(a1,a2,k2,k3);(دوتا از کشیش ها رد میشن)

left(a1,a3,k1,k2); & right(a2,k3);(یه کشیش و یه ادمخور برمیگردن)

left(k1,k2); & right(a1,a2,a3,k3);(دو تا کشیش رد مشن)

left(k1,k2,k3); & right(a1,a2,a3);(یه ادمخور برمیگرده)

left(k3); & right(a1,a2,a3,k1,k2);(دوتا آدمخور از رودخونه رد میشن)

left(k1,k3); & right(a1,a2,a3,k2);(یکی از آدمخورها برمیگرده)

left(null); & right((a1,a2,a3,k1,k2,k3);(دو تا آدمخور باقی مونده هم رد میشن)

houtanal
دوشنبه 24 فروردین 1383, 16:27 عصر
دوتا از آدمخوارا دو تا از کشیشها را می خورن و بعد به سمت دیگه می رن در این صورت شرط مسئله صادق است!!!!

Sepidar
سه شنبه 25 فروردین 1383, 19:52 عصر
unit HV;

interface
const
Left=false;
Right=true;

Human=0;
Vampire=1;

Type
TPopulation=array[Human..Vampire] of byte;

TRiverCondition=Record
SidesPopulation:array[Left..Right] of TPopulation;
BoatSide:Boolean;
end;

var
n:byte;
FirstSide:boolean;

function Transport(a:TRiverCondition):Boolean;
implementation


function IsValid(a:TRiverCondition):boolean;
begin
Result:=(a.SidesPopulation[Left][Human]>0)and
(a.SidesPopulation[Left][Vampire]>0)and
(a.SidesPopulation[Right][Human]>0)and
(a.SidesPopulation[Right][Vampire]>0)and

(a.SidesPopulation[Left][Human]>=
a.SidesPopulation[Left][Vampire]) and

(a.SidesPopulation[Right][Human]>=
a.SidesPopulation[Right][Vampire]);

end;

function Goal(a:TRiverCondition):boolean;
begin
Result:=(a.SidesPopulation[FirstSide][Human]=0)and
(a.SidesPopulation[FirstSide][Vampire]=0)and
(a.SidesPopulation[not FirstSide][Human]=n)and
(a.SidesPopulation[not FirstSide][Vampire]=n);
end;

procedure WriteCondition(a:TRiverCondition);
begin
//display a in somewhere
end;

function Transport(a:TRiverCondition):Boolean;
var
vv,hh:byte;
ok:Boolean;
b:TRiverCondition;
begin
b.BoatSide:=not a.BoatSide;
ok:=Goal(a);
if IsValid(a) and not ok then
for vv:=0 to 2 do
for hh:=0 to 2 do
if ((vv+hh)>0) and (not ok) then begin
b.SidesPopulation[a.BoatSide][Human]:=a.SidesPopul ation[a.BoatSide][Human]-hh;
b.SidesPopulation[not a.BoatSide][Human]:=a.SidesPopulation[a.BoatSide][ Human]+hh;
b.SidesPopulation[a.BoatSide][Vampire]:=a.SidesPop ulation[a.BoatSide][Vampire]-vv;
b.SidesPopulation[not a.BoatSide][Vampire]:=a.SidesPopulation[a.BoatSide ][Vampire]+vv;

ok:=Transport(b);
end;


if ok then WriteCondition(a);
Result:=ok;
end;

end.

امیدوارم کار کنه

موفق باشید :)

GentleGuy
یک شنبه 04 اردیبهشت 1384, 18:54 عصر
اره دیگه هر دفعه باید یکی قایقو بر گردونه
برای سه تا سخت نیست ولی اگه بخواهی الگوریتم رو واسه n تا کشیش و ادو خوار بنویسی خفن میشه
Help me (us) please :mad:

dehghanimeh
دوشنبه 27 آبان 1387, 22:42 عصر
دوستان اینجا رو یه نگاه بندازید
http://barnamenevis.org/forum/showthread.php?t=110558

ms_arani
چهارشنبه 29 آبان 1387, 10:54 صبح
پیاده سازی کامل مسئله کشیشها و آدمخواران
تقدیم به شما دوست عزیز...

nokteh
دوشنبه 08 آذر 1389, 09:29 صبح
سلام دوستان
تشکر میکنم از بابت مطالب خوب ومفیدتون
یه چیز بگم!!!:افسرده: من نمیدونم این الگوریتم ها چه طوری کار میکنن؟؟؟؟
اگه کسی لطف کنه و راه حل مسئله رو تئوری بدون الگوریتم برام توضیح بده خیلی ممنون میشم:قلب:

Reyhane7
دوشنبه 08 آذر 1389, 11:29 صبح
حل مسئله کشيش‌ها و آدمخوارها به روش هاي مختلف در همين لينک (http://artificial.ir/intelligence/thread827.html)