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

[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):Boole  an;

implementation





function IsValid(a:TRiverCondition):boolean  ;

begin

 Result:=(a.SidesPopulation[Left]&#  91;Human]>0)and

         (a.SidesPopulation[Left][Vampire&#  93;>0)and

         (a.SidesPopulation[Right][Human&#9  3;>0)and

         (a.SidesPopulation[Right][Vampire&  #93;>0)and



         (a.SidesPopulation[Left][Human&#93  ;>=

          a.SidesPopulation[Left][Vampire]&#  41; and



         (a.SidesPopulation[Right][Human&#9  3;>=

          a.SidesPopulation[Right][Vampire]&  #41;;



end;



function Goal(a:TRiverCondition):boolean;

begin

 Result:=(a.SidesPopulation[FirstSide&#  93;[Human]=0)and

         (a.SidesPopulation[FirstSide][Vamp  ire]=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):Boole  an;

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&#9  3;:=a.SidesPopulation[a.BoatSide][  Human]-hh;

       b.SidesPopulation[not a.BoatSide][Human]:=a.SidesPopulat  ion[a.BoatSide][Human]+hh;

       b.SidesPopulation[a.BoatSide][Vampire&  #93;:=a.SidesPopulation[a.BoatSide]&#9  1;Vampire]-vv;

       b.SidesPopulation[not a.BoatSide][Vampire]:=a.SidesPopul  ation[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]

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

[ms_arani]

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

[nokteh]

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

[Reyhane7]

حل مسئله کشيش‌ها و آدمخوارها به روش هاي مختلف در همين لينک