帕斯卡三角形第 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 行中奇数个数）以高效的方法解决了这个问题。

我希望您阅读本文后能理解这个问题和方法。