2009-11-19 80 views
7

Tôi đang tìm kiếm giải thích về cách phiên bản đệ quy của tam giác pascal hoạt độngC++ Hình tam giác Pascal

Sau đây là dòng trả về đệ quy cho tam giác pascal.

int get_pascal(const int row_no,const int col_no) 
{ 
    if (row_no == 0) 
    { 
     return 1; 
    } 
    else if (row_no == 1) 
    { 
     return 1; 
    } 
    else if (col_no == 0) 
    { 
     return 1; 
    } 
    else if (col_no == row_no) 
    { 
     return 1; 
    } 
    else 
    { 
     return(get_pascal(row_no-1,col_no-1)+get_pascal(row_no-1,col_no)); 
    } 
} 

Tôi hiểu cách thuật toán hoạt động Điều tôi tự hỏi là cách đệ quy thực hiện công việc.

+1

Ông có thể viết đoạn code mẫu như một chức năng hoàn chỉnh? Nó sẽ dễ dàng hơn cho bạn để hiểu và bất cứ ai khác để trả lời. –

+0

Bạn có thể đăng toàn bộ mã pascalRecursive không? – BostonLogan

+0

vâng, xin lỗi tôi đã chỉnh sửa mục nhập của tôi bây giờ – starcorn

Trả lời

2

Hình tam giác của Pascal có thể nhận được từ việc thêm hai mục nhập phía trên hiện tại.

 
    | 0   1   2   3   column 
--+---------------------------------------------- 
0 | 1 (case 1) 
1 | 1 (case 2) 1 (case 2) 
2 | 1 (case 3) 2 (sum) 1 (case 4) 
3 | 1 (case 3) 3 (sum) 3 (sum) 1 (case 4) 

row 

vv ví dụ cột 2, hàng 3 = cột 2, dòng 2 + cột 1, dòng 2, nơi các trường hợp như sau:

if (row_no == 0) // case 1 
{ 
    return 1; 
} 
else if (row_no == 1) // case 2 
{ 
    return 1; 
} 
else if (col_no == 0) // case 3 
{ 
    return 1; 
} 
else if (col_no == row_no) // case 4 
{ 
    return 1; 
} 
else // return the sum 
    return pascalRecursive(height-1,width)+pascalRecursive(height-1,width-1); 
7

tam giác Pascal cơ bản là tổng của hai giá trị ngay lập tức ở trên nó ....

  1 
     1 1 
     1 2 1 
    1 3 3 1 

vv

  • Trong trường hợp này, số 1 thu được bằng cách thêm số 1 ở trên với khoảng trắng (0)
  • Đối với mã, tất cả số 1 được chiếm trong cột đầu tiên (0) hoặc khi hàng (col ==)

Đối với hai điều kiện biên giới này, chúng tôi mã trong trường hợp đặc biệt (để khởi tạo). Đoạn chính của đoạn mã (phần đệ quy) là logic thực tế.

(Điều kiện 'hàng == 1' là không cần thiết)

1

Dưới đây là cách đệ quy làm việc

We call v(i, j), it calls v(i - 1, j), which calls v(i - 2, j) and so on, 
until we reach the values that are already calculated (if you do caching), 
or the i and j that are on the border of our triangle. 

Then it goes back up eventually to v(i - 1, j), which now calls v(i - 2, j - 1), 
which goes all the way to the bottom again, and so on. 

.................................................................... 
        _ _ _ _ call v(i, j) _ _ _ _ _ 
       /       \ 
       /        \ 
      /        \ 
      call v(i - 1, j)      v(i - 1, j - 1) 
     /    \     /    \ 
     /     \    /    \ 
call v(i - 2, j) v(i - 2, j - 1) v(i - 2, j - 1) v(i - 2, j - 2) 
.................................................................... 

Nếu bạn cần để có được những giá trị thường xuyên, và nếu bạn có đủ bộ nhớ:

class PascalTriangle 
    # unlimited size cache 

    public 

    def initialize 
    @triangle = Array.new 
    end 

    def value(i, j) 
    triangle_at(i, j) 
    end 

    private 

    def triangle_at(i, j) 
    if i < j 
     return nil 
    end 

    if @triangle[i].nil?   
     @triangle[i] = Array.new(i + 1) 
    else 
     return @triangle[i][j] 
    end 

    if (i == 0 || j == 0 || i == j) 
     @triangle[i][j] = 1 
     return @triangle[i][j] 
    end 

    @triangle[i][j] = triangle_at(i - 1, j) + triangle_at(i - 1, j - 1) 
    end 
end 
4

Hãy tham khảo trang cho mã nguồn:

#include <stdio.h> 
int main() 
{ 
    int n, x, y, c, q; 
    printf("Pascal Triangle Program\n"); 
    printf("Enter the number of rows: "); 
    scanf("%d",&n); 

    for (y = 0; y < n; y++) 
    { 
     c = 1; 
     for(q = 0; q < n - y; q++) 
     { 
       printf("%3s", " "); 
     } 
     for (x = 0; x <= y; x++) 
     { 
       printf(" %3d ",c); 
       c = c * (y - x)/(x + 1); 
     } 
     printf("\n"); 
    } 
    printf("\n"); 
    return 0; 
    } 
.210

Kết quả sẽ là,

Chương trình Tam giác Pascal

Nhập số hàng: 11

        1 

           1  1 

          1  2  1 

         1  3  3  1 

         1  4  6  4  1 

        1  5  10  10  5  1 

       1  6  15  20  15  6  1 

      1  7  21  35  35  21  7  1 

      1  8  28  56  70  56  28  8  1 

     1  9  36  84 126 126  84  36  9  1 

    1  10  45 120 210 252 210 120  45  10  1 
+0

OP đang tìm kiếm một phiên bản đệ quy. Vẫn là một lặp đi lặp lại tốt đẹp. –

+0

'c = c * (y - x)/(x + 1);' có thể giải thích điều này –

30

thuật toán của bạn có chứa một vài vị từ không cần thiết cho các trường hợp cơ sở. Có thể tuyên bố đơn giản hơn như sau:

int pascal(int row, int col) { 
    if (col == 0 || col == row) { 
    return 1; 
    } else { 
    return pascal(row - 1, col - 1) + pascal(row - 1, col); 
    } 
} 

Điều này tất nhiên giả định rằng bạn đã đảm bảo rằng đối số được chuyển đến hàm là số nguyên không âm; bạn luôn có thể bao gồm một xác nhận nếu bạn không thể áp đặt một bảo đảm như vậy từ bên ngoài chức năng.

+1

là nó có hiệu quả dường như tính toàn bộ kim tự tháp cho mọi số –

2

Đây là mã của @kathir-softwareandfinance với tên biến dễ đọc hơn và ý nghĩa hơn

#include <stdio.h> 

int main() 
{ 
    int nOfRows, cols, rows, value, nOfSpace; 
    printf("Pascal Triangle Program\n"); 
    printf("Enter the number of rows: "); 
    scanf("%d",&nOfRows); 

    for (rows = 0; rows < nOfRows; rows++) 
    { 
    value = 1; 
    for(nOfSpace = 0; nOfSpace < nOfRows - rows; nOfSpace++) 
    { 
     printf("%3s", " "); 
    } 

    for (cols = 0; cols <= rows; cols++) 
    { 
     printf(" %3d ",value); 
     value = value * (rows - cols)/(cols + 1); 
    } 
    printf("\n"); 
    } 
    printf("\n"); 

    return 0; 
} 
3

Cách tối ưu nhất là cái này:

int pascal(int row, int col) { 
    if (col == 0 || col == row) return 1; 
    else if(col == 1 || (col + 1) == row) return row; 
    else return pascal(row - 1, col - 1) + pascal(row - 1, col); 
} 

Không giống như các thuật toán Fox của nó ngăn chặn các cuộc gọi đệ quy cho các giá trị có thể dễ dàng tính toán ngay từ các giá trị đầu vào.

0

Sử dụng phương pháp tiếp cận tối ưu để tối ưu hóa; chỉ cần 1 lệnh trả về.

int f(int i, int j) { 
    return (
     (i <= 1 || !j || j == i) ? 1 : 
     (f(i - 1, j - 1) + f(i - 1, j)) 
    ); 
} 

thấy explanation

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