奇偶自然数序列中范围的和

---

问题陈述包括在先奇后偶的自然数序列中查找范围的和。

该序列包含从 1 到 N 的所有奇数自然数，然后包含从 2 到 N 的所有偶数自然数，包括 N。序列的大小为 N。问题中会提供一个范围 [a,b]，我们需要求出该范围内的序列和。这里 a 和 b 都包含在范围内。

例如，给定N=7。

序列将首先包含从 1 到 N（即 7）的所有奇数自然数，然后包含从 1 到 7 的所有偶数。N 的值也包含在序列中。因此，序列将是 1, 3, 5, 7, 2, 4, 6。

1, 3, 5, 7, 2, 4, 6.

我们需要找到给定范围 a 和 b 内的序列和，其中 a 和 b 都包含在内。

在这个问题中，输入 a 和 b 表示必须计算序列和的范围，N 表示序列中的项目总数。我们的任务是打印范围 [a,b] 内的序列和。

示例

输入

a=3, b=6, N=8

输出

18

说明 − 输入中给定的 N 值为 8。序列将是 1, 3, 5, 7, 2, 4, 6, 8，因为它首先包含直到 8 的所有奇数自然数，然后是直到 8 的所有偶数自然数。范围 [3,6] 内的序列和将是

5+7+2+4=18，这就是我们需要的输出。

输入

a=1 , b=4, N=4

输出

10

说明 − 给定的 N 值为 4。序列包含直到 N 的所有奇数，然后是直到 N 的所有偶数。序列将是 1, 3, 2, 4。

范围 [1,4] 内的序列和是 1+3+2+4=10，这是输出。

让我们了解查找给定范围内的指定序列和的算法。

算法

创建序列，将其放入数组中，然后从数组中获取提供的范围的和，这可以作为问题的简单解决方案。这种方法的空间和运行时要求均为 O(N)。

我们可以通过遵循序列中的模式来考虑更好的方法。由于我们知道 N 的值，我们需要形成一个序列，其中它包含直到 N 的所有奇数自然数，然后是直到 N 的所有偶数自然数。

范围将给出为 [a,b]，其中 a 和 b 都包含在内。我们可以简单地找到从 1 到 b 的序列和，并从中减去从 1 到 a−1 的序列和。这样我们就可以得到从 a 到 b 的序列和。

由于序列中有 N 个数字，其中首先包含所有奇数，然后是直到 N 的所有偶数，因此序列中的奇数个数将是如果 N 是偶数则为 N/2，如果 N 是奇数则为 (N/2)+1。

我们可以使用 ceil() 函数找到 N 的序列中奇数的个数。

语法

double x;
ceil(x);

此函数返回大于或等于函数中传递的参数的最小整数。例如，x=2.4，该函数将返回 3，因为它是大于或等于 2.4 的最小整数。

使用 ceil() 函数，我们通过 ceil(N/2.0) 找到序列中奇数的个数，并通过N−ceil(N/2.0)找到序列中偶数的个数。

可以使用等差数列前 n 项和公式计算前 N 个奇数的和，因为它构成了一个首项为 1、公差为 2 的等差数列。

公式如下所示：

$\mathrm{S_{n}=\frac{n}{2}(2*a+(n−1)d),a=等差数列的首项，d=公差}$

$\mathrm{前 N 个奇数的和=\frac{N}{2}(2*1+(N−1)*2)}$

$\mathrm{=N^{2}}$

类似地，使用相同的公式，我们找到前 N 个偶数的和。这里首项将是 2，公差也将是 2。

$\mathrm{前 N 个偶数的和=\frac{N}{2}(2*2+(N−1)*2)}$

$\mathrm{=\frac{2*N}{2}(2+N−1)=N(N+1)}$

• 为了找到范围 [a,b] 中直到 b 的序列和，我们将首先使用公式检查序列中奇数的个数。如果奇数的个数大于 b 的值，我们将简单地使用公式找到直到 b 的奇数和，即 b^2。

• 对于 b 的值大于奇数个数的情况，我们将通过从 b 的值中减去奇数的个数来计算直到 b 位置的偶数个数，然后使用公式找到前 N 个偶数的和来找到直到 b 的所有偶数的和。

现在使用相同的过程，我们将找到直到 a−1 的序列和，并从中减去直到 b 的序列和，这将给我们提供给定范围（即 [a,b]）内的序列和，其中 a 和 b 也包含在内。

为了在恒定时间内解决问题，我们将在我们的方法中使用此算法。

方法

在我们的方法中实现上述算法以查找给定范围内的和的步骤

• 我们将创建一个函数来查找从第一个位置到第 p 个位置的序列和。

• 我们将检查序列中 N 个数字的奇数个数是否大于指定的第 p 个位置，如果是，我们将简单地使用公式返回和为 p^2 来查找奇数的和，因为直到 p 的奇数个数将是前 p 个奇数。

• 如果奇数的个数小于 p，那么我们将计算直到第 p 个位置的序列中偶数的个数，并将其用于公式中以查找偶数的和。

• 使用该函数，我们将计算直到 b 的序列和，并从中减去直到 a−1 的序列和，以获得给定范围（即 [a,b]）内的序列和。

示例

//C++ program to find the sum of the sequence within the given range [a,b]
#include <bits/stdc++.h>

using namespace std;

//function to find the sum of the sequence of N up to p position
//1,3,5,7,...N-1,2,4,6.....N
long long Sum(long long p, long long N)
{
    long long s=0; //to store the sum of the sequence till p
    
	// to find the number of odd numbers in the sequence till N
	long long odd_numbers = ceil(N / 2.0);

//if p is less than the number of odd numbers, find the sum of first p odd numbers
	if (p <= odd_numbers){
	s = p * p; //using the formula for sum of first p odd numbers
	return s;
    }

	//to store the number of even numbers in the sequence till p
	long long even_numbers = p - odd_numbers;

	//add the sum of odd numbers using the formula n^2 and even numbers using n(n+1)
	s = ((odd_numbers*odd_numbers)+ even_numbers*(even_numbers+1));
	
	return s; //return sum
}

int main()
{
	long long N,a,b;
	N=100;
	a=42;
	b=87;
	
	//to find the sum within the range [a,b] by subtracting the sum till b with sum till a-1
	long long ans = Sum(b,N) - Sum(a-1,N);
	
	//printing the output
	cout<<"The sum of the sequence within the range ["<<a<<","<<b<<"] : "<<ans<<endl;

	return 0;
}

输出

The sum of the sequence within the range [42,87] : 2225

时间复杂度− O(1)，因为查找给定范围内的序列和所花费的时间是恒定的。

空间复杂度− O(1)，因为我们在方法中没有使用任何额外的空间。

结论

本文讨论了查找给定范围内的序列和的问题，其中序列由直到 N 的奇数自然数和然后是直到 N 的偶数自然数组成。遵循序列中的模式，我们在本文中提出了一种高效的 C++ 算法，该算法可以在恒定时间内运行并占用恒定的空间。

我希望您在阅读本文后能够理解这个问题以及解决它的方法。