دوستان عزیز سلام

وبلاگ برنامه نویسی و طراحی الگوریتم با مطالب متنوعی در زمینه های مختلف برنامه نویسی در خدمت شماست. برای مشاهده مطالب بروز شده از آدرس زیر استفاده کنید:

WWW.AACHP.BLOGFA.COM

به امید دیدار

سلام بر رفقا

بنا بر دلايلی مجبور به اسبابکشی از اينجا هستم. شما می تونيد مطالب جديد رو تو خونه جديد بخونيد.

فعلا خدانگهدار

WWW.AACHP.BLOGFA.COM 

سلام بر دوستان عزيز

يه تعداد از بچه ها سوالات ACM رو درخواست کرده بودن که می تونن امروز به خواستشون برسن. اميدوارم مفيد واقع بشه.

سوالات جهانی ۲۰۰۰

سوالات جهانی ۲۰۰۱

سوالات جهانی ۲۰۰۲

سوالات جهانی ۲۰۰۳

سوالات جهانی ۲۰۰۴

سوالات جهانی ۲۰۰۵

خوب و خوش و خرم باشيد

سلام بر دوستان

دانش آموزای ریاضی و علاقه مندای ریاضیات تعریف اولیه دترمینان یک ماتریس مربعی از مرتبه n رو می دونن:

یا

که دترمینان ماتریس مربعی مرتبه n رو به دترمینان n تا ماتریس از مرتبه n-1 تبدیل می کنه و البته برای مرتبه 2 داریم:

حالا فرض کنید تابعی نوشتیم که دترمینان یک ماتریس مربعی مرتبه n رو به روش خودفراخوانی (بازگشتی) محاسبه می کنه. فکر می کنید اگه n=20 باشه ، این تابع چند بار باید خودش را فرابخونه تا بتونه دترمینان رو حساب کنه؟ مرحله توقف تابع بازگشتی رو هم n=2 در نظر بگیرید یعنی برای n=2 تابع مستقیما دترمینان رو محاسبه می کنه.

فکر می کنید این عدد چقدر بزرگ باشه؟ بیاین با هم حساب کنیم:

فرض کنیم T(n) تعداد فراخوانیها برای حساب کردن دترمینان ماتریس مرتبه n باشه. واضحه کهT(2)=1  و همینطور:

T(3)=3T(2)+1=4

T(4)=4T(3)+1=17

برای حساب کردن دترمینان ماتریس 3 در 3 یه بار تابع رو با n=3 فراخوانی می کنیم . اون هم خودش سه بار تابع رو برای n=2 فراخوانی می کنه. پس رو هم 4 بار تابع فراخوانی می شه و ...

با یه حساب سر انگشتی می تونید به این نتیجه برسید که اگه n به اندازه کافی بزرگ باشه (مثلا n>10) میشه گفت:

T(n)=n!(e-2)

یعنی مثلا برای n=20 تابع باید بیشتر از 1.7 میلیارد میلیارد بار(یه 17 با 17 تا صفر جلوش) خودش رو فراخوانی کنه تا بتونه دترمینان رو حساب کنه!!!!!! اصطلاحا گفته می شه که این روش از مرتبه O(n!) هست.تازه اینها فقط تعداد فراخوانیها رو نشون میده.اینکه هر بار محاسبات توی تابع چقدر طول می کشه و چقدر حافظه نیاز هست بماند ، که اگه بخوایم اونارم حساب کنیم عددمون سر به فلک می کشه!!!

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

یکی از روشا استفاده از الگوریتم گاوس-جردن برای حل دستگاه معادلاته که در واقع  اصلیترین روش به حساب می یاد و فوق العاده با صرفه تر از روش قبلیه. اکثر شما با این روش آشنا هستین و فکر نکنم نیازی به توضیح اون باشه. فقط مختصرا بگم که روش کلی اون ساده کردن معادلات دستگاه با جمع کردن ضرایب مناسبی از اونها با همه ، تا ماتریس ضرایب به یه ماتریس همانی یا بالا مثلثی یا پایین مثلثی تبدیل بشه.

اما آیا روش دیگه ای وجود داره؟

اگه بخش ضمیمه کتاب «حساب دیفرانسیل و انتگرال و هندسه تحلیلی» نوشته «جرج بی. توماس و ...» رو که تو هر دانشگاه و کتابخونه ای پیدا می شه بخونید ، یه روش خیلی جالب برای محاسبه دترمینان ارائه شده که دترمینان ماتریس مرتبه n رو فقط به یه دترمینان از مرتبه n-1 تبدیل می کنه. روش جدید به این شکل هست که:

البته باید توجه کنید که تو هر مرحله درایه سطر و ستون اول باید غیر صفر باشه که اگه نبود می شه سطرها رو جابه چا کرد. اگه جابه جایی سطرهام اثر نداشت معنیش اینه که یه ستون داریم که همه درایه هاش صفره . پس دترمینان صفر میشه.

حالا اگه T(n) رو واسه این روش حساب کنیم (خودتون زحمتشو بکشین) به دست می یاد:

T(n)=( 2 n ^ 3 - 3 n ^ 2 + 7 n -12 ) / 6

(^ برای توان به کار رفته)

که گفته می شه این الگوریتم از مرتبه O(n^3) هست.

اگه n=20 باشه: T(20)=14928 که نشون میده این روش نسبت به روش اول فوق العاده کاراتره (15هزار کجا و 1.7 میلیارد میلیارد کجا !!!!) در ضمن محاسباتش هم نسبت به روش اول خیلی خیلی کمتره. ولی به پای روش گاوس – جردن نمی رسه.

خوب حالا فکر می کنید بتونید برنامه محاسبه دترمینان به روش سوم رو بنویسید؟بسم ا ... ما منتظریم.

موفق باشید

سلام

بعضی از دوستان می گن که نمی تونن لينک دانلود کتابهارو باز کنن. براشون يه پيشنهاد دارم:

از Google استفاده کنيد و برای جستجو بنويسيد:

"Thinking in C++" filetype:PDF 

عبارت رو دقيقا مثل بالا تایپ کنيد. اونجا می تونيد لينکهای دانلود رو پيدا کنيد.

موفق باشيد

سلام

در مورد پاسخ شماره ۱ بايد بگم که من چون خودم به ++C تسلط بيشتری دارم از اون استفاده کردم . ولی شما می تونيد از زبانهای ديگه استفاده کنيد.

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

منتظر مساله شماره ۲ که کمی (فقط کمی) سخت تر از قبليه ، باشيد.

سلام بر دوستان

چی شد پس؟

يعنی کسی مساله شماره ۱ رو نتونسته حل کنه؟

نا اميدم نکنيد.

در مورد ACM Contest چه می دانید؟

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

1- باید به یکی از زبانهای برنامه نویسی متداول و اعلام شده توسط کمیته اجرایی مسابقات تسلط کامل داشته باشند. این زبانها عموما C++ ، C و يا جاوا  می باشند.

سلام بر دوستان

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

منتظرم