با سلام خدمت همه دوستان
آیا کسی برنامه یا الگوریتمی از معمای کشیشها و آدم خوارها داره ؟؟؟
Printable View
با سلام خدمت همه دوستان
آیا کسی برنامه یا الگوریتمی از معمای کشیشها و آدم خوارها داره ؟؟؟
میشه همینجا مساله رو طرح کنین
شاید خودمون به جواب رسیدیم 8-)
به روی چشم :shock:
مساله به قرار زیر است :
3 کشیش و 3 ادمخوار در یک طرف رودخانه قرار دارند و همچنین قایقی که قادر است یک یا دو نفر را حمل کند . راهی بیابید که همگی به طرف دیگر رودخانه بروند بدون اینکه تعداد کشیشها در یکجا کمتر از تعداد ادمخوارها بشود .
معمولا این مساله را با گرگ و گوسفند عنوان میکردند ولی خوب کتابهای خارجکی حال کردند بگن کشیش و ادم خوار :wink:
اگه آدمخوارها رو با 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);(دو تا آدمخور باقی مونده هم رد میشن)
دوتا از آدمخوارا دو تا از کشیشها را می خورن و بعد به سمت دیگه می رن در این صورت شرط مسئله صادق است!!!!
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	 3;>0)and
(a.SidesPopulation[Right][Vampire& #93;>0)and
(a.SidesPopulation[Left][Human] ;>=
a.SidesPopulation[Left][Vampire]&# 41; and
(a.SidesPopulation[Right][Human	 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	 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]	 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.
امیدوارم کار کنه
موفق باشید :)
اره دیگه هر دفعه باید یکی قایقو بر گردونه
برای سه تا سخت نیست ولی اگه بخواهی الگوریتم رو واسه n تا کشیش و ادو خوار بنویسی خفن میشه
Help me (us) please :mad:
دوستان اینجا رو یه نگاه بندازید
https://barnamenevis.org/showthread.php?t=110558
پیاده سازی کامل مسئله کشیشها و آدمخواران
تقدیم به شما دوست عزیز...
سلام دوستان
تشکر میکنم از بابت مطالب خوب ومفیدتون
یه چیز بگم!!!:افسرده: من نمیدونم این الگوریتم ها چه طوری کار میکنن؟؟؟؟
اگه کسی لطف کنه و راه حل مسئله رو تئوری بدون الگوریتم برام توضیح بده خیلی ممنون میشم:قلب: