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

برا مسائلی که توابع بازگشتی و 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 که خودم خریده بودم تست کردم خیلی اینطوری خوشگل تره.

این ویدیو به بررسی فرمول دقیق برای محاسبه اعداد اول می‌پردازد که توسط C. P. Willans در سال ۱۹۶۴ ارائه شده است. این فرمول با استفاده از توابع ریاضی پیچیده، امکان محاسبهٔ مستقیم عدد اول n‌ام را فراهم می‌کند. اگرچه این فرمول از نظر تئوری جالب است، اما به دلیل پیچیدگی محاسباتی، در عمل کارایی محدودی دارد.

برای آشنایی بیشتر با این فرمول و نحوهٔ عملکرد آن. https://youtu.be/j5s0h42GfvM

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

یه کامنت جالب هم بود زیرش:
I’m pretty sure C. P. stands for coolformulaforcalculating primes

عبارت

((j-1)!+1)/j

اگر عدد صحیح بشه نشون میده که اون عدد یک عدد اوله و حالا ضرب اون در عدد پی و گرفتن تابع کوسینوس ازش مقادیر اعشاری رو چیزی غیر از یک و منفی یک میده و مقادیر صحیح رو یک و منفی یک و بعد با به توان ۲ رسوندش و کف گرفتن ازش فقط یک ها میمونه که تعداد اعداد اول رو بهمون میده.
بنظرم تا همینجاش شگفت انگیز بود.

در حال حاضر اینجاییم.
با همراهیه سید
@ahes2025

بنظرم هر کدوم یه زبانی رو مسلط ترن یا شاید منابع بیشتری ازش دارن برا همین دیفالت تصمیم میگیرن با اون کد بزنن. طبق تجربه شخصی دیدم که grok اکثر مواقع cpp کد میزنه.