مقدمه

به‌ نام خدا، سلام!

مسیر یادگیری در کوئرا کالج

آنچه خواهید دید!

توضیحاتی در مورد شبه‌کدها

طرح درس، گواهی و  امتیازات

بزن بریم!

۱. ورود به دنیای الگوریتم‌ها

اهداف فصل

خصوصیات الگوریتم

الگوریتم چیست

مراحل حل مسئله

مقایسه الگوریتم‌ها

زمان اجرای برنامه

شمارش عملیات‌ها

جست‌وجو در دنباله ۱

جست‌وجو در دنباله ۲

تبدیل به حسابی ۱

میانه صحیح

تبدیل به حسابی ۲

۲. تحلیل زمانی الگوریتم‌ها

عدم اهمیت ضریب‌ها

تعریفِ ابتداییِ اردر

چند مثال از اردر

مقایسه اردر‌ها

بزرگ‌ترین زیربازه ۱

بزرگ‌ترین زیربازه ۲

نیمه مرتب

شمارش مثلث‌ها ۱

شمارش مثلث‌ها ۲

شمارش مثلث‌ها ۳

مرتب‌سازی و تحلیل زمانی

مرتب‌سازی حبابی

۳. الگوریتم‌های استقرایی

استقرای ریاضی

استقرای قوی

مرتب‌سازی انتخابی

مرتب‌سازی درجی

بزرگ‌ترین زیربازه ۳

الگوریتم هورنر

مجموع ارقام

۴. الگوریتم‌های بازگشتی

آشنایی اولیه

چند مثال ساده

پشته فراخوانی

روش‌های تحلیل توابع بازگشتی

مثال‌های تحلیل توابع بازگشتی

دنباله بازگشتی

فرکتال

ب.م.م

برج هانوی

کد گرِی

𝑛تایی مرتب

تناظر زیر مجموعه‌ها با اعداد دودویی

بخش‌بندی

۵. الگوریتم‌های حریصانه

خریدن کتاب

زندگی کارمندی

پمپ بنزین

کاف‌کیک

انرژی خور

تخته

بیشترین تعداد بازه

اشتباهات رایج

آبمیوه فروشی حریصانه

جاسوسی

تمرین‌های دوره‌ای ۱

استارت-آپ باکلاس

پله‌نوردی

علسوپا

پالیندرومینیا

ضرب متناظر دو دنباله

بسته‌های شکر

تعمیر پشت‌بام

شرکت پالایش و پخش نخود در برره

مساوات

۶. برنامه‌نویسی پویا

دومینوار

بزرگترین زیر‌بازه

آجرچینی

بزرگترین زیر جدول

انتخاب

بیشینه مسیر جدول

چالش مسیر‌یابی

مسئله‌ی کوله پشتی

یا همه یا هیچ یا یکی

بهینه‌سازی حافظه کوله پشتی

بزرگ‌ترین زیردنباله مشترک

ضرب ماتریس

بزرگ‌ترین زیردنباله اکیدا صعودی

بریم توچال!

۷. الگوریتم‌های پس‌گرد

مسائل پس‌گرد

تعداد جایگشت

دنباله‌ پس‌گردنی

سودوکو

𝑛 وزیر

یک اسب

۸. روش تقسیم‌ و حل

ادغامات

محاسبهٔ توان

تابع توان‌دار

قلّه

جستجوی دودویی

بشمر!

نابه‌جایی

مرتب‌سازی سریع

pivot کجاست؟

دسته به دسته

تمرین‌های دوره‌ای ۲

مرد مالیاتچی و جاعل

تعداد ۱۱ بخش پذیرها (۲)

مثلث‌ها

خواب پوپک

باقر حال نداره ولی پول داره

تکامل

انتقام از TA‌ سخت‌گیر

رژیم سخت

دنباله تورج‌پسند

سینما، سینما

بازرگانی سوکرات و پسران

شیر

متوازی‌الاضلاع ممنوع!

آجر چینی (۲)

بازار موبایل

منظره‌ای به‌ یاد ماندنی

۹. ساختمان‌داده‌ها

پشته

پرانتز‌گذاری معتبر

هیستوری

صف

الگوی من کیه؟

صف دو‌طرفه

آرایه پویا

لیست پیوندی

پیاده‌سازی ساختمان‌داده‌های قبلی با لیست پیوندی

ویرایشگر متن

درخت هرمی

کافه‌ سالاد

میانه‌روی

درخت دودویی جستجو و ساختار مجموعه‌ای

برنامه‌ریزی فرودگاه

برش کیک

پول یا وجدان؟

۱۰. پیش‌پردازش و بهینه‌سازی

مجموع جزئی

خواستار

مجموع جزئی در ماتریس

مربع

کادوی مشتی

درخواست مینیمم عدد در بازه

کمینه در بازه

مرتب‌سازی درجی رشته‌ها

مجموع جزئی در آرایه متغَیّر

بیشینه در آرایه متغیّر

۱۱. الگوریتم‌های گراف

گراف

دی‌اِف‌اِسِ پیش‌گو

بی‌اِف‌اِسِ مسیر‌یاب

پیدا کردن دور در گراف‌ها

گراف‌های دوبخشی

پیدا کردن کمر گراف

مسافرت

پادشاه

دوست‌یابی

جدول

قطـــر

تمرین‌های دوره‌ای ۳

وسیله کمک آموزشی

زینی

بتایپ

قطار کامیابی

هیچ‌وقت مغرور نشو!

دنباله متوازن

مرتفع

گراف قرمز و آبی

ترور

میان‌ترم هندسه

اسم فامیل

صفا

مساحت محصور

عدد روی تخته

دنباله

کمینه بیشینه اختلاف!

ضمیمه

منابع خوب

نکاتی درباره باقی‌مانده و سرریز کردن (Overflow)

تحلیل الگوریتم‌ها

پیاده‌سازی ساختمان‌‌داده‌ها بخش اول

پیاده‌سازی ساختمان‌‌داده‌ها بخش دوم

مرتب‌سازی در زبان ++C

استفاده از pair در ++C

ساختمان‌های داده در ++C

کتابخانه‌ها و توابع پرکاربرد ++C

روش‌های دیگر خواندن ورودی در ++C

پرکابردهای پایتون بخش اول

پرکابردهای پایتون بخش دوم

در این دوره با بخش‌های زیادی تحت عنوان **شبه کد** یا *Psuedo Code* برخورد می‌کنید. این شبه کد‌ها در بخش‌های خاکستری رنگ به صورت زیر می‌آیند:

```
This is a "Psuedo Code"
```
هدف این شبه‌کدها خلاصه‌‌سازی و ارائه‌ی روند الگوریتمی‌ای است که برای حل مسئله به آن احتیاج داریم. معمولاً با خواندن این شبه‌کدها نوشتن برنامه با زبان مورد نظر‌تان راحتتر خواهد شد.

هر شبه‌کد قرار است تابعی خاص یا روندی خاص را پیاده‌سازی کند. به عبارتی هر شبه‌کد یک یا چند **ورودی** و یک یا چند **خروجی** یا تعدادی پردازش دارد.

# بخش توضیحات شبه‌کد

بخش‌ بالایی شبه‌کدها به **هدف و توضیحات**، **ورودی** و بعضاً نامگذاری شبه‌کد اختصاص یافته‌است.

```
> my_pusedo_code(inputs)
input1 : explanation of input1
input2 : explanation of input2
.
.
.
gets all the inputs and processes them
------
```
همانطور که‌ می‌بینید بخش بالایی `------` مربوط به توضیحات و هدف شبه کد است و حالت انتزاعی دارد یعنی صرفاً ورودی‌ها و خروجی‌ای که قرار است ارائه شود در این بخش معرفی می‌شود و هیچ‌ کاری به اتفاقی که داخل شبه‌کد می‌افتد نداریم.

# بخش پردازش‌ها

پس از توضیحات پردازش‌های شبه کد به صورت شبه‌دستور هایی می‌آید. این *شبه دستورها* مانند دستورها در اکثر زبان‌های برنامه‌نویسی عمل می‌کنند و یکسری دستورات کنترلی داریم که در ادامه معرفی خواهیم کرد.

دستورات خط به خط هستند و هر دستوری با شماره‌ای مشخص شده‌است. برای مثال در شبه کد زیر ابتدا `operation1`و سپس `operation2`و بعد از آن `operation3` اجرا می‌شود.

```
> sequential_psuedo_code
this psuedo code introduces the sequential way that a
psuedo code is running
-------------------------------------------------------
1. operation1
2. operation2
3. operation3
```
# دستورات کنترلی

هر خط از بخش پردازش‌ها یک دستور کنترلی است که در اینجا به آن می‌پردازیم. در طول دوره با تک تک این دستورات آشنا خواهید شد.

## انتساب یا مقداردهی

با استفاده از عملگر `<-` یا `:=` انتساب می‌کنیم. انتساب به این معنی است که یک متغیر یا `container`یک مقدار خاصی می‌گیرد. برای مثال اگر بنویسیم `a := 2` یا `a <- 2` در واقع متغیر `a` از آن خط به بعد مقدار `2` به آن اختصاص داده‌ می‌شود.

اگر بنویسیم `a := a / 2` یا اگر بنویسیم `a <- a / 2` مقدار `a` برابر **مقدار قبلی `a`** تقسیم بر ۲ می‌شود. برای مثال اگر تا قبل از اجرای این خط مقدار `a` برابر ۴ بود، پس از آن برابر ۲ می‌شود.

```
> value_assignment
this psuedo code shows how values can be assigned
--------------------------------------------------
1. a <- 2
2. b <- 3
3. a <- a + 1
4. a <- b - 2
```
در جدول زیر می‌توانید مقادیر داده‌شده به هر متغیر را پس از هر خط ببینید:

| شماره‌ خط | a |      b     |
|:--------:|:-:|:----------:|
|     1    | 2 | تعریف نشده |
|     2    | 2 |      3     |
|     3    | 3 |      3     |
|     4    | 1 |      3     |

## شرط
هر شرط به صورت زیر تعریف می‌شود:

```
if "conditional statement":
	operations
else:
	operations
```
که در بخش `conditional statement` هر عبارت منطقی‌ای را می‌توانید بنویسید. برای مثال فرض کنید قرار است اگر ساختمان‌داده یا متغیر `a` خالی نبود یک سری دستور اجرا کنید. در این‌صورت می‌توانید چنین شبه‌کدی بزنید:

```
> psuedo_code_with_conditionals
S : a data-structure or variable that may or may not
 be empty
this pusedo code checks if data structure S is empty
or not
----------------------------------------------------
1. if S is not empty:
2.	output "S is not empty
3. else:
4.	output "S is empty"
```
همانطور که می‌بینید `S is not empty` یک گزاره‌ی شرطی منطقی است که یا **درست** است یا غلط. اگر درست باشد `S is not empty` خروجی تابع خواهد شد و در غیر این‌صورت `S is empty` خروجی تابع خواهد بود.

همچنین می‌توانید گزاره‌هایی به صورت `S != NULL` یا `S != empty` نیز نوشته‌شود. صرفاً مهم این است که مفهوم گزاره‌ای به شکل درست یا غلط رسانده شود.

در شبه‌کدها می‌توانید از ساختارهایی مثل `elseif` نیز استفاده کنید و به معنای این است که در صورتی که شرط‌های قبلی برقرار نبود ولی شرط کنونی برقرار بود یکسری عملیات قرار است انجام شود.

## حلقه
فرض کنید می‌خواهیم روی همه‌ی چیز‌هایی که خصوصیات خاصی دارند کاری انجام دهیم. برای این‌کار از این ساختار استفاده می‌کنیم. برای مثال فرض کنید می‌خواهیم مجموع تمامی اعداد زوج از ۱ تا $n$ را خروجی دهیم. سه شبه کد می‌بینید که هر کدام‌شان مفهوم مورد نظر را می‌رسانند و درست هستند.

```
> calculate_sum_of_even_numbers (implementation 1)
n : a number which is the upper bound of the numbers
    we are summing up
this psuedo code calculates the sum of all even numbers
from 1 to n
-------------------------------------------------------
1. sum := 0
2. for all even numbers less than or equal to n like x:
3. 	sum := sum + x
4. output sum
```
```
> calculate_sum_of_even_numbers (implementation 2)
n : a number which is the upper bound of the numbers
    we are summing up
this psuedo code calculates the sum of all even numbers
from 1 to n
-------------------------------------------------------
1. sum := 0
2. for x even from 1 to n:
3. 	sum := sum + x
4. output sum
```
توجه کنید صرفاً مهم است پس از `for`یک متغیر یا متغیر‌هایی تعریف کنیم که این متغیر یا متغیر ها خاصیت مورد نظر را داشته‌باشند. برای مثال در اینجا `x` متغیر مورد نظر است.

هم چنین می‌توانیم با استفاده از ساختار شرط و یک ساختار حلقه‌ی ساده این‌کار را بکنیم:

```
> calculate_sum_of_even_numbers (implementation 3)
n : a number which is the upper bound of the numbers
    we are summing up
this psuedo code calculates the sum of all even numbers
from 1 to n
-------------------------------------------------------
1. sum := 0
2. for x from 1 to n:
3. 	if x is even:
4. 		sum := sum + x
5. output sum
```
همچنین می‌توانیم ساختاری به نام `while`تعریف کنیم که تا وقتی شرطی برقرار باشد یکسری عملیات را انجام می‌دهد.

```
while conditional statement:
	operations
```
همانند `if` می‌توانیم پس از `while`یک عبارت شرطی استفاده کنیم و تا زمانی‌که این شرط برقرار باشد `operations` اجرا می‌شود. برای مثال همان شبه‌کد قبلی را می‌توانیم به صورت زیر بازنویسی کنیم:

```
> calculate_sum_of_even_numbers (implementation 4)
n : a number which is the upper bound of the numbers
    we are summing up
this psuedo code calculates the sum of all even numbers
from 1 to n
-------------------------------------------------------
1. sum := 0
2. x := 0
3. while x <= n:
4.     sum := sum + x
5. 	x := x + 2
6. output sum
```

## کامنت

این دستورات در واقع دستور نیستند و صرفاً برای رفع ابهام ظاهر می‌شوند تا تکه‌ای از شبه‌کد را توضیح بیشتری بدهند. مثلاً در شبه کد زیر فرض کنید `complex piece of psuedo code` مجموعه دستوراتی است که پیچیده‌اند. در این‌صورت قبل از آن در قالب کامنت توضیحاتی راجع‌ به آن بخش از کد می‌دهیم:

```
> introduce_comments_in_psuedo_code
this psuedo code contains a complex piece of operations
with a comment documenting it
-------------------------------------------------------
1. // this is a comment:
2. // the psuedo code you see in the followingdoes a
3. // complex algorithm
4. complex operation1
5. complex operation2
.
.
.
```
برای مثال در شبه کد بالا عملیات از خط چهارم شروع می‌شوند و توضیحات اضافی ارزش الگوریتمی خاصی ندارند.

# تعریف تابع به وسیله‌ی شبه‌کد

می‌توانیم توابع مختلف را با استاندارد‌ها زیر به صورت شبه‌کد تعریف کنیم. کافیست پس از اسم آن تابع ورودی هایش را در پرانتز قرار دهیم و در شبه‌کد‌های دیگر از آن استفاده کنیم. با چنین ساختار‌هایی ممکن‌است در طول دوره برخورد کنید.

برای مثال در شبه‌کد زیر جمع اعداد زوج از ۱ تا $n$ را به صورت تابع تعریف می‌کنیم و مقدار `sum` را `return` می‌کنیم. در اینصورت تابع این مقدار را **بر می‌گرداند**.

```
> calculate_sum_of_even_numbers(n)
n : a number which is the upper bound of the numbers
    we are summing up
this psuedo code function calculates the sum of all 
even numbers from 1 to n and returns it
-------------------------------------------------------
1. sum := 0
2. x := 0
3. while x <= n:
4.      sum := sum + x
5.      x := x + 2
6. return sum
```
حال می‌توانیم از این مقدار **برگردانده‌شده** در شبه‌کد‌های دیگر نیز استفاده کنیم.

```
> psuedo_code_that_is_using_function
x : a number
y : another number
this psuedo code gets a number 'x' and assigns sum of
all even numbers less than or equal to 'x' in 'y'
-----------------------------------------------------
1. y := calculate_sum_of_even_numbers(x)
```
<details class="blue">
<summary>
نکاتی برای نوشتن شبه‌کد
</summary>

* بهتر است همه‌ی شبه‌کد ها به صورت تابع نوشته‌شوند. 

* اگر از ساختار خاصی استفاده می‌کنید این ساختار را در تمام طول دوره حفظ کنید برای مثال اگر از `:=` برای نوشتن یک شبه‌کد استفاده می‌کنید، در تمام طول دوره از همین علامت استفاده کنید و از `<-` استفاده نکنید.

</details>

<details class="red" open>
<summary>**هشدار**</summary>
زمانی‌که راه‌حل شبه‌کد را می‌بینید، شاید وسوسه شوید و بخواهید به جای پیاده‌سازی راه‌حل، شبه کد را به‌صورت مستقیم و تنها با تغییر ساختار زبانی آن ارسال کنید. این کار باعث ضعف در درک سوال و راه‌حل آن شده و همچنین می‌تواند شما را با باگ‌هایی مواجه کند که رفع آن‌ها زمان بیشتری از درک سوال و سپس پیاده‌سازی یافته‌هایتان خواهد گرفت. 

در طرف مقابل، ارسال شبه‌کد به مدل‌های هوش مصنوعی برای تبدیل آن به زبان‌های برنامه‌نویسی، می‌تواند در یادگیری شما اختلال ایجاد کند. **هدف** تمرین‌ها، تثبیت مباحث برای خودتان بوده و استفاده از این ابزارها برای انجام برنامه‌نویسی به‌جای شما، می‌تواند شما را از **اهدافتان دور کند**.

پیشنهاد ما این است که ابتدا، شبه کد را مطالعه و درک کنید؛ سپس، خودتان دست به کد شوید و آن را پیاده‌سازی کنید. طبیعی است که برای درک سوال یا حتی انجام برخی از دیباگ‌ها، ابزارهای هوش مصنوعی می‌توانند به شما کمک کنند و استفاده از آن‌ها توصیه نیز می‌شود؛ اما فراموش نکنید که این شما هستید که باید الگوریتم را درک کنید، نه هوش مصنوعی! 
</details>

الگوریتم پیشرفته و ساختمان‌داده‌ها