帕斯卡三角形第 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，也可以使用帕斯卡三角形。
帕斯卡三角形第五行奇数项的数量为 4，即 1、5、5 和 1，这是所需的输出。
输入
N=10
Output
4
解释− 输入为 10，这意味着我们需要计算帕斯卡三角形第 10 行中的奇数个数。第 10 行的二项式系数值为 1、10、45、120、210、252、210、120、45、10 和 1。奇数项的数量为 4，即所需的输出。
让我们理解计算帕斯卡三角形任意第 N 行中奇数个数的算法。
算法
存在一个数学关系，可以计算帕斯卡三角形第 N 行中奇数个数。该定理指出，第 N 行奇数的数量等于 N 的二进制表示中 1 的数量乘以 2。
让我们通过一个例子来理解这个定理。
假设我们需要计算帕斯卡三角形第 10 行中的奇数。 10 的二进制表示是 1010，即 $\mathrm{2^{3}+2^{1}=8+2=10}$。10 的二进制表示中 1 的个数为 2。
根据定理，帕斯卡三角形第 N 行奇数的个数等于 2 的二进制表示中 1 的个数。
第 10 行奇数的个数 $\mathrm{2^{2}=4}$
我们将在我们的方法中使用上述定理来计算帕斯卡三角形第 N 行奇数的个数。
方法
在我们的方法中，为了计算奇数的数量，实现算法的步骤如下:
我们将创建一个函数来计算 N 的二进制表示中 1 的数量。
初始化一个变量来表示 1 的数量。然后，我们将在 while 循环中迭代，直到 N 大于 0。在此期间，我们将通过对 N 和 1 进行与运算来更新计数，因为只有当两位都为 1 时，它才返回 1，否则运算符返回 0。同时，我们将继续通过右移 (>>) 1 来更新 N。
一旦我们获得了 N 的二进制表示中 1 的数量，我们将使用 pow() 函数计算 2 的 1 的数量，从而找到奇数的数量。
返回 $\mathrm{2^{no\:of\:1's}}$ 的值，这将是所需的输出。
示例
//C++ 代码用于查找杨辉三角第 N 行中奇数的数量
#include <bits/stdc++.h>
using namespace std;
//函数用于查找 N 的二进制表示中置位的位数
int numberofones(int N){
int a=0; //存储置位的位数
//循环迭代计数置位的位数
while(N>0){
a = a + (N&1); //如果 N 中有一个设置位，则通过加 1 来更新 a
N = N>>1; //右移 N 1 来检查其他设置位
}
return a; //返回 N 中 1 的个数
}
//函数用于获取第 N 行奇数的个数
int numberofodds(int N){
int x; //存储 N 中置位的位数
x=numberofones(N); //调用该函数将 N 中置位的位数存储在 x 中
int ans; //存储奇数的个数
ans=pow(2,x); //奇数的个数等于 N 中置位位数的 2 的乘积
return ans; //返回个数
}
int main()
{
int N; //用于获取输入
N=25;
//调用函数
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) 因为计算奇数个数不需要额外的空间。
结论
本文讨论了计算帕斯卡三角形第 N 行奇数个数的问题。我们利用数学中关于帕斯卡三角形第 N 行奇数个数的定理，在 C++ 中用一种高效的方法解决了这个问题。
希望您在阅读本文后能够理解这个问题以及相应的方法。
