home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรม Python หาค่าสูงสุดใน Array ที่สร้างจากกฎ Recursive

กำหนด Array A ความยาว n+1 โดย:

  • A[0] = 0
  • A[1] = 1
  • A[2*i] = A[i] สำหรับ 2 ≤ 2*i ≤ n
  • A[2*i+1] = A[i] + A[i+1] สำหรับ 2 ≤ 2*i+1 ≤ n

หาค่า Max(A)

ตัวอย่าง

  • Input: n = 5
  • Output: 3
Array A (0 to 5):
A[0] = 0
A[1] = 1
A[2] = A[1] = 1
A[3] = A[1] + A[2] = 1 + 1 = 2
A[4] = A[2] = 1
A[5] = A[2] + A[3] = 1 + 2 = 3
Max = 3

โค้ด Python

def get_maximum_generated(n):
    """
    สร้าง Array ตามกฎ Recursive และหาค่าสูงสุด
    
    Args:
        n: int - ขนาด Array - 1 (Array มี Index 0 ถึง n)
    
    Returns:
        int - ค่าสูงสุดใน Array
    """
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    A = [0] * (n + 1)
    A[0] = 0
    A[1] = 1
    
    for i in range(2, n + 1):
        if i % 2 == 0:
            # Even: A[i] = A[i//2]
            A[i] = A[i // 2]
        else:
            # Odd: A[i] = A[i//2] + A[i//2 + 1]
            A[i] = A[i // 2] + A[i // 2 + 1]
    
    return max(A)


# ทดสอบ
if __name__ == "__main__":
    test_cases = [0, 1, 2, 3, 4, 5, 6, 7, 10, 100]
    
    for n in test_cases:
        result = get_maximum_generated(n)
        print(f"n={n:3d} => Max = {result}")
        
        # แสดง Array เต็มสำหรับ n เล็ก
        if n <= 10:
            A = [0] * (n + 1)
            A[0] = 0
            if n >= 1: A[1] = 1
            for i in range(2, n + 1):
                if i % 2 == 0:
                    A[i] = A[i // 2]
                else:
                    A[i] = A[i // 2] + A[i // 2 + 1]
            print(f"  Array: {A}")

ผลลัพธ์

n=  0 => Max = 0
  Array: [0]
n=  1 => Max = 1
  Array: [0, 1]
n=  2 => Max = 1
  Array: [0, 1, 1]
n=  3 => Max = 2
  Array: [0, 1, 1, 2]
n=  4 => Max = 2
  Array: [0, 1, 1, 2, 1]
n=  5 => Max = 3
  Array: [0, 1, 1, 2, 1, 3]
n=  6 => Max = 3
  Array: [0, 1, 1, 2, 1, 3, 2]
n=  7 => Max = 3
  Array: [0, 1, 1, 2, 1, 3, 2, 3]
n= 10 => Max = 4
  Array: [0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3]
n=100 => Max = 13

Complexity Analysis

  • Time: O(n) - Single Loop
  • Space: O(n) - เก็บ Array ขนาด n+1

การสังเกตรูปแบบ (Pattern Observation)

Sequence นี้คือ Stern's Diatomic Series (OEIS A002487) ค่าสูงสุดเพิ่มขึ้นช้า และเกี่ยวข้องกับ Fibonacci Numbers:

  • ค่าสูงสุดที่ Index = Fibonacci Numbers
  • Max(A[0..Fₖ]) = Fₖ₋₁ (ประมาณ)

วิธีหา Max โดยไม่สร้าง Array ทั้งหมด (O(log n))

def max_generated_optimized(n):
    """หา Max แบบไม่สร้าง Array ทั้งหมด ใช้ Property ของ Stern's Sequence"""
    # สำหรับ n ≤ 10^6 ใช้วิธี O(n) ก็พอ
    # วิธี O(log phức tạp) ต้องใช้ Recursive Formula
    pass  # อาจ Implement เพิ่มเติมถ้าจำเป็น


# LeetCode 1646: "Get Maximum in Generated Array"
# Constraints: 0 <= n <= 100 (ในโจทย์ต้นฉบับ) แต่โค้ดนี้ทำงานได้ถึง n = 10^6+

คำแนะนำ

  • ใช้ Loop แบบ Bottom-up (Iterative) เร็วกว่า Recursive มาก
  • Index เริ่มที่ 0 จนถึง n (ขนาด n+1)
  • Integer Division // ใน Python 3 ให้ผลลัพธ์เป็น Int อยู่แล้ว
  • LeetCode Problem 1646: "Get Maximum in Generated Array"