C++ 帕斯卡三角形中第N行的奇数

该问题的陈述包括计算帕斯卡三角形中第N行的奇数个数。

帕斯卡三角形是一个由每行代表二项式展开中的二项系数构成的三角形数组。帕斯卡三角形如下所示：

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

这个三角形可以用相同的逻辑进行进一步扩展。Pascal三角形中的每个值代表自n=0起的二项式系数，并且每行中的每个值表示\mathrm{^nC_{r}}，其中r在r=0到r=n范围内变化。

注意 ：对于每一行，总共有(N+1)个项。

在这个问题中，我们将会在输入中得到一个数字N，我们的任务是统计Pascal三角形中第N行中的奇数的个数。

让我们通过下面的例子来理解这个问题。

输入

N=5

输出

4

解释 − 输入的数字是5。帕斯卡三角形的第5行将有6个项，即1、5、10、10、5和1，可以使用公式^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，这是需要的输出。

让我们了解计算Pascal三角形的第N行中奇数个数的算法。

算法

有一个数学关系给出了帕斯卡三角形的第N行中奇数的数量。该定理规定，第N行中的奇数的数量等于N的二进制表示中1的数量的2的幂。

让我们用一个例子来理解该定理。

假设我们需要计算帕斯卡三角形的第10行中的奇数个数。10的二进制表示为1010，即\mathrm{2^{3}+2^{1}=8+2=10}。10的二进制表示中1的数量为2。

根据该定理，帕斯卡三角形的第N行中奇数的数量将等于N的二进制表示中1的数量的2的幂，

第10行的奇数个数为\mathrm{2^{2}=4}

我们将在我们的方法中使用上述定理，以便计算帕斯卡三角形的第N行中奇数的数量。

方法

按照以下步骤实施我们的方法以获得奇数个数：

• 我们将创建一个函数来计算N的二进制表示中1的数量。

• 初始化一个变量来记录1的数量。然后，我们将在一个while循环中迭代，直到N大于0，我们将通过N和1的AND运算来更新计数，因为它只有在两个位都是1时才返回1，否则返回0。同时，我们将通过右移(>>)1来不断更新N。

• 一旦我们得到了N的二进制表示中1的数量，我们将通过计算2的1的数量的幂来找到奇数的数量，使用pow()函数。

• 返回\mathrm{2^{no:of:1’s}}的值，这将是所需的输出。

示例

//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(N) 因为没有额外的空间用于找到奇数的数量。

结论

本文讨论了在Pascal三角形的第N行中计算奇数个数的问题。我们使用了一个有效的方法来解决这个问题，在C++中使用了数学定理来计算Pascal三角形的第N行中奇数的数量。

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