Giải phương trình chức năng lập trình

Question

Given:

F (F (n)) = n

F (F (n + 2) + 2) = n

F (0) = 1

trong đó n là số nguyên không âm. F (129) =?

Làm cách nào để chúng tôi có thể giải quyết các phương trình chức năng như vậy theo chương trình? Lựa chọn ngôn ngữ lập trình của tôi là Python.

Answer 1

Phương trình chức năng, theo thuật ngữ chung nhất, thực sự rất khó. Không phải ngẫu nhiên mà mỗi cuộc thi toán học quốc tế đều có một trong số đó, thường là nhìn vô tội như người bạn đã viết. Các phương pháp giải quyết chúng thay đổi từ cảm ứng đơn giản đến phân tích không gian Banach vô hạn chiều và phương pháp lập trình chung để giải quyết chúng là rất khó xảy ra.

Trong trường hợp đặc biệt này, đây là một cách tiếp cận thẳng về phía trước:

Giả sử đối với bất kỳ hai số nguyên m, n chúng ta có F (m) = F (n) = k. Nhưng sau đó m = F (F (m)) = F (k) = F (F (n)) = n: do đó m = n và F không bao giờ lấy cùng giá trị trên hai đầu vào khác nhau. Nhưng chúng ta biết rằng F (F (n)) = n = F (F (n + 2) +2) - do đó F (n) và F (n + 2) +2 phải là cùng một số - đó là để nói , F (n + 2) == F (n) - 2 == F (n-2) - 4 = .... Bây giờ chúng ta biết F (0) = 1, vì vậy F (1) = F (F (0)) = 0. Nhưng sau đó F (129) = F (127) - 2 = F (125) - 4 = ... = F (1) - 128 = -128

Vì vậy, có giải pháp của bạn - nhưng thuật toán cơ học để giải quyết bất kỳ biến thể nào không tồn tại.

Answer 2

Dựa trên những gì @ivancho và @aaronasterling đã nói, tôi đã có thể viết chương trình này nên làm như lừa:

def f(n): 
    if not n: 
     return 1 
    else: 
     return f(n-2)-2 

>>> f(4) 
-3 

Comment nếu đây không phải là những gì bạn đang sau