2008-12-10 37 views
5

Tôi nhận ra rằng có một mô hình rõ ràng trong đầu ra này, tôi chỉ muốn biết tại sao REPL của lispbox hủy bỏ khi tôi cố gắng chạy bất cứ điều gì> 52. Ngoài ra, mọi đề xuất về cải thiện mã được chào đón nhiều hơn.^-^Câu hỏi Odd liên quan đến dự án euler 72 (lisp)

(defun count-reduced-fractions (n d sum) 
    (setf g (gcd n d)) 
    (if (equal 1 d) 
     (return-from count-reduced-fractions sum) 
     (if (zerop n) 
      (if (= 1 g) 
       (count-reduced-fractions (1- d) (1- d) (1+ sum)) 
       (count-reduced-fractions (1- d) (1- d) sum)) 
      (if (= 1 g) 
       (count-reduced-fractions (1- n) d (1+ sum)) 
       (count-reduced-fractions (1- n) d sum))))) 

Tất cả tôi nhận được khi tôi gọi

(count-reduced-fractions 53 53 0)

; Đánh giá hủy bỏ

Nó không có ý nghĩa nhiều với tôi , xem xét nó sẽ chạy (và trả lại kết quả chính xác) trên tất cả các số dưới đó, và tôi có thể (nếu tôi muốn) làm 53 trong đầu của tôi, trên giấy, hoặc một dòng tại một thời điểm trong lisp. Tôi thậm chí còn thử nghiệm trên nhiều con số khác nhau lớn hơn 53 để chắc chắn rằng nó không phải là cụ thể cho 53. Không có gì hoạt động.

+0

Các điểm trong văn bản của bạn có biểu thị gì không? – Svante

+0

nó giống như một khuôn mặt cười.^- ^,^_ ^, :), v.v. v.v. –

+0

Tôi biết biểu tượng cảm xúc, ý tôi là điểm "......". – Svante

Trả lời

0

Có thể là tràn ngăn xếp (heh).

+0

bạn có ý nghĩa thực sự? – Haoest

+0

Nếu nó là một thực tế, ông chắc chắn đã tận dụng nó không chính xác. –

3

Tôi đoán là có giới hạn chiều sâu ngăn xếp tích hợp với lispbox. Vì Lisp thường không đảm bảo các hàm đệ quy đuôi sử dụng không gian ngăn xếp không đổi, nên có thể mọi yêu cầu đếm đếm giảm phân số sẽ thêm một lớp khác trên ngăn xếp.

Nhân tiện, SBCL chạy thuật toán này mà không gặp sự cố.

* (count-reduced-fractions 53 53 0) 
881 

* (count-reduced-fractions 100 100 0) 
3043 
1

Như một vấn đề về phong cách, bạn có thể tạo d và tổng hợp tùy chọn.

(defun test (n &optional (d n) (sum 0)) ..) 
6

Hành vi này gợi ý tối ưu hóa cuộc gọi đuôi bị thiếu, để đệ quy của bạn thổi ngăn xếp. Một lý do có thể là bạn đã tối ưu hóa gỡ lỗi được gỡ lỗi.

Nhân tiện, bạn không cần thực hiện cuộc gọi rõ ràng đến return-from. Kể từ sum là một biểu tượng tự đánh giá, bạn có thể thay đổi dòng này

(return-from count-reduced-fractions sum)

để

sum

chỉnh sửa: Giải thích về sự thay đổi đề xuất: "tổng" để đánh giá giá trị của riêng mình, mà trở thành giá trị trả về của câu lệnh "if", trong đó (vì đây là câu lệnh cuối cùng trong defun) trở thành giá trị trả về của hàm.

chỉnh sửa: Giải thích về tối ưu hóa declaimed: Bạn có thể thêm dòng sau vào cấp cao nhất của bạn:

(declaim (optimize (speed 3) 
        (debug 0)))

hoặc sử dụng như nhau, nhưng với declare thay vì declaim như báo cáo kết quả đầu tiên trong chức năng của bạn. Bạn cũng có thể thử (khoảng cách 3) và (độ an toàn 0) nếu nó không hoạt động.

Tối ưu hóa cuộc gọi đuôi có nghĩa là cuộc gọi hàm có giá trị trả về được trả về trực tiếp được dịch thành thay thế khung trên ngăn xếp (thay vì xếp chồng), thực hiện "làm phẳng" hàm gọi đệ quy thành vòng lặp và loại bỏ đệ quy các cuộc gọi hàm.Điều này làm cho việc gỡ lỗi trở nên khó khăn hơn một chút, bởi vì không có các cuộc gọi chức năng nào mà bạn mong đợi chúng, resp. bạn không biết làm thế nào "sâu" vào một đệ quy một lỗi xảy ra (cũng giống như nếu bạn đã viết một vòng lặp để bắt đầu với). Môi trường của bạn có thể thực hiện một số tuyên bố mặc định mà bạn phải ghi đè để bật TCO.

chỉnh sửa: Chỉ cần xem lại câu hỏi này, g là gì? Tôi nghĩ rằng bạn thực sự muốn

(let ((g (gcd n d))) 
    ;; ... 
) 
+0

dường như kéo dài tuổi thọ của hàm, nhưng không nhiều. –

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