الگوریتم‌های ساده ایجاد کنید

این یک متن ترجمه شده ماشینی است که ممکن است حاوی خطا باشد!

Quote

“الگوریتم”، کلمه‌ای که برنامه‌نویسان وقتی نمی‌خواهند توضیح دهند چه کاری انجام داده‌اند، از آن استفاده می‌کنند.

Algoritme?

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

یک الگوریتم یک تابع منطقی است که یک عملیات معین را انجام می‌دهد. بنابراین، از نظر فنی می‌توانید تابعی که دو عدد را با هم جمع می‌کند را “الگوریتم” بنامید، اما اغلب یک الگوریتم چیزی کمی پیچیده‌تر از آن است. اغلب از الگوریتم‌ها برای سریع‌تر کردن عملیاتی که زمان زیادی می‌برند استفاده می‌شود.

آیا باید در این تمرین‌ها از پایتون استفاده کنم؟

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

کتابخانه‌های داخلی؟

ایده در این تمرین‌ها این است که از استفاده از کتابخانه‌های داخلی یا توابع خاص پایتون اجتناب کنید. برای مثال، یک “خط فرمان” ساده برای معکوس کردن متن وجود دارد: text[::-1], اما در اینجا می‌خواهیم شما سعی کنید این‌گونه تمرین‌ها را بدون استفاده از آن حل کنید. ممکن است یک تابع داخلی را در صورتی که یافتن راه‌حل کمی دشوار باشد، اشاره کنیم. این با ❗ مشخص خواهد شد.

در عمل، باید کاملاً امکان‌پذیر باشد که همه این تمرین‌ها را با استفاده از if، for، while و عملیات لیست معمولی حل کنید.

چگونه یک الگوریتم را “طراحی” کنیم؟

اغلب اوقات، الگوریتم‌ها به صورت تکراری طراحی می‌شوند. این به چه معناست؟

1. ✅ ابتدا مسئله را به بخش‌های کوچک‌تر تقسیم کنید.

ابتدا به مهم‌ترین چیزی که برای عملکرد الگوریتم نیاز دارید فکر کنید
- آیا باید مقداری را برگرداند؟ یک boolean؟ یک لیست؟
- آیا به توابع کمکی نیاز دارم؟

2. ❓ آیا موارد خاصی وجود دارد؟

اگر یک لیست خالی یا متن خالی وارد کنید چه اتفاقی می‌افتد؟

3. ✅ با تلاش برای ساخت یک راه حل شروع کنید.

4. ✅ بررسی کنید که آیا الگوریتم در زمان اجرا به خوبی کار می‌کند

ورودی‌های بزرگتر را امتحان کنید، آیا زمان زیادی طول می‌کشد؟

5. ❓ به راه حل خود فکر کنید، آیا به تمام مراحلی که استفاده کرده‌اید نیاز دارید؟

آیا همه بررسی‌های if ضروری هستند؟
اگر بیش از یک حلقه for دارید، آیا راه‌های واضحی برای تبدیل این به یک حلقه for وجود دارد؟
- این بسته به این دارد که حلقه‌ها تودرتو هستند یا پشت سر هم. اغلب می‌توان از حلقه‌های پشت سر هم اجتناب کرد.

6. ✅ به سناریوهای شدید با ورودی‌ها فکر کنید:

مثال با اعداد: اعداد بزرگ، اعداد کوچک، اعداد منفی
مثال متن: متن زیاد، کلمات کوچک زیاد، فاصله‌های اضافی، حروف بزرگ و کوچک.

7. ❓ آیا استفاده از شبه-کد برای درک بهتر منطق مفید است؟

مسئله 1 - پیدا کردن اینکه آیا یک لیست شامل یک عدد مشخص است

یک الگوریتم (تابع) ایجاد کنید که مشخص کند آیا یک لیست شامل یک عدد مشخص است یا خیر. باید True یا False را بر اساس وجود یا عدم وجود عدد در لیست برگرداند.

در اینجا لیستی از داده‌های آزمایشی وجود دارد:

Test-data for algoritme:

Test-Data	Sjekk	Svar
`[1, 2, 3, 4, 5, 6, 7, 8, 9]`	`5`	`True`
`[1, 2, 3, 4, 5, 6, 7, 8, 9]`	`10`	`False`
`[2, 3, 5, 7, 11, 13, 17, 19, 23]`	`2`	`True`
`[2, 3, 5, 7, 11, 13, 17, 19, 23]`	`10`	`False`
`[-1, 0, 1, -34, 321, 22, 98, -214]`	`-214`	`True`
`[-1, 0, 1, -34, 321, 22, 98, -214]`	`0`	`True`
`[-1, 0, 1, -34, 321, 22, 98, -214]`	`2`	`False`

Tips til framgangsmåte

یک لیست و یک مقدار لیست را در یک تابع وارد کنید. در این تمرین، اعداد هستند، اما می‌توانند متن باشند.
از یک حلقه for برای پیمایش لیست استفاده کنید.
اگر عدد با عدد بررسی برابر بود، True را برگردانید.
اگر حلقه for تمام شد و شما آن را پیدا نکردید، False را برگردانید.

Svaret (i python)

def exists_in_list(the_list, check):
    for number in the_list:
        if number == check:
            return True
    return False

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

مسئله 2 - جمع کردن

یک الگوریتم ایجاد کنید که لیستی از اعداد را جمع کند.

Test-data for algoritme:

[1, 2, 3, 4, 5, 6], می‌دهد پاسخ 21.
[5, 1, 23, 68, 22, 13, 4], می‌دهد پاسخ 136
[3, 3, -3, -3, 3] می‌دهد پاسخ 3. در صورت تمایل، می‌توانید اعداد منفی را نادیده بگیرید و پاسخ 9 را ارائه دهید.

Tips til framgangsmåte

یک لیست را در یک تابع وارد کنید.
یک مجموع موقت را به عنوان 0 ذخیره کنید.
از یک حلقه for برای پیمایش لیست استفاده کنید.
مجموع لیست را return کنید.

Svaret (i python)

def sum_list(numbers):
    total = 0
    for num in numbers:
        total += num
    return total

تابع جمع لیست (به پایتون)

def sum_list(numbers):
    total = 0
    for num in numbers:
        total += num
    return total

مسئله 3a - حداکثر مقدار در یک لیست

یک الگوریتم برای یافتن بزرگترین مقدار در یک لیست ایجاد کنید.

Test-data for algoritme:

[1, 2, 3, 4, 5, 6], می‌دهد پاسخ 6.
[6, 17, 227, 1, 23, 42, 12], می‌دهد پاسخ 227
[2, -2, 2, -2, -2, 2] می‌دهد پاسخ 2.

Tips til framgangsmåte

یک لیست را در یک تابع وارد کنید.
یک مقدار موقت به اولین عنصر لیست اختصاص دهید.
از یک حلقه for برای پیمایش لیست و مقایسه با مقداری که در 2 تنظیم کرده‌اید استفاده کنید.
اگر مقدار بزرگتر است، مقدار موقت را به مقدار جدید تنظیم کنید.
این مقدار موقت را return کنید.

Svaret (i python)

def find_max(numbers):
    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

این پاسخ (به زبان پایتون) است.

def find_max(numbers):
    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

مسئله 3b - اگر لیست خالی باشد؟

یک بررسی اضافه کنید که بررسی کند آیا لیست شامل عناصر است یا خیر. اگر نه، None را برگردانید.

Svaret (i python)

def find_max(numbers):
    if len(numbers) == 0:
        return None

    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

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

مسئله 4 - شمارش تعداد یک عنصر مشخص در یک لیست

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

Test-data for algoritme:

["apple", "banana", "orange", "apple", "apple", "banana"] med apple gir svaret 3.
[1, 4, 5, 2, 4, -3, -4, 4, 2, 4, 221, 3, 1, 1, 4, 1, 12, 33, 4, 4, 2, -4, 1, 4] med 4 gir svaret 8.
["cat", "dog", "cat", "mouse", "cat", "dog", "dog"] med dog gir svaret 3.
[7, 7, 2, 9, 7, 1, 0, 7, 3, 7, 9] med 7 gir svaret 5.
["red", "blue", "green", "red", "yellow", "red"] med red gir svaret 3.
[10, -2, -2, -2, 5, 10, 10, -2] med -2 gir svaret 4.

Tips til framgangsmåte

یک لیست و یک مقدار بررسی را در یک تابع وارد کنید
با یک مقدار شمارنده موقت که روی 0 تنظیم شده است، شروع کنید.
با استفاده از یک حلقه for، لیست را پیمایش کنید.
اگر عنصر با بررسی برابر بود، مقدار شمارنده را با 1 افزایش دهید.
مقدار شمارنده را برگردانید.

Svaret (i python)

def count(the_list, check):
    count = 0
    for element in the_list:
        if element == check:
            count += 1

    return count

این پاسخ (به زبان پایتون) است:

def count(the_list, check):
    count = 0
    for element in the_list:
        if element == check:
            count += 1

    return count

وظیفه 5 - معکوس کردن یک `string`، متن

یک الگوریتم ایجاد کنید که یک string داده شده را معکوس کند.

Test-data for algoritme:

Hello there! تبدیل می‌شود به !ereht olleH.
heisann alle sammen تبدیل می‌شود به nemmas ella nnasieh
Python تبدیل می‌شود به nohtyP
racecar تبدیل می‌شود به racecar
12345abc تبدیل می‌شود به cba54321
god morgen تبدیل می‌شود به negrom dog

Tips til framgangsmåte

یک string را به یک تابع وارد کنید.
یک مقدار موقت برای ذخیره یک string خالی ایجاد کنید.
متن را با یک حلقه for با range پیمایش کنید. در اینجا می‌توانید لیست را از عقب به جلو پیمایش کنید، اما می‌توانید این را با پیمایش رو به جلو در لیست حل کنید.
هر کاراکتر را به ترتیب به مقدار موقت اضافه کنید.
متن موقت را برگردانید.

Svaret (i python)

def reverse(text):
    result = ""
    # این خط کمی پیچیده است، اما از انتها شروع می شود،
    # (شامل) تا 0 (با نوشتن -1 به عنوان انتها) می رود
    # و هر بار 1 واحد به عقب شمارش می کند
    for i in range(len(text) - 1, -1, -1):
        result += text[i]
    return result

در صورت تمایل، می توانید از الگوریتمی استفاده کنید که به جای آن به ابتدا اضافه می کند:

def reverse(text):
   result = ""
   for i in range(0, len(text)):
       # به جای آن به ابتدا اضافه کنید
       result = text[i] + result
   return result

وظیفه 6 - الگوریتم پالیندروم

یک الگوریتم ایجاد کنید که بررسی کند آیا یک کلمه داده شده یک پالیندروم است یا خیر. مثال‌هایی از پالیندروم‌ها عبارتند از abba، racecar، regninger.

Tips til framgangsmåte

یک تابع ایجاد کنید که متن را برای بررسی دریافت کند.
از یک حلقه for برای بررسی اینکه آیا حروف در هر طرف متن یکسان هستند استفاده کنید.
اگر یک حرف مطابقت نداشت False را برگردانید، اگر همه مطابقت داشتند (حلقه for تمام شد)، True را برگردانید.

Ekstra:
آیا می‌بینید چگونه می‌توانید الگوریتم را دو برابر سریع‌تر کنید؟

Hint

Du trenger bare å sjekke halvparten!

پاسخ (در پایتون)

def palindrome(text):
    for i in range(0, len(text)):
        if text[i] != text[len(text) - i - 1]:
            return False
    return True

الگوریتم سریع‌تر

def palindrome(text):
for i in range(0, int(len(text) / 2)):
if text[i] != text[len(text) - i - 1]:
return False
return True

وظیفه 7 - بررسی اینکه آیا یک لیست مرتب شده است

یک الگوریتم ایجاد کنید که بررسی کند آیا یک لیست مرتب شده است یا خیر. ساده‌ترین راه برای بررسی این موضوع، شروع از ابتدا و مقایسه اینکه آیا عنصر بعدی “بزرگتر” است یا خیر. اگر یک عنصر “بزرگتر” نباشد، لیست مرتب نیست.

Test-data for algoritme:

[1, 2, 3, 4, 5, 6], می‌دهد پاسخ True.
[6, 17, 227, 1, 23, 42, 12], می‌دهد پاسخ False
[2, -2, 2, -2, -2, 2] می‌دهد پاسخ False.
[2, 2, 3, 4, 4, 6], می‌دهد پاسخ True.
[12, 23, 34, 45, 56, 67], می‌دهد پاسخ True.

Tips til framgangsmåte

یک تابع ایجاد کنید که یک لیست را به عنوان ورودی دریافت کند.
از یک حلقه for برای پیمایش کل لیست استفاده کنید (از range برای طول لیست، منهای 1 len(list) - 1 استفاده کنید).
عنصر \(n\) را با \(n + 1\) مقایسه کنید، یعنی عنصر فعلی را با عنصر بعدی.
اگر \(n\) کمتر از \(n + 1\) باشد، به مقایسه بعدی بروید.
اگر کمتر نباشد، بلکه بزرگتر باشد، لیست مرتب نیست. در اینجا False را برگردانید.
اگر به انتهای لیست رسیدید، لیست مرتب است، True را برگردانید.

Svaret (i Python)

def is_sorted(the_list):
    for i in range(len(the_list) - 1):
        if the_list[i] > the_list[i + 1]:
            return False
    return True

این تابع بررسی می‌کند که آیا یک لیست مرتب شده است یا خیر. اگر لیست مرتب شده باشد، True را برمی‌گرداند، در غیر این صورت False را برمی‌گرداند.

به عنوان مثال:

is_sorted([1, 2, 3, 4, 5])  # True
is_sorted([5, 4, 3, 2, 1])  # False
is_sorted([1, 3, 2, 4, 5])  # False

وظیفه 8 - جابجایی

یک الگوریتم ایجاد کنید که یک لیست از موارد را جابجا کند. روش‌های زیادی برای انجام این کار وجود دارد، اما یک روش خوب چیزی است که به عنوان الگوریتم جابجایی Fisher-Yates شناخته می‌شود. می‌توانید در اینجا در مورد آن بیشتر بدانید Wikipedia.

Test Data

["a", "b", "c", "d", "e"] → می‌تواند مثلاً ["c", "e", "a", "d", "b"] باشد
[1, 2, 3, 4, 5, 6] → می‌تواند مثلاً [4, 1, 6, 3, 2, 5] باشد
["apple", "banana", "orange"] → می‌تواند مثلاً ["orange", "apple", "banana"] باشد
["x"] → همچنان ["x"] باقی می‌ماند
[] → همچنان [] باقی می‌ماند

به این صورت کار می‌کند:

Algoritmen

یک تابع ایجاد کنید که لیست اعداد را به عنوان ورودی دریافت کند.
یک لیست خالی جدید ایجاد کنید که نتیجه‌ی ترکیبی را در خود نگه دارد.
از یک random برای انتخاب یک اندیس تصادفی در لیست استفاده کنید.
این عنصر را به لیست خالی اضافه کنید و آن را از لیست قدیمی حذف کنید.
لیست جدید را از تابع برگردانید.

Svaret (i Python)

import random

def shuffle(the_list):
    shuffled = []

    while len(the_list) > 0:
        i = random.randrange(0, len(the_list))
        shuffled.append(the_list[i])
        the_list.pop(i)

    return shuffled

وظیفه ۹ - مرتب‌سازی بوگو

در این وظیفه، شما باید یک الگوریتم مرتب‌سازی (عملاً) وحشتناک، اما بسیار ساده ایجاد کنید. این الگوریتم هنگام کار با لیست‌های بزرگ بسیار ضعیف است (مرتب‌سازی بیش از ۱۲-۱۳ مورد برای همیشه طول می‌کشد). در سطح ۲، یک الگوریتم مرتب‌سازی بهتر، مرتب‌سازی حبابی را ایجاد خواهیم کرد.

Test Data

[3, 1, 2] → [1, 2, 3]
[5, 4, 3, 2, 1] → [1, 2, 3, 4, 5]
[10, 7, 8, 2] → [2, 7, 8, 10]
[1, 1, 1] → [1, 1, 1]
[9, 3, 6, 3, 9] → [3, 3, 6, 9, 9]
[0, -1, 4, -2] → [-2, -1, 0, 4]

الگوریتم به این صورت کار می‌کند:

Algoritmen

یک تابع ایجاد کنید که لیست اعداد مرتب‌نشده را به عنوان ورودی دریافت کند.
لیست را به صورت تصادفی مخلوط کنید (از shuffle در مسئله 8 استفاده کنید).
بررسی کنید که آیا لیست مرتب شده است یا خیر (از بررسی‌ای که در مسئله 7 ایجاد کردید استفاده کنید).
اگر لیست مرتب نشده است، مراحل 2 و 3 را تکرار کنید.
تا زمانی که لیست مرتب شود، تکرار کنید، سپس برگردانید.

به زبان ساده: bogo-sort کل لیست را مخلوط می‌کند و امیدوار است که مرتب شود.

در مورد Big O notation در Level 2 بخوانید.

نکته: برای ایجاد یک لیست نامرتب برای الگوریتم خود، می‌توانید از shuffle در مسئله ۸ استفاده کنید.

Svaret (i Python)

def bogo_sort(the_list):
    while not is_sorted(the_list):
        the_list = shuffle(the_list)
    return the_list

مسئله 10a - جستجوی متن - “زیررشته” (سخت!)

یک الگوریتم ایجاد کنید که بتواند یک کلمه کلیدی را در متن پیدا کند. یعنی، اگر جمله‌ای مانند hello there دارید، باید True را با کلمه کلیدی hello و False را با کلمه کلیدی مانند hahah برگردانید. این الگوریتم باید بدون توجه به ورودی و خروجی کار کند.

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

Test-data for algoritme:

hello there everyone با there = True
hello there everyone با ever = True
hello there everyone با then = False
qwecvyufavsjekkftyergwcery با sjekk = True

Tips til framgangsmåte

یک تابع ایجاد کنید که دو string، داده و کلمه کلیدی را به عنوان ورودی دریافت کند.
از یک حلقه for با range برای پیمایش متن استفاده کنید.
در اینجا مهم است که به این فکر کنید حلقه تا کجا باید پیش برود.
یک متغیر موقت ایجاد کنید که نشان دهد آیا کلمه کلیدی پیدا شده است یا خیر، آن را به طور پیش فرض روی True تنظیم کنید.
از یک حلقه for دیگر با range برای مقایسه جایی که در متن هستید با کلمه کلیدی استفاده کنید.
اگر چیزی در کلمه کلیدی با جایی که اکنون بررسی می‌کنید مطابقت نداشته باشد، متغیر موقت را روی True تنظیم کنید و از حلقه داخلی break کنید.
اگر به انتهای متن رسیدید و چیزی پیدا نکردید، False را برگردانید.

Svaret (i Python)

def search(data, word): 
    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

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

به عنوان مثال:

data = "Hello world"
word = "world"
result = search(data, word)
print(result)  # Output: True

در این مثال، تابع search با موفقیت کلمه “world” را در رشته “Hello world” پیدا می‌کند و مقدار True را برمی‌گرداند.

مسئله 10b

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

Tips til framgangsmåte

این بررسی را قبل از حلقه for اضافه کنید.

Svaret (i python)

def search(data, word): 
    if len(word) > len(data):
        return False

    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

مسئله 11 - معکوس کردن کلمات در جمله (سخت)

به مسئله 5 در مورد معکوس کردن یک جمله برگردید. الگوریتمی را تغییر دهید (یا از نو شروع کنید) که هر کلمه را در یک جمله معکوس کند و سپس آنها را دوباره به هم متصل کند.

Test-data for algoritme:

hello there everyone تبدیل می‌شود به olleh ereht enoyreve
This is the way it goes! تبدیل می‌شود به sihT si eht yaw ti !seog
does this racecar go? of course! تبدیل می‌شود به seod siht racecar ?og fo !esruoc

Tips til framgangsmåte

یک تابع ایجاد کنید که یک string را به عنوان ورودی دریافت کند.
❗متن را با استفاده از .split(" ") تقسیم کنید.
یک متغیر موقت برای ذخیره مقدار نهایی ایجاد کنید.
از یک حلقه for برای پیمایش هر کلمه استفاده کنید.
از همان روش برای معکوس کردن که در وظیفه 5 استفاده شد، استفاده کنید.
از نتیجه برای افزودن به متغیری که در مرحله 2 ایجاد کردید، استفاده کنید.
مقدار نهایی را برگردانید.

Svaret (i Python)

def reverse_words(words):
    sentence = words.split(" ")
    output = ""

    for word in sentence:
        reversed_word = ""
        for i in range(0, len(word)):
            reversed_word = word[i] + reversed_word
        output += reversed_word + " "

    return output

این تابع کلمات را معکوس می‌کند. به عنوان مثال، اگر ورودی “hello world” باشد، خروجی “olleh dlrow” خواهد بود.

این یک راه حل ساده برای معکوس کردن کلمات در یک جمله است.

امیدوارم این کمک کند!

➕اضافه:

مسئله E1 - حذف موارد تکراری از یک لیست

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

Tips til framgangsmåte

با یک تابع شروع کنید که یک لیست را به عنوان ورودی می‌گیرد.
در اینجا ما از حلقه‌های while به جای for استفاده خواهیم کرد. این کار در پایتون آسان‌تر است، در زبان‌های دیگر for با متغیرهای شمارنده به خوبی کار می‌کند.
یک متغیر شمارنده idx (برای index، یا i) ایجاد کنید.
از یک حلقه while استفاده کنید که تا طول لیست ادامه یابد.
ما می‌خواهیم عنصر در idx را با تمام عناصر دیگر مقایسه کنیم.
یک متغیر شمارنده دیگر jdx (یا j) ایجاد کنید که از idx + 1 شروع شود.
عنصر در idx را با عنصر در jdx مقایسه کنید، اگر یکسان هستند، jdx را با استفاده از pop(jdx) حذف کنید.
HUSK! اگر عنصر را حذف کنید، لیست کوچکتر می‌شود، بنابراین باید یک گام به عقب برگردید با jdx -= 1.
jdx را با 1 افزایش دهید و عنصر بعدی را تست کنید.
پس از حلقه while داخلی، idx را با 1 افزایش دهید و حلقه while خارجی ادامه خواهد یافت.
در نهایت لیست را با حذف موارد تکراری برگردانید.

Test Data

[1, 2, 2, 3, 1, 4, 3] → می‌شود [1, 2, 3, 4]
["a", "b", "a", "c", "b", "d"] → می‌شود ["a", "b", "c", "d"]
[5, 5, 5, 5] → می‌شود [5]
["x", "y", "z", "x", "y", "x"] → می‌شود ["x", "y", "z"]
[10, -1, 10, -1, 0, 0, 10] → می‌شود [10, -1, 0]
["apple", "apple', "banana", "orange", "apple", "orange", "pear", "apple"]
- باید بدهد: ["apple", "banana", "orange", "pear"]

Svaret (i Python)

def delete_duplicates(the_list):
    idx = 0

    while idx < len(the_list):
        jdx = idx + 1

        while jdx < len(the_list):
            if the_list[idx] == the_list[jdx]:
                the_list.pop(jdx)
                jdx -= 1
            jdx += 1
        idx += 1

    return the_list

این پاسخ (در پایتون) است.

وظیفه E2 - مرتب‌سازی شمارشی

مرتب‌سازی شمارشی یکی از معدود الگوریتم‌های مرتب‌سازی است که در زمان \(O(n)\) کار می‌کند. یعنی، زمان آن به طور قابل توجهی بیشتر از تعداد عناصر لیست نیست. برای اطلاعات بیشتر در مورد نمادگذاری Big O، به Level 2 مراجعه کنید.

تا حدودی به گستره عناصر بستگی دارد. اگر کوچکترین عدد 0 و بزرگترین عدد 100000 باشد، ممکن است کمی طول بکشد، بنابراین می‌توان از این روش در صورتی استفاده کرد که گستره مقادیر کم باشد. این روش برای اعداد منفی نیز کار نمی‌کند، اما می‌توان الگوریتم را طوری تغییر داد که با اعداد منفی کار کند.

الگوریتم به این صورت کار می‌کند:

بزرگترین عنصر را پیدا کنید، مقدار این عنصر را به عنوان \(k\) ذخیره کنید.
لیستی ایجاد کنید که شامل \(k + 1\) عنصر باشد، count.
لیست مرتب‌نشده را پیمایش کنید و از مقدار عدد به عنوان شاخص استفاده کنید. یعنی، اگر عنصر مقدار 47 را داشته باشد، به count[47] بروید و آن را با 1 افزایش دهید.
لیست count را پیمایش کنید و تعداد اعدادی که شاخص آن‌ها هستند را قرار دهید. مثال: اگر عدد 3 در شاخص 1 وجود دارد، سه عدد 1 را اضافه کنید.

Testdata

داده‌های نامرتب	داده‌های مرتب‌شده
`[7, 3, 9, 1, 4, 3, 0, 6, 8, 6, 2, 1, 9, 0, 5, 4]`	`[0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9]`
`[12, 13, 15, 0, 8, 15, 8, 5, 16, 8, 0, 20, 4, 9, 17, 16, 1, 3, 6, 15, 5, 2, 3, 1, 19, 13, 17, 5, 3, 10]`	`[0, 0, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 8, 8, 8, 9, 10, 12, 13, 13, 15, 15, 15, 16, 16, 17, 17, 19, 20]`

Tips til framgangsmåte

با ایجاد یک تابع که یک لیست را به عنوان ورودی دریافت می‌کند، شروع کنید.
یک لیست output خالی ایجاد کنید.
از یک حلقه for برای پیمایش کل لیست استفاده کنید.
قبل از حلقه for، مقدار حداکثر را در یک متغیر نگه دارید.
اگر مقدار بزرگتری پیدا کردید، مقدار حداکثر را به‌روزرسانی کنید.
لیستی ایجاد کنید که شامل این تعداد صفر + 1 باشد. مثال: بزرگترین مقدار 47 است، پس لیستی با 48 صفر ایجاد کنید. می‌توانید این کار را با [0] * (maks + 1) یا یک حلقه for انجام دهید. آن را count بنامید.
یک بار دیگر با یک حلقه for لیست را پیمایش کنید.
از مقدار عنصر به عنوان اندیس استفاده کنید و آن را با 1 افزایش دهید. count[value] += 1
از یک حلقه for برای پیمایش لیست count استفاده کنید.
از مقداری که در هر اندیس وجود دارد برای افزودن آن تعداد عدد استفاده کنید.
لیست مرتب شده را برگردانید.

Svaret (i Python)

def counting_sort(input_list):
    output = []

    max_val = input_list[0]

    for n in input_list:
        if n > max_val:
            max_val = n

    # این یک آرایه پر از صفرها ایجاد می‌کند
    count = [0] * (max_val + 1)

    for n in input_list:
        count[n] += 1

    for i in range(len(count)):
        # از _ برای نادیده گرفتن یک مقدار استفاده کنید
        for _ in range(count[i]):
            output.append(i)

    return output

الگوریتم‌های ساده ایجاد کنید

چگونه یک الگوریتم را “طراحی” کنیم؟

1. ✅ ابتدا مسئله را به بخش‌های کوچک‌تر تقسیم کنید.

2. ❓ آیا موارد خاصی وجود دارد؟

3. ✅ با تلاش برای ساخت یک راه حل شروع کنید.

4. ✅ بررسی کنید که آیا الگوریتم در زمان اجرا به خوبی کار می‌کند

5. ❓ به راه حل خود فکر کنید، آیا به تمام مراحلی که استفاده کرده‌اید نیاز دارید؟

6. ✅ به سناریوهای شدید با ورودی‌ها فکر کنید:

7. ❓ آیا استفاده از شبه-کد برای درک بهتر منطق مفید است؟

مسئله 1 - پیدا کردن اینکه آیا یک لیست شامل یک عدد مشخص است

مسئله 2 - جمع کردن

مسئله 3a - حداکثر مقدار در یک لیست

مسئله 3b - اگر لیست خالی باشد؟

مسئله 4 - شمارش تعداد یک عنصر مشخص در یک لیست

وظیفه 5 - معکوس کردن یک string، متن

وظیفه 6 - الگوریتم پالیندروم

وظیفه 7 - بررسی اینکه آیا یک لیست مرتب شده است

وظیفه 8 - جابجایی

وظیفه ۹ - مرتب‌سازی بوگو

مسئله 10a - جستجوی متن - “زیررشته” (سخت!)

مسئله 10b

مسئله 11 - معکوس کردن کلمات در جمله (سخت)

➕اضافه:

مسئله E1 - حذف موارد تکراری از یک لیست

وظیفه E2 - مرتب‌سازی شمارشی

وظیفه 5 - معکوس کردن یک `string`، متن