帕斯卡三角形第 N 行中的奇數

---

問題陳述包括計算帕斯卡三角形第 N 行中的奇數。

帕斯卡三角形是一個三角形陣列，其中每一行代表二項式表示式展開中的二項式係數。帕斯卡三角形如下所示：

                              1
                          1        1
                      1        2        1
                   1      3         3       1
               1       4       6        4      1

可以使用相同的邏輯進一步擴充套件三角形。帕斯卡三角形中的每個值都代表二項式係數，從 n=0 開始作為行，每一行中的每個值都代表 $\mathrm{^nC_{r}}$，其中 r 的範圍從 r=0 到 r=n。

注意：對於每一行 N，共有 (N+1) 個項。

在這個問題中，我們將得到輸入中的數字 N，我們的任務是計算帕斯卡三角形第 N 行中奇數的數量。

讓我們透過以下示例瞭解這個問題。

輸入

N=5

輸出

4

解釋 - 輸入數字是 5。帕斯卡三角形第 5 行共有 6 個項，即 1、5、10、10、5 和 1，可以使用公式 $\mathrm{^5C_{r}}$（其中 r 的範圍為 0 到 5）或使用帕斯卡三角形計算。

帕斯卡三角形第 5 行中的奇數個數為 4，即 1、5、5 和 1，這就是所需的輸出。

輸入

N=10

輸出

4

解釋 - 給定的輸入是 10，這意味著我們需要計算帕斯卡三角形第 10 行中的奇數。第 10 行的二項式係數的值將是 1、10、45、120、210、252、210、120、45、10 和 1。奇數項的數量為 4，這就是所需的輸出。

讓我們瞭解計算帕斯卡三角形任意第 N 行中奇數個數的演算法。

演算法

存在一個數學關係，可以給出帕斯卡三角形第 N 行中奇數的數量。該定理指出，帕斯卡三角形第 N 行中奇數的數量等於 2 的冪，其中冪是 N 的二進位制表示中 1 的個數。

讓我們用一個例子來理解這個定理。

假設我們需要計算帕斯卡三角形第 10 行中的奇數。10 的二進位制表示是 1010，即 $\mathrm{2^{3}+2^{1}=8+2=10}$。10 的二進位制表示中 1 的個數是 2。

根據該定理，帕斯卡三角形第 N 行中奇數的數量將等於 2 的冪，其中冪是 N 的二進位制表示中 1 的個數，

第 10 行中奇數的數量 $\mathrm{2^{2}=4}$

為了計算帕斯卡三角形第 N 行中奇數的數量，我們將在我們的方法中使用上述定理。

方法

為了獲得奇數的計數，在我們的方法中實現演算法需要遵循以下步驟：

• 我們將建立一個函式來計算 N 的二進位制表示中 1 的個數。

• 初始化一個變數來計算 1 的個數。然後，我們將迭代一個 while 迴圈，直到 N 大於 0，我們將透過獲取 N 和 1 的 AND 來更新計數，因為它只有在兩個位都為 1 時才返回 1，否則運算子返回 0。同時，我們將透過右移 (>>) 1 來不斷更新 N。

• 一旦我們得到 N 的二進位制表示中 1 的個數，我們將使用 pow() 函式計算 2 的冪來找到奇數的個數。

• 返回 $\mathrm{2^{1的個數}}$ 的值，這將是所需的輸出。

示例

//C++ code to find the number of odd numbers in the N-th row of Pascal's Triangle

#include <bits/stdc++.h>

using namespace std;

//function to find the number of set bits in binary representation of N
int numberofones(int N){
    int a=0;  //to store the number of set bits
    //iterating in the loop to count the set bits
    while(N>0){ 
        
        a = a + (N&1);  //update a by adding 1 if there is a set bit in N
        
        N = N>>1;  //right shift N by 1 to check for other set bits
    }
    
    return a;  //return number of 1's in N
}

//function to get the count of number of odd numbers in N-th row
int numberofodds(int N){
    int x;  //to store the number of set bits of N
    x=numberofones(N);  //calling the function to store number of set bits of N in x 
    
    int ans;  //to store count of odd numbers
    ans=pow(2,x);  //number of odd numbers equal to the 2 raised to no of set bits in N
    
    return ans; //return the count
}

int main()
{
    int N;  //for taking the input
    N=25;
    //calling the function
    cout<<"Count of odd numbers in the "<<N<<"th row of Pascal's triangle : "<<numberofodds(N)<<endl;
    
    N=53;
    cout<<"Count of odd numbers in the "<<N<<"th row of Pascal's triangle : "<<numberofodds(N)<<endl;

    return 0;
}

輸出

Count of odd numbers in the 25th row of Pascal's triangle : 8
Count of odd numbers in the 53th row of Pascal's triangle : 16

時間複雜度：O(N) 計算 N 的設定位數所需的時間。

空間複雜度：O(1) 因為沒有額外空間來查詢奇數的個數。

結論

本文討論了計算帕斯卡三角形第 N 行中奇數個數的問題。我們使用 C++ 中的數學定理（關於帕斯卡三角形第 N 行中奇數個數）以高效的方法解決了這個問題。

我希望您閱讀本文後能理解這個問題和方法。