رفتن به محتوا
کارگاه و مبانی برنامه‌نویسی

جلسه چهارم

۱. عملیات روی ماتریس

هر تابع یک ماتریس مربعی به ابعاد n دریافت می‌کند و باید عملیات خواسته شده را روی آن انجام دهد:

۱. جمع قطرها: محاسبه مجموع اعداد روی قطرهای اصلی و فرعی (عنصر وسط در ماتریس‌های فرد فقط یکبار محاسبه شود)
۲. مجموع همسایه‌ها: ساخت ماتریس جدید که هر عنصر آن مجموع همسایه چپ و بالای آن در ماتریس اصلی باشد (همسایه‌های ناموجود صفر فرض شوند)
۳. چرخش ماتریس: چرخاندن ماتریس ۹۰ درجه در جهت عقربه‌های ساعت (بدون استفاده از حافظه اضافی)

فرمت ورودی برای هر سه قسمت

n
a11 a12 ... a1n
a21 a22 ... a2n
... ... ... ...
an1 an2 ... ann

نمونه برای هر سه قسمت

ورودی:

3
1 2 3
4 5 6
7 8 9

خروجی قسمت ۱: 25 (جمع قطرها: 1+5+9+3+7 = 25)

جواب الف
def diagonal_sum(matrix):
    """
    محاسبه مجموع قطرهای اصلی و فرعی ماتریس.
    برای ماتریس با ابعاد فرد، عنصر وسط فقط یکبار شمرده می‌شود.
    """
    n = len(matrix)
    total = 0


    # محاسبه مجموع قطر اصلی (از بالا-چپ به پایین-راست)
    for i in range(n):
        total += matrix[i][i]


    # محاسبه مجموع قطر فرعی (از بالا-راست به پایین-چپ)
    for i in range(n):
        # در صورت فرد بودن ابعاد، عنصر وسط را نادیده می‌گیریم
        if n % 2 == 1 and i == n // 2:
            continue
        total += matrix[i][n-1-i]


    return total

خروجی قسمت ۲:

1  3   5
5  11 14
11 20 23
جواب ب
def neighbor_sum(matrix):
    """
    ساخت ماتریس جدید که هر عنصر آن مجموع همسایه‌های چپ و بالای آن است.
    همسایه‌های ناموجود صفر در نظر گرفته می‌شوند.
    """
    n = len(matrix)




    result = []
    for i in range(n):
        result.append([])
        for j in range(n):
            result[i].append(0)




    # پر کردن اولین عنصر
    result[0][0] = matrix[0][0]


    # پر کردن سطر اول (فقط همسایه چپ دارد)
    for j in range(1, n):
        result[0][j] = matrix[0][j] + result[0][j-1]


    # پر کردن ستون اول (فقط همسایه بالا دارد)
    for i in range(1, n):
        result[i][0] = matrix[i][0] + result[i-1][0]


    # پر کردن بقیه ماتریس
    for i in range(1, n):
        for j in range(1, n):
            result[i][j] = matrix[i][j] + result[i-1][j] + result[i][j-1]


    return result

خروجی قسمت ۳:

7 4 1
8 5 2
9 6 3
جواب ج با دو روش ریاضیاتی و بند کفشی
def rotate_matrix(matrix):
    """
    چرخش ماتریس ۹۰ درجه در جهت عقربه‌های ساعت به صورت درجا.
    """
    n = len(matrix)


    # گام ۱: ترانهاده کردن ماتریس
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]


    # گام ۲: معکوس کردن هر سطر
    for i in range(n):
        matrix[i].reverse()


    return matrix


def rotate_matrix(matrix):
    n = len(matrix)


    # For each ring, starting from outer ring moving inward
    for i in range(n // 2):
        # For each element in the current ring
        for j in range(i, n - 1 - i):
            temp = matrix[i][j]
            matrix[i][j] = matrix[n-1-j][i]
            matrix[n-1-j][i] = matrix[n-1-i][n-1-j]
            matrix[n-1-i][n-1-j] = matrix[j][n-1-i]
            matrix[j][n-1-i] = temp


    return matrix

۲. عملیات روی دیکشنری

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

ورودی و خروجی

# ورودی
student_grades = {
    "Ali": 18,
    "Sara": 20,
    "Reza": 17,
    "Nina": 20
}


# خروجی
["Sara", "Nina"]
جواب با دو روش استفاده از توابع آماده و دستی
def get_top_students(student_grades):
    """
    برگرداندن لیست دانش‌آموزان با بالاترین نمره.
    """
    # یافتن بالاترین نمره
    max_grade = max(student_grades.values())


    # یافتن تمام دانش‌آموزان با بالاترین نمره
    top_students = []
    for student, grade in student_grades.items():
        if grade == max_grade:
            top_students.append(student)


    return sorted(top_students)  # مرتب‌سازی الفبایی برای خروجی یکسان
def get_top_students(student_grades):
    """
    یافتن دانش‌آموزان با بالاترین نمره بدون استفاده از توابع آماده پایتون
    """
    max_grade = 0
    for grade in student_grades.values():
        max_grade = max(max_grade, grade)


    top_students = []
    for student, grade in student_grades.items():
        if grade == max_grade:
            top_students.append(student)


    # sort the top-students by name
    n = len(top_students)
    for i in range(n-1):
        for j in range(n-i-1):
            if top_students[j] > top_students[j+1]:
                temp = top_students[j]
                top_students[j] = top_students[j+1]
                top_students[j+1] = temp


    return top_students

۳. پردازش رشته‌ها

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

۱. معکوس‌کننده کلمات: هر کلمه معکوس شود ولی ترتیب کلمات حفظ شود
۲. دیکشنری‌ساز: ساخت دیکشنری از کلمات منحصربفرد با طول بیشتر از ۳ حرف (کلید: کلمه، مقدار: طول کلمه)

نمونه

ورودی (برای هر دو تابع):

"The quick brown fox jumps over the lazy dog!"

خروجی تابع ۱:

"ehT kciuq nworb xof spmuj revo eht yzal !god"
جواب الف
def reverse_words(text):
    """
    معکوس کردن هر کلمه با حفظ ترتیب کلمات.
    """
    # جدا کردن متن به کلمات با حفظ نقطه‌گذاری
    words = []
    current_word = ""


    for char in text:
        if char.isalnum() or char.isspace():
            current_word += char
        else:
            if current_word:
                words.append(current_word)
                current_word = ""
            words.append(char)


    if current_word:
        words.append(current_word)


    # معکوس کردن هر کلمه و اتصال مجدد
    result = []
    for word in words:
        if word.isspace() or not word.isalnum():
            result.append(word)
        else:
            result.append(word[::-1])


    return "".join(result)


def reverse_words(text):
    """
    معکوس کردن هر کلمه با حفظ ترتیب کلمات به روش ساده
    """
    result = ''
    word = ''


    # پیمایش کاراکتر به کاراکتر رشته
    i = 0
    while i < len(text):
        char = text[i]


        # اگر به فاصله یا علامت نگارشی رسیدیم
        if char == ' ' or char in '!.,?':
            # معکوس کردن کلمه قبلی اگر وجود داشته باشد
            if word:
                # معکوس کردن کلمه با حلقه ساده
                reversed_word = ''
                j = len(word) - 1
                while j >= 0:
                    reversed_word += word[j]
                    j -= 1
                result += reversed_word
                word = ''


            # اضافه کردن کاراکتر فعلی به نتیجه
            result += char
        else:
            # اضافه کردن حرف به کلمه فعلی
            word += char


        i += 1


    # معکوس کردن آخرین کلمه اگر وجود داشته باشد
    if word:
        reversed_word = ''
        j = len(word) - 1
        while j >= 0:
            reversed_word += word[j]
            j -= 1
        result += reversed_word


    return result


### تابع دیکشنری‌ساز:
def create_word_dict(text):
    """
    ساخت دیکشنری از کلمات با طول بیشتر از ۳ حرف به روش ساده
    """
    word_dict = {}
    current_word = ''


    # پیمایش کاراکتر به کاراکتر
    i = 0
    while i < len(text):
        char = text[i].lower()  # تبدیل به حروف کوچک


        # اگر حرف یا عدد باشد
        if ('a' <= char <= 'z') or ('0' <= char <= '9'):
            current_word += char
        # اگر به جداکننده رسیدیم و کلمه‌ای داریم
        elif current_word:
            # اگر طول کلمه بیشتر از ۳ باشد
            if len(current_word) > 3:
                word_dict[current_word] = len(current_word)
            current_word = ''


        i += 1


    # بررسی آخرین کلمه
    if current_word and len(current_word) > 3:
        word_dict[current_word] = len(current_word)


    return word_dict

خروجی تابع ۲:

{
    'quick': 5,
    'brown': 5,
    'jumps': 5,
    'over': 4,
    'lazy': 4
}
جواب ب با دو روش تابع آماده و دستی
### تابع دیکشنری‌ساز:
def create_word_dict(text):
    """
    ساخت دیکشنری از کلمات با طول بیشتر از ۳ حرف به روش ساده
    """
    word_dict = {}
    current_word = ''


    # پیمایش کاراکتر به کاراکتر
    i = 0
    while i < len(text):
        char = text[i].lower()  # تبدیل به حروف کوچک


        # اگر حرف یا عدد باشد
        if ('a' <= char <= 'z') or ('0' <= char <= '9'):
            current_word += char
        # اگر به جداکننده رسیدیم و کلمه‌ای داریم
        elif current_word:
            # اگر طول کلمه بیشتر از ۳ باشد
            if len(current_word) > 3:
                word_dict[current_word] = len(current_word)
            current_word = ''


        i += 1


    # بررسی آخرین کلمه
    if current_word and len(current_word) > 3:
        word_dict[current_word] = len(current_word)


    return word_dict
def create_word_dict(text):
    """
    ساخت دیکشنری از کلمات منحصربفرد با طول بیشتر از ۳ حرف.
    """
    # تقسیم متن به کلمات و پاک‌سازی
    words = text.lower().replace('!', ' ').replace('.', ' ').split()


    # ساخت دیکشنری برای کلمات بلندتر از ۳ حرف
    word_dict = {}
    for word in words:
        if len(word) > 3:
            word_dict[word] = len(word)


    return word_dict

۴. زیرآرایه کوهستانی (یکم درد داره)

تابعی بنویسید که طول بلندترین زیرآرایه کوهستانی را در یک آرایه پیدا کند. یک آرایه زمانی کوهستانی است که:

  1. طول حداقل ۳
  2. دارای نقطه اوج i که برای آن:
    • اعداد تا نقطه i صعودی اکید
    • اعداد از نقطه i نزولی اکید

نمونه‌ها

[2,1,4,7,3,2,5] -> 5 # زیرآرایه [1,4,7,3,2]
[2,2,2] -> 0        # هیچ زیرآرایه کوهستانی ندارد
جواب
def longest_mountain(arr):
    """
    یافتن طول بلندترین زیرآرایه کوهستانی.
    """
    n = len(arr)
    if n < 3:
        return 0


    max_length = 0


    # بررسی هر نقطه اوج ممکن
    for i in range(1, n-1):
        # بررسی اینکه آیا i یک نقطه اوج است
        if arr[i] > arr[i-1] and arr[i] > arr[i+1]:
            # یافتن مرز چپ
            left = i - 1
            while left > 0 and arr[left-1] < arr[left]:
                left -= 1


            # یافتن مرز راست
            right = i + 1
            while right < n-1 and arr[right+1] < arr[right]:
                right += 1


            # به‌روزرسانی طول حداکثر اگر این یک کوه معتبر است
            max_length = max(max_length, right - left + 1)


    return max_length

۵. تطابق الگو

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

نمونه‌ها

"abba", "dog cat cat dog"    -> true
"abba", "dog cat cat fish"   -> false  # fish با هیچ حرفی متناظر نیست
"aaaa", "dog cat cat dog"    -> false  # یک حرف نمی‌تواند با دو کلمه متفاوت متناظر شود
جواب
def pattern_match(pattern, words):
    word_list = words.split()


    if len(pattern) != len(word_list):
        return False


    pattern_to_word = {}
    word_to_pattern = {}


    for i in range(len(pattern)):
        p = pattern[i]
        w = word_list[i]


        if p in pattern_to_word:
            if pattern_to_word[p] != w:
                return False
        elif w in word_to_pattern:
            if word_to_pattern[w] != p:
                return False
        else:
            pattern_to_word[p] = w
            word_to_pattern[w] = p


    return True

۶. مسیر با حداکثر طلا (اصلا هم درد نداشت)

در یک معدن طلا با ابعاد m × n، هر سلول از این معدن یک عدد صحیح دارد که نشان‌دهنده مقدار طلا در آن سلول است. اگر سلولی خالی باشد، مقدار آن 0 است. با توجه به شرایط زیر، حداکثر مقدار طلایی که می‌توانید جمع‌آوری کنید را برگردانید:

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

نمونه ۱

ورودی: grid = [[0,6,0],[5,8,7],[0,9,0]]
خروجی: 24
توضیحات:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
مسیر برای دریافت حداکثر طلا: 9 -> 8 -> 7

نمونه ۲

ورودی: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
خروجی: 28
توضیحات:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
مسیر برای دریافت حداکثر طلا: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

محدودیت‌ها

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 15
  • 0 <= grid[i][j] <= 100
  • حداکثر ۲۵ سلول حاوی طلا وجود دارد.
جواب
def gold_path(i, j):
    # اگر خارج از محدوده باشیم یا به خانه خالی برسیم
    if (i < 0 or i >= len(grid) or
        j < 0 or j >= len(grid[0]) or
        grid[i][j] == 0):
        return 0


    # نگهداری مقدار فعلی و صفر کردن خانه برای جلوگیری از بازدید مجدد
    gold = grid[i][j]
    grid[i][j] = 0


    # حرکت به چهار جهت و پیدا کردن بیشترین مقدار
    best = max(
        gold_path(i+1, j),  # پایین
        gold_path(i-1, j),  # بالا
        gold_path(i, j+1),  # راست
        gold_path(i, j-1)   # چپ
    )


    # برگرداندن مقدار خانه به حالت اول
    grid[i][j] = gold


    return gold + best
def collect_maximum_gold(grid):
    """
    پیدا کردن بیشترین مقدار طلا در مسیر معدن
    """


    # امتحان کردن همه نقاط شروع ممکن
    max_gold = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] != 0:
                max_gold = max(max_gold, gold_path(i, j))


    return max_gold

۷. کلمات گمشده در سرزمین فاصله‌ها!

تصور کن جمله‌ای داری که در آن، کلمات در میان دریایی از فاصله‌های اضافه گم شده‌اند. وظیفه تو این است که این کلمات گمشده را پیدا کنی و بشماری، اما باید مراقب باشی! فاصله‌های اضافی فقط می‌خواهند تو را گیج کنند. به آن‌ها اهمیت نده! (فقط حواست باشه که از تابع split() استفاده نکنی)

نمونه

ورودی :

"     Python     is    an  amazing   language   for   programming! "

خروجی:

7

تیم تدریس‌یاران درس - © ۱۴۰۳