Aftabgardan

(امتیاز : 0)
توسط امین شفیعی در مورخه : پنجشنبه، 24 بهمن، 1392

سلام به دوستان آفتابگردانی و به خصوص دوست قدیمی خودم آقا حمید.

امیدوارم مثل همیشه خوب و شاد باشید.

هنوز هم گاه گداری به آفتابگردون سر میزنم و در جریان امورش هستم هرچند کم و شاید به ندرت ;)

همیشه از برنامه نویسی به خاطر جذاب بودن و شیرینی سختیش خوشم میومدش و این سوال رو که دیدم برام جالب بود جوری که باعث شد پیگیرش باشم و مثل بقیه خودم هم روش فکر کنم تا اگر به جوابی رسیدم بگم البت بعد از پایان مسابقه.

اولش برام خیلی بی منطق بود سوال برای همین قبل از کد نویسی دنبال الگوریتم بودم و منطق تا این به ذهنم رسید، که گفتم بگم البته فرصت تست الگوریتم رو نداشتم به علت مشغله اما فکر کنم منطقا درست کار کنه:

حالت کلی مسئله این هستش: ما m تا عدد داریم ( که اینجا 114 {تعداد سوره های قرآن}) که قرار مجموع n تا از اون ها بشه یه عددی مثل x

(که اینجا 100 هست) پس مسلما باید هر یک به یک m تا عددمون از عدد 100 کوچیکتر باشن پس تمام 114 تا تا سوره قرآن قابل قبول نیستن و فقط اونایی که زیر 100 تا آیه دارن قابل قبولن که تعدادشون برابر هستش با 96 تا سوره از بین این 96 تا سوره هم ما یه سری سوره داریم که تعداد آیه هاشون باهم برابر هستن پس میتونیم اعداد تکراری رو حذف کنیم و تا پردازش کمتری انجام بدیم ( اما بعدا کلک میزنیم و آیه هایی رو که تعدادبرابر هستن با یه دستور ساده for فقط تو چاپ کردن اصلاح میکنیم) که با حذف این سوره های برابر و در واقعا یونیک کردن اعدادمون ما 60 تا سوره برامون باقی میمونه اما خوب فیلتر هنوز تموم نشده حالا باید جمع کمترین عددمون و بیشترین عددمون کوچیکتر مساوی 100 بشه چون اگر بزرگترین عددمون که از 100 کوچیکتر هست جمعش با کوچیکترین عدد بیشتر از 100 بشه به دردمون نمیخوره که با این حساب ما کلا 58 تا عدد قابل قبول و معتبر داریم پس تا اینجا کارمون خیلی خیلی راحت تر و بازه زمانی الگوریتممون کمتر میشه و نیازی نیست که 114 به توان 114 مقایسه انجام بشه (با احتساب حالات تکراری)

خوب حالا اعدادمون رو sort شده داخل یه آرایه قرار میدیم که 58 تا اندیس داره، حالا وقت برنامه اصلی هستش، حلقه ها همیشه یکی از دردسر ساز ترین قسمت های هر زبان برنامه نویسی برای کامپایلر ها و بازه های زمانی هستن مخصوصا زمانی که به درستی استفاده نشن و یا چند حلقه تو در تو داشته باشیم!

همون طوری که توی متن هم حمید جان اشاره کرد اگر جمع عدد اول و دوم بشه a جمع اعداد بعدی باید بشه 100 منهای a ( خط 16 توضیحات پست بالا) خوب پس ما داریم هی یه کار تکراری رو انجام میدیم پس به جای حلقه می تونیم از توابع بازگشتی استفاده کنیم.

پس تا اینجا ما یه ارایه از اعداد مرتب شده از کوچیک به بزرگ داریم پس تابع بازگشتیمون دو پارامتر پارامتر ورودی داره که یکی نشون دهنده شماره ایندکسی از ارایه هس که قراره جمع از اون شروع بشه و دومی شمار ایندکسی از ارایه که عدد پایه برای شروع رو نشون میده، مثلا اینجا اولین عدد ما 3 و دومی 4 .... و پنجاه و هشتمین عدد که 96 هست و پارامتر های ورودی ما میشه 0 که نشون دهنده عدد پایه برای شروع یعنی ایندکس شماره 0 و 1 که عدد شروع جمع رو نشون میده یعنی ایندکس شماره 1 هست و روال عملکرد تابع بازگشتی ما میشه :

x + 3 =100

x=> y + 4 =97

( یعنی مرحله اول تابع بازگشتی عدد اول ارایه بعلاوه یه عدد مجهولی که اینجا x هست میشه 100 تو مرحله دوم تابع بازگشتی x برابر میشه با جمع عدد دوم ارایه مون با یه مجهول دیگه ای که میدهد 97 تا الی اخر )

تا جایی که متغییر ما به صفر یا یه عدد منفی برسه اگر به صفر رسید پس سلسله اعداد انتخاب شده درست بودن و جمعشون میشه 100 ولی اگر به منفی رسید سلسله اعداد انتخاب شده اشتباه بوده و جمعشون مساوی 100 نمیشه.

که نگهداری این سلسله اعداد هم با یه ارایه دو بعدی به راحتی امکان پذیر هستش. که در اخر ما یه ارایه دو بعدی داریم که بر حسب نوع پر شدنش اعداد توی هر سطر و یا هر ستونش مجموعه اعدادی هستن که مجموعشون برابر 100 هست.

که فقط باید برای شرط پایان تابع تو در تو این رو لحاظ کنید که شرطش اینه که اگر به صفر یا عدد منفی رسیدیم کار تموم شه، که این طوری باز کمتر از حالت 54 به توان 54 میشه بر عکس الگوریتم هایی با for های تو در تو و قاعدتا هر هددی که با عددا بعدش جمع میشه تا قبل از رسیدن به عدد 85 جوابش رو میده و هر بار هم که تابع بازگشتی ما با عدد بعدی فراخونی میشه از اعداد ما مثل حالت فاکتوریل مانند کم میشه :)

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

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

امیدوارم تونسته باشم طریقه کار الگوریتم رو بهتون برسونم.

یا اینکه اگر کسی خواست پیاده سازیش کنه و نتیجه رو با هم ببینیم.

ممنون از حمید جان بابت این سوال شیرین و جالبش :).

موفق باشید.

امین شفیعی;


تِستا ؛ سیستم مدیریت آزمون آنلاین	نُمرا ؛ سیستم مدیریت آموزش

حُجرا ؛ سیستم مدیریت محتوا	لینکا ؛ سیستم مدیریت و فروش لینک

مَدفا ؛ طرح مدرسه هوشمند	پروژا ؛ سیستم مدیریت پروژه

درباره‌ آفتابگردان

اخبار کوتاه سایت:

محصولات آفتابگردان

بلوک کاربری

موضوعات اخبار

آخرین نظرات کاربران

مطالب پیشنهادی