صفحه‌ی اصلی

صفحه‌ی شخصی مسعود اقدسی‌فام
الگوریتمستان - برنامه‌نویسی و طراحی الگوریتم
RSS Feed
● وب‌گاه مجموعه سوالات منطقه‌ای و جهانی مسابقات برنامه‌نویسی ACM-ICPC، با امکان ارسال پاسخ و بررسی جواب.
● علاقه‌مندان به شرکت در مسابقات برنامه‌نویسی و حل سوالات الگوریتمی می‌توانند از این وب‌گاه معتبر به همراه کتاب‌های معرفی شده جهت تمرین و آمادگی بیشتر استفاده کنند.
امروز: شنبه، ۸ فروردین ماه ۱۳۹۴ ، کاربران حاضر در وب‌گاه: ۲ کاربر
جستجو در نوشته‌های وب‌گاه:   
برنامه‌نویسی ++C
برنامه‌نویسی ++C
مباحث آموزشی زبان برنامه‌نویسی ++C
الگوریتم‌ها
الگوریتم‌ها
الگوریتم‌ها، روش‌های طراحی الگوریتم و حل مسأله
ساختمان داده‌ها
ساختمان داده‌ها
مفاهیم ساختمان داده‌ها و کاربردهای آنها
مسابقات برنامه‌نویسی
مسابقات برنامه‌نویسی
حل مسأله و آمادگی مسابقات برنامه‌نویسی
کتاب الکترونیکی
کتاب الکترونیکی
معرفی کتاب‌های الکترونیکی
محاسبات ریاضی
محاسبات ریاضی
معرفی و بررسی الگوریتم‌های محاسباتی
اشتراک‌گذاری در LinkedIn      Cloob      اشتراک‌گذاری در Twitter      اشتراک‌گذاری در Facebook      اشتراک‌گذاری در فیس‌نما

Google Plus      ارسال با پست الکترونیک      اشتراک‌گذاری در Digg      ارسال با Yahoo Messenger      اشتراک‌گذاری در StumbleUpon


الگوریتمستان
عناوین بخشی از مباحث پرکاربرد در سوالات مسابقات برنامه‌نویسی
الگوریتمستان
بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه‌ی آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
الگوریتمستان
آشنایی با الگوریتم دایکسترا برای یافتن کوتاهترین مسیر تک‌مبدأ در گراف وزن‌دار بدون یال منفی با قطعه کد به زبان ++C
الگوریتمستان
آشنایی با الگوریتم استراسن برای محاسبه‌‌ی حاصلضرب ماتریس‌ها
الگوریتمستان
آشنایی با کلاس‌های حافظه و کاربرد آنها در زبان ++C
الگوریتمستان
معرفی کتاب Art of Programming Contest برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود
الگوریتمستان
بررسی روش‌های بسط لاپلاس، گاوس، فرمول تحویل و ساروس، برای محاسبه‌ی دترمینان ماتریس مربعی، و پیچیده‌گی زمانی آنها


الگوریتمستان
معرفی الگوریتم جستجوی اول سطح (BFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C
الگوریتمستان
آشنایی با الگوریتم دایکسترا برای یافتن کوتاهترین مسیر تک‌مبدأ در گراف وزن‌دار بدون یال منفی با قطعه کد به زبان ++C
الگوریتمستان
معرفی کتاب Programming Challenges برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود
الگوریتمستان
معرفی کتاب Concrete Mathematics برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود
الگوریتمستان
بررسی مسأله‌ی Simple Addition از سوالات آمادگی مسابقات برنامه‌نویسی
الگوریتمستان
معرفی متغیرهای مرجع در زبان برنامه‌نویسی ++C و آشنایی با مهمترین کاربردهای آنها
الگوریتمستان
آشنایی با روش حریصانه و کاربردهای آن مانند مسأله‌ی خرد کردن پول

مسأله

    ساختمان جدید دپارتمان مهندسی کامپیوتر تنها شامل آسانسور بوده و پله ندارد. برای دسترسی سریع و مناسب به اتاق‌ها و کلاس‌های طبقات مختلف، آسانسورها به گونه‌ای تنظیم شده‌اند که تنها در طبقات مشخصی توقف داشته باشند؛ مثلا تعدادی تنها در طبقات زوج و تعدادی دیگر تنها در طبقات فرد. دکمه‌های داخل آسانسور و کنار ورودی آسانسور نیز تنها برای همین طبقات از پیش مشخص شده فعال هستند. این ایده دسترسی سریع و مناسب به طبقات ساختمان را برای برخی افراد فراهم می‌کند؛ به عنوان نمونه اعضای هیئت علمی دسترسی مستقیم به طبقات اتاق‌های خود دارند. اما در حالت کلی باعث سردرگمی می‌شود. اگر شخصی بخواهد از طبقه‌ای به طبقه‌ی دیگری برود، ممکن است هیچ آسانسوری در هر دوی آنها توقف نداشته باشد و شخص مجبور به تعویض آسانسور گردد. در چنین شرایطی این سوال پیش می‌آید که کدام آسانسور (یا آسانسورها) باید انتخاب شوند و کدام انتخاب‌ها شخص را در زمان کمتری به مقصد می‌رساند. اگر مسیر حرکت شخص از طبقه‌ی i به طبقه‌ی j به صورت $ i = f_1 \rightarrow f_2 \rightarrow f_3 \rightarrow \cdots \rightarrow f_k = j $ نمایش داده شود، عبارت $ \sum_{r=1}^{k-1} \vert f_i - f_{i+1} \vert $ زمان لازم برای رسیدن به مقصد از طریق آن مسیر است. برنامه‌ای بنویسید که افراد را در استفاده‌ی بهتر (در زمان کمتر) از آسانسورها یاری کند.

ادامه ...

کتاب Concrete Mathematics: A Foundation for Computer Science اثری با موضوع مفاهیم اولیه‌ی ریاضیات پیوسته (CONtinuous mathematics) و ریاضیات گسسته (disCRETE mathematics) به قلم رونالد گراهام، دونالد کنوت و اُرِن پاتاشنیک - از دانشمندان بزرگ علوم ریاضیات و کامپیوتر - است . در این کتاب از بیان متفاوتی نسبت به نوشتار عموم کتاب‌های آموزش ریاضی استفاده شده و مفاهیم پایه‌ای محاسباتی علم کامپیوتر به زبان ساده و گیرا توضیح داده شده است. این مفاهیم پیش‌نیاز حل بسیاری از مسائل کامپیوتری، ریاضی و محاسبات علمی هستند. به همین دلیل، مطالعه‌ی آن به علاقه‌مندان برنامه‌نویسی، بویژه شرکت‌کنندگان المپیادهای کامپیوتری و مسابقات برنامه‌نویسی توصیه می‌شود.

ادامه ...

الگوریتم پیمایش اول سطح یا جستجوی اول سطح (Breadth First Search - BFS) از جمله الگوریتم‌های مشهور پیمایش و جستجوی گراف است که در حل مسائل الگوریتمی و هوش مصنوعی کاربرد دارد. این الگوریتم برای پیمایش و جستجوی گراف از یک صف برای نگهداری ترتیب جستجو استفاده می‌کند.

    الگوریتم BFS با وارد کردن گره مبدأ به صف پردازش شروع شده و تا خالی نشدن این صف مراحل زیر را تکرار می‌شود:

    1- عنصر جلوی صف را به عنوان گره جاری انتخاب و از صف حذف کن.

    2- گره جاری را پردازش کن.

    3- گره‌های مجاور گره جاری که پردازش نشده و در صف پردازش نیز قرار ندارند به این صف اضافه کن.

    منظور از پردازش، هر عملی روی گره است که پیمایش یا جستجو به آن نیت صورت گرفته است.

ادامه ...


صف اولویت‌دار (یا صف اولویتی - Priority Queue) از جمله ساختمان داده‌های بسیار پرکاربرد است. در صف عادی از تکنیک FIFO - مخفف First In First Out - استفاده می‌شود. در این تکنیک، مثل یک صف نانوایی، داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند. بنابراین اولین داده‌ی ورودی، اولین داده‌ی خروجی نیز خواهد بود. اما در صف اولویت‌دار برای هر داده، اولویتی - نه لزوما منحصربفرد - مشخص می‌شود. صف اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستم عامل کامپیوتر هم برای مدیریت پردازش‌ها از صف‌های اولویت‌دار استفاده می‌کند.

    به عنوان مثال، فرض کنید پردازش‌های زیر در انتظار اختصاص CPU به خود هستند:

      

جدول درخواست پردازنده

ادامه ...

آرایه‌های دو بعدی کاربردهای بسیاری از جمله جداول و ماتریس‌ها دارند. اهمیت تعریف آرایه‌های پویای دو بعدی کمتر از آرایه‌های یک بعدی نیست. آرایه‌های پویای دو بعدی یک ویژگی جالب در مقایسه با آرایه‌ی ایستا دارند. شما با تعریف پویای آرایه‌های دو بعدی می‌توانید جداول غیرمستطیلی تشکیل دهید. در واقع وقتی آرایه‌های دو بعدی را به صورت پویا ایجاد می‌کنید، این اختیار را دارید که تعداد ستون‌های هر ردیف را متفاوت انتخاب کنید.

    به قطعه کد زیر توجه کنید:

int **table;

cin >> n;

table = new int*[ n ];

int i, j;

for ( i = 1 ; i <= n ; i++ )

ادامه ...

معمای هشت وزیر از جمله مسائل کلاسیک مباحث طراحی الگوریتم است که در حالت کلی‌تر با عنوان معمای n وزیر یا معمای چند وزیر مطرح می‌شود.

    

برای افرادی که با بازی شطرنج آشنایی ندارند

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

      

معمای هشت وزیر

ادامه ...

دترمینان ماتریس مربعی - که به صورت |A| یا ( det( A نمایش داده می‌شود - یکی از مفاهیم مشهور جبر خطی است که کاربردهای بسیاری در علوم مختلف دارد. امکان محاسبه‌ی سریع دترمینان یک ماتریس با ابعاد بزرگ، بحث مهمی است که در ادامه سه روش محاسباتی رایج و پیچیده‌گی زمانی آنها مرور خواهند شد.

    طبق تعریف دترمینان، اگر اندازه‌ی ابعاد ماتریس مربعی یک باشد (n = 1)، دترمینان همان مقدار تک‌عضو آن است. یعنی:

      

\[ det( \begin{bmatrix} a \end{bmatrix} ) = \vert \begin{bmatrix} a \end{bmatrix} \vert = a \]

      

    اما اگر مرتبه‌ی ماتریس بزرگتر از یک باشد (n > 1)، دترمینان را به یکی از روش‌های زیر می‌توان محاسبه کرد.

ادامه ...