2017-12-12 28 views
5

Dưới đây là đoạn code đệ quy trong câu hỏi:làm thế nào để xác định đầu ra của hàm đệ quy phức tạp bằng tay

def trace(a, b): 
    if (a > b): 
     return -1 
    elif (a == b): 
     print (a * a) 
     return a * a 
    else: 
     m = (a + b)/2 
     return trace (a, m) + trace (m + 1, b) 

x=trace(1,4) 

trong khi tôi không chắc chắn những gì chức năng này là nghĩa vụ phải làm, chúng ta có nghĩa vụ phải tìm đầu ra của x=trace(1,4) cùng với giá trị của x, bằng tay (nghĩa là chúng ta không thể sử dụng nhàn rỗi để giúp chúng ta).

Sau một thời gian, tôi xác định rằng hàm sẽ in 1 và 12.25, sẽ là đầu ra khi gán x thành trace(1,4).

Tuy nhiên, tôi không biết cách xác định giá trị của X sẽ là bao nhiêu. Mặc dù câu trả lời là -91,75, tôi không có manh mối nhỏ như thế nào nó có nguồn gốc (mặc dù tôi biết làm thế nào, nó sẽ mất lứa tuổi để đến với câu trả lời này, và tôi không chắc chắn làm thế nào chúng ta có thể nhanh chóng đến với giải pháp trong một khoảng thời gian ngắn như khi viết bài kiểm tra).

Cảm ơn trước sự giúp đỡ của bạn!

+2

Dòng thứ 8 phải là 'm = (a + b) // 2'. Bằng cách này, nó sẽ hoạt động tương tự trong Python2 và Python3. –

+0

@EricDuminil: Jupp, đây chắc chắn là một câu hỏi Python 2, nhưng có thể được thực hiện để làm việc trong Python 3 bằng cách sửa nó theo cách của bạn. – Sherlock70

Trả lời

1

có một cái nhìn tại những dòng này:

m = (a + b)/2 
return trace(a, m) + ... 

những dòng này chỉ được thực hiện nếu b lớn hơn a. Điều đó có nghĩa là m sẽ luôn lớn hơn a và cuộc gọi hàm đệ quy đầu tiên có cùng một vấn đề. Với các giá trị a = 1b > a, m hội tụ thành 1. Về lý thuyết, đệ quy không bao giờ kết thúc kể từ m sẽ không bao giờ là 1.0 trở xuống. Tuy nhiên, độ chính xác phao bị hạn chế do đó có một điểm (sau nhiều lần gọi đệ quy), nơi bộ xử lý không thể khác nhau m từ 1.0. Tại thời điểm này, elif (a == b): trở thành sự thật và dừng đệ quy. Điều đó không giải thích tại sao kết quả là -91.75, nhưng nó cho thấy lý do tại sao nó gần như không thể hiển thị tất cả các cuộc gọi đệ quy trong một sơ đồ hoặc cây hoặc sth. Tôi hy vọng nó sẽ giúp.

+0

Vâng, tôi đã có thể xác định rằng về phía cuối, khi nó yêu cầu dấu vết trả lại (a, m) + dấu vết (m + 1, b), dấu vết đó (a, m) sẽ hội tụ theo hướng in (1), trong khi dấu vết (m + 1, b) sẽ hội tụ theo hướng in (12), có vẻ phù hợp với kết quả trong IDLE. Tôi giả định -91,75 đến từ bao nhiêu cuộc gọi đệ quy cần cho m là 1,0 theo IDLE. Tôi chỉ không biết làm thế nào ai đó sẽ xác định điều này bằng bút và giấy. – rexorsist

2

Trước hết, tôi đã lừa. Với bộ ngực của tôi ở đây là một số gợi ý: Chức năng này chắc chắn không dành cho Python 3! Lý do là toán tử /. Trong Python 2 nó dẫn đến số nguyên trong Python3 nó kết quả nổi. Vì vậy, lưu ý điều kiện tiên quyết này ở đây là giải pháp của tôi:

Chức năng này không phức tạp. Kiểu dữ liệu của mỗi biến và tất cả các biến của bạn là số nguyên! m sẽ luôn là một số nguyên. x là 30. Mức đệ quy là ba, bằng bảy cuộc gọi đến hàm của bạn (bao gồm cả hàm đầu tiên). Và đây là cách bạn đi về những thứ như thế này: Lấy một số giấy và một cây bút và chỉ viết xuống từng bước.

  1. Đầu vào là: a = 1 và b = 4 dẫn đến phần khác trong chức năng của bạn ... không có đầu ra cho đến thời điểm này. Có m được tính là (1 + 4)/2. Trong cuốn sách của tôi là 2,5. Nhưng điều này được làm tròn thành 2, bởi vì chúng ta có số nguyên. Sau đó, đệ quy bắt đầu bằng hai cuộc gọi (1,2) và (3,4)
  2. Hãy xem (1,2): a = 1 và b = 2. Một lần nữa, không có đầu ra và chúng ta đi đến phần khác: m được tính là 3/2, là 1,5 được làm tròn thành 1. Một lần nữa hai hàm của hàm có tham số mới (1,1) và (2, 2). Lưu ý rằng cả hai cuộc gọi bây giờ sẽ nhập phần elif của hàm và mỗi cuộc gọi sẽ tạo ra một đầu ra và một giá trị trả lại. Bạn có thể thay thế (1,1) bằng 1 và (2,2) với 4. Phép đệ quy được thực hiện ở đây, và kết quả của dấu vết (1,2) trong 5. Hãy nhìn vào nhánh khác của đệ quy.
  3. Đầu vào là = 3 và b = 4 dẫn đến một cặp cuộc gọi khác với các thông số sau: (3,3) và (4,4). Tôi nghĩ rằng bây giờ bạn sẽ nhận được hang của nó. Phần thú vị là cộng tất cả các giá trị trả lại theo cách chúng được cung cấp.

Làm như thế nào: Nó tổng hợp tất cả các ô của tất cả các số nguyên giữa a và b.

+0

Cảm ơn bạn rất nhiều vì sự giúp đỡ của bạn. Nó không bao giờ xảy ra với tôi nếu mã này có thể có nghĩa là cho Python 2. Điều này rất có thể là một lỗi đánh máy từ giáo sư của tôi vì nó có nghĩa là cho Python 3, đó là gây phiền nhiễu vì tôi đã dành nhiều giờ cố gắng để xác định kết quả với bút và giấy . Việc sử dụng các số nguyên chỉ có ý nghĩa hơn và làm cho việc này trở nên dễ dàng hơn nhiều. Cảm ơn một lần nữa! – rexorsist

+0

Bạn được chào đón. – Sherlock70

+0

@rexorsist: Sooo, bạn nghĩ sao? Câu trả lời có thể chấp nhận được, hay nó thiếu gì? – Sherlock70

Các vấn đề liên quan