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

https://news.1rj.ru/str/Computer_Jam

وقتی میری فوتسال ولی تعویضت میکنن

من هنوز کامل نخوندمش ولی دارم منظم پیش میبرمش یه نکته جالب دیگه هم که توش اشاره کرد و میخام از این به بعد به کار بگیرمش این بود که به ریت مسئله اصن نگاه نکن چونکه وقتی میبینی ریت یک مسئله بالاست انتظار یچیز خیلی سخت داری و نمیتونی عادی روی مسئله فک کنی و ممکنه مسئله خیلی خیلی ساده تر باشه

معمولن تاپ تن بودن تو اینجور مسابقات خفن به حساب میاد.
بعد امروز سر مسابقه یکی از تیما داد میزد تاپ تن شدیم. (مسابقه با ۹ تا تیم برگزار شد😂)

برا مسائلی که توابع بازگشتی و dp نیازه، برا سریعتر کردن روند محاسبه، تکنیکی به کار میره به اسم memoization حرفش اینه که اگه قراره مقداری رو دوباره بهش نیاز داشته باشی یجا ذخیرش کن که نیاز نباشه دوباره حسابش کنی.
مثال بارزش حساب کردن سری فیبوناچی هست.

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n < 2:
        memo[n] = n
    else:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(10))

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

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

print(fib(10))

حالا یه مشکل دیگه که پیش میاد بخصوص تو مسابقات اینه که ما معمولن یه حجم محدودی حافظه داریم و اینکه همه چیزو هم ذخیره کنیم خیلی بهینه نیست.
ولی پایتون یه قابلیت دیگم داره به اسم Least Recently Used اینو میشه محدودش کرد که یک تعدادی از آخرین مقادیری که استفاده شدن رو نگه داره فقط.

from functools import lru_cache

@lru_cache(maxsize=100)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

print(fib(10))

ما میتونیم از بالا به پایین به مسئله نگاه کنیم که بهش میگن Top-Down Approach.
نمونه کد اول پست بالایی میشه. که البته داخل کد تکنیک memoization هم استفاده شده.
ولی میتونیم از پایین به بالا هم به مسئله نگاه کنیم که بهش میگن Bottom-Up Approach.
حالا به جا اینکه بگیم مثلن fib(5) نیاز داره به مقادیر fib(4) و fib(3) میگیم که اگه fib(4) و fib(3) رو باهم جمع کنیم به fib(5) میرسیم. باهمین ایده از دو مقدار اولی که از سری فیبوناچی میدونیم، شروع میکنیم و تا اون مقداری که نیاز داریم حساب میکنیم.

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

مزیتش اینه که دیگه خبری از تابع بازگشتی نیست.

هوش و ذکاوت

گاهی برای حل بعضی مسائل مجبوریم همه حالت‌های ممکن رو بررسی کنیم. این دقیقاً کاریه که الگوریتم backtracking انجام می‌ده. ولی خب، همه حالت‌ها رو بررسی کردن معمولاً به صرفه نیست، برای همین یه تکنیک خیلی مهم به اسم pruning داریم (هرس کردن حالت‌های غیرضروری).

مثال معروفش حل کردن مسئله n-queens هست:

def solve(n):
    result = []
    board = []

    def is_safe(row, col):
        for r, c in enumerate(board):
            if c == col or abs(row - r) == abs(col - c):
                return False
        return True

    def backtrack(row):
        if row == n:
            result.append(board[:])
            return
        for col in range(n):
            if is_safe(row, col):  # pruning
                board.append(col)
                backtrack(row + 1)
                board.pop()

    backtrack(0)
    return result

print(solve(4))

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

این تکنیک تو خیلی از مسائل ترکیبیاتی و گرافی می‌تونه سرعت الگوریتم رو از نمایی به قابل‌حل برسونه.

حس باحالیه که، یه عکسی رو میبینی و خودت از اینکه یه وقتی اونجا بودی تعجب میکنی

تمام شد. مبارک خیلیا

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