مسئله ي جالبيه، هر کس تونست به هر زبوني پياده سازي کنه حتماً اينجا اعلام کنه
مسئله ظرف نان مقدس
به شما n ظرف نان مقدس اهدا شده است. هر یک از این n ظرف دارای ظرفیت مخصوصی برای نان هستند:
( c1,c2 ,c3,…cn)
در ابتدا در هر یک از n ظرف تعداد مشخصی نان قرار داده شده است.
(x1,x2,x3,…xn) که هر کدام به این صورته مثلاً: 0< x1<c1,……0<xn<cn
پدر مقدس از شما میخواهد تا مقادیر نان هر ظرف را با اعمال زیر به (d1,d2,…,dn)که باز0<d1<c1 ,…..0<dn<cn تغییر دهید:
- می توانید همه نان های یک ظرف را تا جایی که ظرف دوم جا دارد در ظرف دیگر خالی کنید ( باقیمانده در ظرف اول می ماند)
- می توانید با دعا از عیسی مسیح بخواهید تا تعداد نانهای داخل یک ظرف را به توان دو برساند.
مدلسازی:
ورودی مسئله که ورودی استاندارد خوانده خواهد شد به صورت زیر است:
در سطر اول تعداد سبدها و در سطر دوم به ترتیب ظرفیت هر ظرف نان نوشته خواهد شد. در سطر سوم مقدار اولیه هر ظرف و در سطر آخر مقدار درخواستی نان ها در هر ظرف خواهد بود:
3
100 5 3
45 0 0
41 1 3
می توانید فرض کنید که ; 3<n<5 1 < ci < 1000
قابل توجه شما:این علامتهای کوچکتر و بزرگتری که نوشتم مساوی هم دارند
حل مسئله:
هدف پیدا کردن کمترین هزینه ممکن برای رساندن محتویات ظرف ها به درخواست پدر مقدس است. اما در این راه هزینه عمل اول (جابجایی محتویات ظروف ) با عمل دوم (دعا به درگاه مسیح) یکسان نیست. هزینه هر جابجایی برابر 1 و هزینه عمل دوم برابر تعداد نان هایی خواهد بود که عیسی به شما اعطا کرده به اضافه 1 است.
خروجی مسئله:
در خروجی استاندارد در سطر اول ابتدا طول دنباله اعمال، سپس هزینه آنها و در آخر تعداد حالات مشاهده شده توسط الگوریتم را می نویسید.سپس دنباله جواب را در سطر بعدی خواهید نوشت.دنباله جواب به صورت یک دنباله از جفتهای مرتب خواهد بود که بین دو درایه یک ویرگول قرار دارد و جفتهای مجزا با فاصله از هم جدا شده اند.
به ازای هر جابجایی نان ها ،درایه اول دنباله ظرف مبدا و درایه دومی ظرف مقصد خواهند بود.برای هر بار دعا نیز یک جابجایی از یک ظرف به خودش را در نظر بگیرید.مثلاً اگر در ابتدا نان های ظرف 1 را در ظرف 2 ریخته اید و آنگاه محتویات ظرف 2 را در ظرف 3 و سپس دعا نموده اید تا محتویات ظرف 3 به توان دو برسد و در آخر نیز نان های ظرف 3 را در ظرف 1 ریخته اید ،جوابی که در خروجی چاپ می کنید باید چنین باشد:
4 10 234
1,2 2,3 3,3 3,1
اگر هیچ جوابی پیدا نکردید،ابتدا عدد 1- و سپس تعداد حالات جستجو را در خروجی می نویسید:
-1 131222
پیاده سازی:
مسئله را باید با الگوریتم های زیر پیاده سازی کرد:
1- الگوریتم BFS
2- الگوریتم DFS
3- الگوریتم Iterative Deepening DFS
4- Bidirectional Search
5- Uniform Cost Search
نیاز نیست تا الگوریتم DFS یک جواب بهینه را پیدا نماید.
برنامه باید الگوریتمی که موقع اجرا به کار می برد را به عنوان آرگومان در هنگام اجرا بگیرد.
مثلاً اگر نام برنامه شما project.exe است ،دستور زیر باید برنامه شما را با الگوریتم BFS به اجرا درآورد:
C:/>project.exe 1