دوشنبه ۱۰ دی ۱۴۰۳ |  عضویت / ورود

اعلام نتایج مسابقه «وتیره»

همانطور که در مطلب «مسابقه‌ای کوچک با جایزه‌ای کوچک ویژه برنامه‌نویسان (به مناسبت دهه فجر)» شاهد بودید، یک مسابقه برنامه‌نویسی به مناسب دهه فجر برگزار کردیم و سؤال آن مسابقه این بود که: برنامه‌ای بنویسید که مشخص کند مجموع آیات چه سوره‌هایی از قران، ۱۰۰ آیه می‌شود.

خوب، در حالی که من اصلاً انتظار نداشتم، اما چهار نفر توانستند به خوبی از پس این برنامه برآیند و برنامه‌شان را ارسال کنند:

- آقای سینا قلی‌پسند: برنامه‌ او اینجاست.

- آقای iman moodi: برنامه او اینجاست.

- آقای سید محمد حسینی نژاد یا همان «مهندس طلبه» خودمان: برنامه او اینجاست.

- آقای فرهاد مرتضی‌پور: برنامه او را از اینجا دانلود کنید.

سورس برنامه‌ها را می‌توانید یک‌جا از اینجا دانلود کنید.

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

در مورد الگوریتمی که عزیزان به کار گرفتند، سه نفر اول، می‌شود گفت یک الگوریتم داشتند و آن استفاده از ۳ یا ۴ حلقه تو در تو بود که باعث می‌شد تا چهار سوره که مجموعاً ۱۰۰ آیه شوند پیدا شود.

اما خوب، احتمالاً می‌دانید که در این حالت، مرتبه زمانی ما n به توان ۳ یا ۴ می‌شود. یعنی ۱۱۴ به توان ۳ یا ۴ پردازش لازم است! (۱۱۴ به توان ۴ می‌شود: 168896016)

می‌بینید که تعداد عملیات بسیار بالاست و سه برنامه اول نهایتاً توانستند مجموع ۴ سوره را پیدا کنند.

البته نیاز بود بهبودهایی انجام می‌دادند از جمله اینکه: وقتی مثلاً سوره حمد در حلقه اول انتخاب می‌شد، در حلقه دوم، سوره‌هایی که از ۹۳ آیه بیشتر دارند، از آرایه حذف شوند. در این حالت پردازش‌ها به تعداد قابل توجهی کاهش می‌یافت و یا در حلقه سوم، باید «سوره حمد+سوره دوم انتخابی» محاسبه می‌شد و سوره‌هایی که بیشتر از «۱۰۰ منهای این مجموع» داشتند حذف می‌شدند و بعد به گردش می‌افتاد...

اما خوب، بهترین الگوریتم به خوبی توسط آقای مرتضی‌پور شناسایی شد و آن استفاده از الگوریتم Back Tracking بود. پیشنهاد می‌کنم حتماً توضیحات خوب و کامل ایشان را در فایل pdfی که ارسال کرده‌اند بخوانید.

چون آن توضیحات واضح و کامل است، من دیگر توضیح نمی‌دهم اما به طور خلاصه، این مسأله شبیه به این بود که بگوییم «یک مجموعه از اعداد رندوم داریم. می‌خواهیم بدانیم چند زیرمجموعه می‌توان یافت که مجموع اعضای آن ۱۰۰ شود؟» برای یافتن زیرمجموعه‌های غیرتکراری یک مجموعه که شرط خاصی داشته باشند، می‌توان از الگوریتم Back Tracking استفاده کرد که موارد تکراری و پردازش‌های اضافه را بسیار کاهش می‌دهد.

البته با توجه به اینکه لیست کردن تمام موارد این مسأله، پردازش بسیار بسیار سنگینی را می‌طلبد، این الگوریتم هم در اواسط کار کم می‌آورد و ادامه نمی‌دهد! من تا یک ساعت و ده دقیقه برنامه را در حال اجرا گذاشتم، بعد از یافتن ۳۰۰ هزار(!!!) ترکیب سوره‌های مختلف، هنگ کرد... (من خودم فکر نمی‌کردم بتوان حداقل ۳۰۰ هزار حالت از ترکیب سوره‌ها را یافت که جمعشان ۱۰۰ بشود!)
دقت کنید که اگر حالات تکراری را حساب کنیم، این برنامه باید ۱۱۴ به توان ۱۱۴ مقایسه انجام دهد تا پاسخ کامل را حساب کند! (یعنی یک ۳ با ۲۳۴ صفر جلو آن!!)

به هر حال، با اینکه برنامه‌های همه دوستان جالب و گاهی مبتکرانه بود اما طبیعتاً جایزه مسابقه تعلق می‌گیرد به آقای فرهاد مرتضی‌پورhttp://aftab.cc/modules/Forums/images/smiles/icon_wink.gif

این مسابقه، بهانه خوبی برای آشنا شدن با نابغه‌های حاضر در آفتابگردان بود. امیدوارم حضورشان باعث پیشرفت روز افزون آفتابگردان و کاربران باشد.

موفق باشید؛
حمید رضا نیرومند


[ارسال شده در مورخه : سه شنبه، 22 بهمن، 1392 توسط Hamid]
[ #اطلاعیه‌های آفتابگردان]



بازدیدها از این مطلب: 5696 بار   امتیاز متوسط : 0  تعداد آراء: 0   امتیاز دهید:

نظرات طرح شده

نام: [ کاربر جدید ]
ایمیل:

نظر:


اجازه استفاده از تگهای HTML را ندارید


جمع عدد 11 با 15 را در كادر زیر وارد نمایید:
(این كار برای جلوگیری از فعالیت موتورهای اسپمر است)


* توجه: نظر شما بعد از بررسی، نمایش داده خواهد شد.

جواد                توسط جواد در مورخه : چهارشنبه، 23 بهمن، 1392(لینک نظر)
آقای مرتضی‌پور

مبــــــــــــــــــــــــــــــــــــــــــــــارکه


[ ارسال جوابیه ]


مهندس طلبه (امتیاز : 0)(لینک نظر)
توسط مهندس طلبه در مورخه : چهارشنبه، 23 بهمن، 1392
سلام علیکم

اولا از اقای نیرومند بابت ایجاد این رقابت تشکر میکنم.

دوما به اقای مرتضی‌پور تبریک میگم،ان شاالله در همه عرصه ها موفق باشند

یاعلی مددی


[ ارسال جوابیه ]


فرهاد مرتضی پور (امتیاز : 0)(لینک نظر)
توسط فرهاد مرتضی پور در مورخه : چهارشنبه، 23 بهمن، 1392
سلام



از همه دوستان ممنونم

از آقای نیرومند تشکر میکنم

مسئله بسیار خوبی بود



شاد باشید


[ ارسال جوابیه ]


[بدون موضوع]                توسط msdn در مورخه : چهارشنبه، 23 بهمن، 1392(لینک نظر)
آقا خیلی وقت کم بود من چون قبلش پروژه قبول کذدم حتی وقت نکردم الگوریتمم رو روی کامپیوتر بیارم. یکی دیگه مسابقه بذارید. خواهشن.


[ ارسال جوابیه ]


ایمان                توسط ایمان در مورخه : چهارشنبه، 23 بهمن، 1392(لینک نظر)
واقعاْ ۳۰۰ هزارتا شد!!!!!!!!!!!!!!!!!!!

مسابقه جالبی بود

ممنون


[ ارسال جوابیه ]


RezaSi                توسط RezaSi در مورخه : چهارشنبه، 23 بهمن، 1392(لینک نظر)
اون فایل PDF که از Wiki بود ... یعنی دقیقا این الگوریتم رو فقط کافی بود کدش کنن ! :) ... لطفا اگه می خواین از این مسابقه ها بزارید سوالایی بزارید که عینا الگوریتم مشخص نداشته باشن .. یکمم فکر بخوان :) ... سوالای ACM مناسب به نظر می رسن ...



موفق باشید آقای نیرومند ...


[ ارسال جوابیه ]

    Re: RezaSi (امتیاز : 1)
    توسط Hamid در مورخه : چهارشنبه، 23 بهمن، 1392
    RezaSi جان، خوب اگر فکر می‌کنید فهمیدن اینکه این مسأله با اون الگوریتم حل می‌شه ساده بوده، زودتر می‌گفتید، جایزه رو به شما می‌دادیم. یا اگر فکر می‌کنید کدنویسی‌ش ساده‌ست می‌تونید کد گامل‌تر رو بنویسید...

    به هر حال، چشم. دفعه بعد اگر خواستیم مسابقه تشکیل بدیم، می‌گیم شما مسأله رو طرح کنید.


    [ ارسال جوابیه ]


مهدی (امتیاز : 0)(لینک نظر)
توسط مهدی در مورخه : جمعه، 25 بهمن، 1392
سلام

استاد یه مطلب در مورد سرور مجازی سایت کم داره vps سایت های ارائه دهنده ایرانی هزینه بالای میگیرن چون یه جورای واسطه هستند و... هزینه بالا رفته

دوم هم اینکه سایت های ارائه دهند سرور هم بیش از اندازه و ظرفیت سرور سایت میارن روش -البته نوع مجازی سازی هم مهمه که در خانواده xen و hyper-v رم و سی پی یو رو نمیتوان بیش از اون چیزی که سرور داره تعریف کن بدین ترتیب از رم و سی پی یو ( اختصاصی هست رم و سی پی یو)خیال ادم راحت میشه ، اما تو open vs اینطوری نیست و اشتراکی هست

اگه ما از خود دیتاسنترهای خارجی سرور مجازی بگیریم مثلا دیتاسنتر ovh

چه مزیت و چه دردسرهای داره (کارت اعتباری برای پرداخت موردی نداره موجوده)

باسپاس فراوان


[ ارسال جوابیه ]


امین شفیعی (امتیاز : 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 جوابش رو میده و هر بار هم که تابع بازگشتی ما با عدد بعدی فراخونی میشه از اعداد ما مثل حالت فاکتوریل مانند کم میشه :)

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

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

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

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

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

موفق باشید.

امین شفیعی;


[ ارسال جوابیه ]

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

    ممنون از لطفت و اینکه سر می‌زنی. ما کاربران با استعدادی که گردن آفتابگردان حق داشته باشند رو فراموش نمی‌کنیم ;)



    در مورد الگوریتمت هم ممنون. جالب بود و البته فکر می‌کنم الگوریتم Back Tracking هم همینطور که توضیح دادی عمل می‌کنه. یعنی اون هم بازگشتیه و ورودی‌هاش همین‌هاست که گفتی...

    به هر حال، ای کاش خودم یا یه نفر دیگه فرصت پیدا کنیم یک الگوریتم که به جواب نهایی برسه رو پیاده‌سازی کنیم و ببینیم واقعاً چند ترکیب از سوره‌های قرآن رو می‌شه پیدا کرد که جمعشون ۱۰۰ بشه؟


    [ ارسال جوابیه ]