Hàng thứ n của tam giác pascal trong c

Tam giác Pascal có thể được tạo như sau. Ở hàng trên cùng, có một mảng gồm 1. Hàng tiếp theo được tạo bằng cách thêm số ở trên và bên trái với số ở trên và bên phải, coi các phần tử trống là 0

Một vài hàng đầu tiên là
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

ví dụ 1
Đầu vào
n = 3
đầu ra
[1, 3, 3, 1]
Giải trình
Đây là hàng 3 trong
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]

Tính tam giác Pascal

Chúng ta có thể tính toán các giá trị tại Tam giác Pascal bằng Thuật toán lập trình động. Giá trị tại p[i][j] bằng p[i – 1][j] + p[i – 1][j – 1]. Do đó, chúng tôi có thể lặp lại cập nhật hàng (kích thước có thể được xác định trước)

1
2
3
4
5
6
7
8
9
10

vector<int> solve(int n) {
    vector<int> res(n + 1, 0);
    res[0] = 1;
    for (int i = 0; i <= n; ++ i) {
        for (int j = i; j > 0; -- j) {
            res[j] += res[j - 1];
        }
    }
    return res;
}

vector solve(int n) {
    vector res(n + 1, 0);
    res[0] = 1;
    for (int i = 0; i <= n; ++ i) {
        for (int j = i; j > 0; -- j) {
            res[j] += res[j - 1];
        }
    }
    return res;
}

Độ phức tạp thời gian là O(N^2) và độ phức tạp không gian là O(N)

Triển khai Tam giác Pascal

• Dạy Bé Lập Trình – Thuật Toán Pascal Và Ứng Dụng
• Bài tập mã hóa – Tam giác Pascal II – Giải pháp C ++ và Python
• Cách in Tam giác Pascal trong C++ (kèm mã nguồn)
• Tính hàng thứ n của tam giác Pascal bằng thuật toán lập trình động
• GoLang. Tạo Tam giác Pascal

–EOF (Blog máy tính & công nghệ cơ bản) —

Xếp hạng sao GD
đang tải

451 từ
Bài cuối. Hai con trỏ với thuật toán cửa sổ trượt để tính chuỗi con dài nhất có nhiều nhất K ký tự riêng biệt
Bài tiếp theo. Chuyển đổi một chuỗi thành định dạng trường hợp lạc đà trong C ++

URL Vĩnh viễn là. Tính toán hàng thứ n của tam giác Pascal bằng thuật toán lập trình động (Phiên bản AMP)

bài viết liên quan

• Dạy Lập Trình Cho Bé - Thuật Toán Lập Trình Động Tính Tổng Đường Đi Tối Thiểu Tam Giác

  Cho một mảng tam giác, trả về tổng đường dẫn tối thiểu từ trên xuống dưới. Cho mỗi…

• Dạy Bé Lập Trình - Thuật Toán Tam Giác Pascal Và Ứng Dụng

  Tam giác Pascal trông như thế này. [1] [1, 1] [1, 2, 1] [1, 3, 3,…

• Thuật toán tính giá trị của Tam giác Pascal

  Câu đố là tạo ra một vài hàng numRows đầu tiên của Tam giác Pascal. Bạn có…

• Dạy Lập Trình Cho Bé - Nhập Môn Thuật Toán Lập Trình Động

  Thuật toán lập trình động là gì?

  Tam giác Pascal là một trong những bài toán phổ biến nhất. Nó sắp xếp số theo hình tam giác. Nói cách khác, Nó là một mảng có dạng tam giác bao gồm các hệ số nhị thức. Chương trình Tam giác Pascal trong ngôn ngữ C có thể được thực hiện theo nhiều cách khác nhau bao gồm cách tiếp cận vũ phu sau đó chúng ta có thể tối ưu hóa mã để giảm độ phức tạp về thời gian và độ phức tạp về không gian

  Phạm vi

  Trong bài viết này chúng ta sẽ tìm hiểu chi tiết về các khái niệm sau

  • Tam giác Pascal và các ví dụ của nó là gì?
  • Cách thực hiện tam giác pascal trong C
  • Các phương pháp thực hiện tam giác pascal trong C
    • Cách tiếp cận vũ phu
    • Phương pháp tối ưu hóa thời gian phức tạp
    • Phương pháp tiếp cận độ phức tạp không gian được tối ưu hóa

  Tam giác Pascal là gì?

  Tam giác Pascal là một sự sắp xếp (mảng) hình tam giác của các số hiển thị các hệ số nếu một biểu thức nhị thức được mở rộng. Các số bên trong mẫu tam giác Pascal được thiết kế sao cho mỗi số sẽ là tổng của hai số gần nhất ở hàng trên của tam giác và các số ở hai cực của mỗi hàng của tam giác sẽ là 1

  Nó là một mảng tam giác gồm các hệ số nhị thức được sử dụng rộng rãi trong các bài toán đại số, lý thuyết xác suất và Tổ hợp. Tam giác Pascal là tam giác đặc biệt được đặt tên theo nhà toán học người Pháp Blaise Pascal. Nói chung, tam giác Pascal được sử dụng để tìm kết quả của một đồng xu, hệ số khai triển nhị thức theo xác suất, v.v.

  Bây giờ chúng ta hãy tìm hiểu thêm về mô hình tam giác pascal với sự trợ giúp của một ví dụ

  Ví dụ về Tam giác Pascal

  Trên đây là một biểu diễn của tam giác pascal trong đó các số được sắp xếp theo cách mà chúng ta có 1 ở cả hai cực trị hoặc các cạnh của tam giác cho đến hết. Các số ở giữa tam giác là tổng của hai số ở hàng trên. Hàng trên cùng trong tam giác pascal được coi là hàng thứ 0 của tam giác. Tiếp theo là hàng tiếp theo được gọi là hàng đầu tiên và sau đó là hàng thứ 2, v.v. Phần tử ở ngoài cùng bên trái của một hàng được coi là phần tử thứ 0 trong hàng đó. Với quy ước này, số phần tử bên trong hàng thứ n bằng (n+1) phần tử trong hàng cụ thể đó

  Tam giác Pascal được thiết kế bằng cách có 1 là phần tử đầu tiên và cuối cùng của một hàng và bằng cách dễ dàng cộng các cặp số liên tiếp ở hàng trước rồi viết chúng vào dòng mới

  Làm thế nào để viết các chương trình tam giác Pascal trong C?

  Như chúng ta đã thảo luận ở các phần trước, tam giác Pascal là một tam giác đặc biệt có sự sắp xếp các hệ số nhị thức. Các số trong tam giác pascal được sắp xếp sao cho mỗi hàng của tam giác bắt đầu bằng 1 và các phần tử ở giữa là tổng của hai phần tử gần nhất của hàng trên

  Bây giờ, hãy hiểu cách chúng ta có thể thực hiện hoặc viết chương trình tam giác Pascal bằng ngôn ngữ C

  Chúng ta sẽ viết hàm dựng tam giác pascal trong C, nhập vào là n và in ra n dòng đầu tiên của tam giác Pascal

  Chúng ta có thể thực hiện tam giác Pascal trong C theo ba cách khác nhau như sau. -

  1. Cách tiếp cận vũ phu
  2. Phương pháp tối ưu hóa thời gian phức tạp
  3. Phương pháp tiếp cận độ phức tạp không gian được tối ưu hóa

  Bây giờ, hãy hiểu mọi cách tiếp cận với việc thực hiện nó

  Phương pháp 1. Lực lượng vũ phu

  Giới thiệu

  Trong cách tiếp cận này, chúng tôi sẽ sử dụng một cách tiếp cận đơn giản để in tam giác Pascal bằng cách sử dụng định lý nhị thức. Ở đây chúng tôi đã sử dụng các công thức giai thừa và kết hợp để thực hiện chương trình Tam giác Pascal trong C

  Bây giờ chúng ta cùng xem code của chương trình để hiểu rõ hơn cách tiếp cận

  cú pháp

  //Pascal Triangle program in C
  #include 
  
  int fact(int n) //function to calculate factorial of a number
  {
    int a;
  
    for (a = 1; n > 1; n--)
      a *= n;
  
    return a;
  }
  
  int combination(int n, int r)
  {
    return fact(n) / (fact(n - r) * fact(r)); // using the mathematical formula of combination nCr
  }
  
  int main()
  {
    int rows;
    int i, j;
  
    //number of rows of pascal's triangle to be printed
    printf("Enter Number of Rows: ");
    scanf("%d", &rows);
  
    for (i = 0; i <= rows; i++)
    {
      for (j = 0; j <= rows - i; j++)
        printf("  ");
  
      for (j = 0; j <= i; j++)
        printf(" %3d", combination(i, j));
  
      printf("\n");
    }
    return 0;
  }
  đầu ra
  Enter Number of Rows: 8
                       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
  ví dụ
  Chương trình tam giác Pascal trên trong C được thực hiện bằng cách sử dụng công thức kết hợp bên trong chương trình thông qua hàm tổ hợp(int n, int r). Theo chương trình trên, chúng ta đã sử dụng biến rows có kiểu int và nó biểu thị số hàng của tam giác pascal sẽ được in
  Sau đó, bên trong phương thức main(), chúng ta sẽ gọi hàm tổ hợp(). Bên trong hàm kết hợp, chúng tôi đang sử dụng công thức kết hợp i. e, (giai thừa(n) / ( giai thừa(n-r) * giai thừa(r)), trong đó n là một số và chúng ta phải chọn r số từ n số. Bây giờ áp dụng công thức này để tính các số cần chèn trong tam giác pascal
  
  
  
  phức tạp
  Vì chúng tôi đang sử dụng ba vòng lặp lồng nhau nên Độ phức tạp về thời gian của cách tiếp cận trên là O(n3)O(n^3)O(n3)
  Chúng tôi không sử dụng bất kỳ không gian thừa nào để in Tam giác Pascal, vì vậy Độ phức tạp không gian của phương pháp trên là O(1)

  Phương pháp 2. Thời gian được tối ưu hóa (O(n2)(O(n^2)(O(n2) Thời gian và O(n2)O(n^2)O(n2) Không gian bổ sung

  Giới thiệu

  Không giống như cách tiếp cận trên, ở đây chúng tôi sẽ tối ưu hóa mã của mình và sử dụng một cách tiếp cận khác để in Tam giác Pascal lên đến số lượng hàng cần thiết. Như chúng ta biết rằng mọi phần tử ở giữa tam giác pascal là tổng của hai phần tử trên. Do đó, trong phương pháp này, chúng tôi sẽ sử dụng mảng 2 chiều sẽ lưu trữ các giá trị của các hàng trước đó để chúng tôi có thể sử dụng các giá trị đó để tạo các giá trị trong hàng mới

  Bây giờ, chúng ta hãy xem mã để hiểu cách tiếp cận được tối ưu hóa để thực hiện chương trình tam giác pascal trong C

  cú pháp

  //Optimized approach for implementing
  //pascal triangle program in C
  #include
  
  void pascalTriangle(int n) {
  int arr[n][n]; //Initializing 2-D array
    
  for (int j = 0; j < n; j++) {
      for (int i = 0; i <= j; i++) {
      // Initializing 1 as the first and last value of the row
      if (j == i || i == 0)
          arr[j][i] = 1;
      // middle elements are sum of values
      // in the above row
      else 
          arr[j][i] = arr[j-1][i-1] + arr[j-1][i];
          printf("%3d ", arr[j][i]);
      }
      printf("\n");
      }
  }
  int main() {
  int rows;
      //number of rows of pascal's triangle to be printed
      printf("Enter the number of rows: ");
      scanf("%d",&rows);
      pascalTriangle(rows); 
      return 0;
  }
  đầu ra
  Enter the number of rows: 6
    1
    1   1
    1   2   1
    1   3   3   1
    1   4   6   4   1
    1   5  10  10   5   1
  ví dụ
  Chương trình tam giác pascal ở trên trong C đạt được bằng cách sử dụng mảng 2 chiều. Bên trong mảng 2 chiều, chúng ta sẽ lưu trữ các giá trị của hàng trước và các giá trị đó có thể được sử dụng để tính các giá trị trong hàng tiếp theo. Sau đó, chúng tôi sử dụng các vòng lặp để lặp qua từng hàng của tam giác và sau đó chúng tôi chèn 1 làm giá trị đầu tiên và cuối cùng của mỗi hàng. Bây giờ, ta tính giá trị các phần tử ở giữa bằng cách thực hiện phép tính tổng hai phần tử của hàng trên trong tam giác pascal. Sau đó, chúng tôi in hình tam giác cần thiết lên đến một số hàng (hàng) được chỉ định như đã thấy trong đầu ra
  phức tạp
  Vì chúng ta đang sử dụng hai vòng lặp lồng nhau nên Độ phức tạp về thời gian của phương pháp trên là O(n2)O(n^2)O(n2)
  Vì chúng ta đang sử dụng mảng 2 chiều nên độ phức tạp Không gian của cách tiếp cận trên là O(n2)O(n^2)O(n2)

  Phương pháp 3. Không gian được tối ưu hóa

  Giới thiệu

  Khác với cách làm trên, ở đây chúng ta sẽ sử dụng một cách tối ưu hơn để xây dựng chương trình tam giác pascal trong C. Vì phần tử đầu tiên và cuối cùng của một hàng chứa 1 nên chúng ta có thể tính các giá trị còn lại của một hàng mà không cần sử dụng thêm khoảng trắng

  Bây giờ, chúng ta hãy xem mã để hiểu cách triển khai tối ưu hơn chương trình tam giác pascal trong C

  cú pháp

  // Pascal Triangle program in C
  //without using extra space
  #include 
  
  void pascalTriangle(int n) {
      for (int j = 1; j <= n; j++) {
          int B = 1; // Initializing the first and last element of a row 
          for (int i = 1; i <= j; i++) {
              printf("%d ", B); // The first value in a row is always 1
              B = B * (j - i) / i; // calculating middle elements of a row
          }
          printf("\n");
      }
  }
  int main() {
      int nRows;
      //number of rows of pascal's triangle to be printed
      printf("Enter number of rows: ");
      scanf("%d", &nRows);
      pascalTriangle(nRows);
      return 0;
  }
  đầu ra
  ________số 8_______
  ví dụ
  Chương trình tam giác pascal ở trên trong C có thể đạt được mà không cần sử dụng thêm dung lượng. Ở đây, chúng tôi đã sử dụng khởi tạo giá trị đầu tiên và cuối cùng của mỗi hàng là 1
  Chúng tôi đã tính toán giá trị trung bình bằng cách sử dụng giá trị đầu tiên và giá trị cuối cùng. Công thức mà chúng tôi đã sử dụng là. B = B * (j - i) / tôi. Sau đó, chúng tôi đã in hình tam giác cần thiết lên đến số hàng đã chỉ định (nRows được cung cấp ở đầu vào) ở đầu ra
  phức tạp
  Vì chúng ta đang sử dụng hai vòng lặp lồng nhau nên Độ phức tạp về thời gian của phương pháp trên là O(n2)O(n^2)O(n2)
  Chúng tôi không sử dụng bất kỳ không gian thừa nào để in Tam giác Pascal, vì vậy Độ phức tạp không gian của phương pháp trên là O(1)

  Ghi chú. Cách tiếp cận tốt nhất để thực hiện chương trình Tam giác Pascal trong C là Phương pháp 3 trong đó độ phức tạp về thời gian và không gian sẽ lần lượt là O(n2)O(n^2)O(n2) và O(1) nhưng có thể có vấn đề về số nguyên

  Làm thế nào để code tam giác Pascal trong C?

  Lập trình .

  #bao gồm < stdio. giờ >

  giai thừa dài(int);

  int chính ()

  int i, n, c;

  printf("Nhập số hàng bạn muốn xem trong tam giác pascal\n");

  scanf("%d", &n);

  for (i = 0; i < n; i++) {

  Tổng của hàng thứ n trong tam giác Pascal là bao nhiêu?

  Tổng các mục ở hàng thứ n của tam giác Pascal là 2n .

  Hàng thứ 0 của tam giác Pascal là gì?

  Có thể dựng tam giác theo cách sau. Ở hàng 0 ( hàng trên cùng ), có một mục khác 0 duy nhất 1. Mỗi mục nhập của mỗi hàng tiếp theo được tạo bằng cách thêm số ở trên và bên trái với số ở trên và bên phải, coi các mục trống là 0.

  Hàng thứ 4 của tam giác Pascal là gì?

  ma thuật 11. Mỗi hàng đại diện cho các số trong quyền hạn của 11 (mang chữ số nếu nó không phải là một số). Ví dụ: các số ở hàng 4 là 1, 4, 6, 4 và 1 và 11^4 bằng 14,641