با سلام خدمت همه دوستان
آیا کسی برنامه یا الگوریتمی از معمای کشیشها و آدم خوارها داره ؟؟؟
با سلام خدمت همه دوستان
آیا کسی برنامه یا الگوریتمی از معمای کشیشها و آدم خوارها داره ؟؟؟
میشه همینجا مساله رو طرح کنین
شاید خودمون به جواب رسیدیم 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);(دو تا آدمخور باقی مونده هم رد میشن)
دوتا از آدمخوارا دو تا از کشیشها را می خورن و بعد به سمت دیگه می رن در این صورت شرط مسئله صادق است!!!!
Artists use lies to tell the truth while politicians use them to cover the truth up
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
پیاده سازی کامل مسئله کشیشها و آدمخواران
تقدیم به شما دوست عزیز...
سلام دوستان
تشکر میکنم از بابت مطالب خوب ومفیدتون
یه چیز بگم!!! من نمیدونم این الگوریتم ها چه طوری کار میکنن؟؟؟؟
اگه کسی لطف کنه و راه حل مسئله رو تئوری بدون الگوریتم برام توضیح بده خیلی ممنون میشم