奇偶自然數序列中範圍的和

---

問題陳述包括在先奇後偶的自然數序列中查詢範圍的和。

該序列包含從 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++ 演算法，該演算法可以在恆定時間內執行並佔用恆定的空間。

我希望您在閱讀本文後能夠理解這個問題以及解決它的方法。