2012-12-07 664 views
5

Tôi đã viết một chương trình trong C để tính giá trị Ackermann cho 2 số nguyên không âm được người dùng nhập. Chương trình kiểm tra nếu các số nguyên không âm và nếu chúng được tính toán giá trị Ackermann của chúng và sau đó yêu cầu đầu vào hoặc thoát mới. Chương trình hoạt động tốt trong C và tôi không có vấn đề với nó. Đây là mã của tôi:Thực hiện thay thế hàm Ackermann trong C

int ackermann(int m, int n){ 
     if (m == 0) return n + 1; 
     if (n == 0) return ackermann(m - 1, 1); 
     return ackermann(m - 1, ackermann(m, n - 1)); 
} 

NHƯNG, trên thực tế, đối với các nhu cầu của một bài học đại học chúng tôi sử dụng một phiên bản sửa đổi của C (về cơ bản giống nhau nhưng với một số quy tắc cú pháp khác nhau) mà mô phỏng cú pháp và các quy tắc của Ngôn ngữ hội MIPS. Cụ thể hơn, chúng tôi sử dụng thanh ghi để thao tác tất cả dữ liệu ngoại trừ mảng và cấu trúc. Ngoài ra, chúng tôi không thể sử dụng cho các vòng lặp while, while, hoặc do-while và thay vào đó, chúng tôi sử dụng các câu lệnh nếugoto. Vì vậy, tôi đã viết chương trình sau bằng ngôn ngữ này (như tôi đã nói nó không quá C với cú pháp khác nhau). Vấn đề của tôi là nó chỉ hoạt động đối với đầu vào người dùng (x, 0) và (0, y) (x và y là số không âm). Nó không hoạt động (4,1), (3,2) và nói chung là tất cả các đầu vào không có số không. Tôi hiểu rằng nó không thể hoạt động hiệu quả với những con số rất lớn như (10,10) do các tính toán lớn này. Nhưng tôi muốn nó làm việc cho một số đầu vào đơn giản như Ackermann (3,1) == 13. Để biết thêm về chức năng Ackermann xin vui lòng xem này: http://en.wikipedia.org/wiki/Ackermann_function Đây là mã của tôi:

//Registers --- The basic difference from C is that we use registers to manipulate data 
int R0=0,R1,R2,R3,R4,R5,R6,R7,R8,R9,R10,R11,R12,R13,R14,R15,R16,R17,R18,R19,R20,R21, 
R22,R23,R24,R25,R26,R27,R28,R29,R30,R31; 

int ackermann(int m, int n){ 

    R4 = m; 
    R5 = n; 

    if(R4 != 0) 
     goto outer_else; 
    R6 = R5 + 1; 
    return R6; 

    outer_else: 
     if(R5 != 0) 
      goto inner_else; 
     R7 = R4 - 1; 
     R6 = ackermann(R7, 1); 
     return R6; 

     inner_else: 
      R8 = R5 - 1; 
      R9 = ackermann(R4, R8); 
      R10 = R4 - 1; 
      R6 = ackermann(R10, R9); 
      return R6; 
} 

Trả lời

6

Tôi nghĩ vấn đề của bạn là các giá trị đăng ký này được định nghĩa là các biến toàn cục và chúng được cập nhật bằng một cuộc gọi bên trong đến ackermann(), trong khi cuộc gọi bên ngoài phụ thuộc vào những giá trị đó không thay đổi. Ví dụ, hãy xem mệnh đề inner_else trong phiên bản đăng ký ackermann(): nó gọi ackermann(R4, R8) và trong tuyên bố tiếp theo tùy thuộc vào giá trị hiện tại của R4 nhưng cuộc gọi đệ quy sẽ làm thay đổi cài đặt R4 trước khi đạt đến câu lệnh gán.

Hai giải pháp chung:

  1. Xác định thanh ghi của bạn như biến cục bộ và để cho các trình biên dịch theo dõi mỗi cuộc gọi chức năng nhà nước cho bạn.

  2. Khi truy cập vào chức năng ackermann(), hãy lưu trạng thái của tất cả các thanh ghi theo cách thủ công và sau đó khôi phục lại khi thoát.

Mặc dù giải pháp 1 dễ dàng hơn, tôi cho rằng giáo viên của bạn có thể thích giải pháp 2 hơn, vì nó minh họa loại kỹ thuật được trình biên dịch sử dụng để xử lý đăng ký thực tế.

+0

Về giải pháp thứ hai, tôi nên đăng ký giải pháp nào và đăng ký? Ở đâu trong hàm tôi có nên khôi phục chúng (pop)? Cảm ơn câu trả lời của bạn :) – mgus

+0

Giải pháp an toàn, ngây thơ sẽ là lưu (khôi phục) tất cả các thanh ghi tại mục nhập (tất cả các điểm thoát). Một cách tiếp cận hiệu quả hơn sẽ là chỉ lưu các thanh ghi được sửa đổi bất cứ nơi nào trong hàm đệ quy và sau đó khôi phục lại các thanh ghi tương tự đó khi thoát. Hiệu quả nhất sẽ là tiết kiệm theo yêu cầu trước khi viết, chỉ tiết kiệm cho những thanh ghi thực sự thay đổi. Nhược điểm của tùy chọn thứ hai là bạn phải theo dõi các thanh ghi nào bạn đã sửa đổi (vì vậy bạn biết cái nào cần khôi phục), yêu cầu cấu trúc dữ liệu khác và một số logic bổ sung. –

+0

Tôi thích đi một cách an toàn .. Tôi đã thay đổi mã theo những gì bạn nói với tôi nhưng vẫn không hoạt động.Đầu tiên tôi đã sử dụng 6 biến toàn cục ** int a, b, c, d, e, f; ** và sau đó trong hàm Ackermann sau các phép gán ** R4 = m; R5 = n; ** Tôi đã thêm:/* PUSH */ a = R4; b = R5; c = R7; d = R8; e = R9; f = R10; và TRƯỚC KHI trở lại tôi đã thêm:/* POP */ a = R4; b = R5; c = R7; d = R8; e = R9; f = R10; Tôi đang làm gì sai? Xin hãy giúp :) Cảm ơn bạn @Marc Cohen – mgus