کشیشها و آدم خوارها

[M@hdi]

با سلام خدمت همه دوستان
آیا کسی برنامه یا الگوریتمی از معمای کشیشها و آدم خوارها داره ؟؟؟

[Sepidar]

میشه همینجا مساله رو طرح کنین

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

[M@hdi]

به روی چشم :shock:
مساله به قرار زیر است :
3 کشیش و 3 ادمخوار در یک طرف رودخانه قرار دارند و همچنین قایقی که قادر است یک یا دو نفر را حمل کند . راهی بیابید که همگی به طرف دیگر رودخانه بروند بدون اینکه تعداد کشیشها در یکجا کمتر از تعداد ادمخوارها بشود .
معمولا این مساله را با گرگ و گوسفند عنوان میکردند ولی خوب کتابهای خارجکی حال کردند بگن کشیش و ادم خوار :wink:

[phantasm]

اگه آدمخوارها رو با 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]

دوتا از آدمخوارا دو تا از کشیشها را می خورن و بعد به سمت دیگه می رن در این صورت شرط مسئله صادق است!!!!

[Sepidar]

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]

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

[dehghanimeh]

دوستان اینجا رو یه نگاه بندازید
http://barnamenevis.org/forum/showthread.php?t=110558

[ms_arani]

پیاده سازی کامل مسئله کشیشها و آدمخواران
تقدیم به شما دوست عزیز...

[nokteh]

سلام دوستان
تشکر میکنم از بابت مطالب خوب ومفیدتون
یه چیز بگم!!!:افسرده: من نمیدونم این الگوریتم ها چه طوری کار میکنن؟؟؟؟
اگه کسی لطف کنه و راه حل مسئله رو تئوری بدون الگوریتم برام توضیح بده خیلی ممنون میشم:قلب:

[Reyhane7]

حل مسئله کشيش‌ها و آدمخوارها به روش هاي مختلف در همين لينک (http://artificial.ir/intelligence/thread827.html)