C++ 中的尼科马库斯定理（奇数正整数的第 k 组之和）

在本文中，我们将讨论 C++ 中的 Nicomachus 定理 (k 组奇正整数之和) 及其不同方法。在讨论其方法之前，我们必须先了解 C++ 中关于 Nicomachus 定理的一些知识。

通过示例解释 Nicomachus 定理

k 的平方等于从 1 到 k 的奇正整数之和。用数学符号表示，该定理可以写成 1+3+5+⋯+(2k−1)=k²。

例如

1、3、5，即前 3 个奇数之和为 9 = 3²。

前 5 个奇数之和 (1+3+5+7+9 = 25) 也等于 25，即 5²。

这个优美的结果表明，简单的算术运算可以揭示数字的内在对称性，并能产生更深刻的数学真理。

方法一：数学归纳法

数学归纳法是一种非常强大的证明关于自然数陈述的方法。它包括两个关键步骤：归纳步骤和基本情况。

• 基本情况：首先，我们证明该陈述对于出现的最小 k (通常是 k = 1) 为真。
• 归纳步骤：在此步骤中，我们证明，如果该陈述对于某个任意的 k=n (归纳假设) 为真，那么它对于 k=n+1 也一定为真。

在此之后，表明它对于所有自然数 k 都为真，这通过从基本情况完成每个后续值来完成。

当将数学归纳法翻译成编程时，我们会运行这些步骤来验证一个定理。例如，考虑 Niomachus 定理，即前 k 个奇数之和等于 k²，我们可以直接将其转化为代码。之后，我们检查基本情况 (k=1)，即第一个奇数 1 的和是 1²。然后我们证明 k=n+1 的和也等于 (n+1)²，并假设该定理对于 k=n 成立。

它也可以应用于编程，使用递归、循环等。与逐个求和并与 k² 进行比较不同，我们对前 k 个奇数求和，将其设为 k²，然后与下一个值进行比较，并重复此过程。该方法与数学归纳法类似，因此该定理对于所有 k 值都成立。

示例

让我们举一个例子来说明使用数学归纳法在 C++ 中实现的 Nicomachus 定理。

输出

Enter the value of k up to which to verify Nicomachus' theorem: 3
Base Case Check: Sum = 1, 1^2 = 1
Verifying for k = 1...
Inductive Hypothesis Check: Sum of first 1 odd numbers = 1, k^2 = 1
Inductive Step Check: Sum of first 2 odd numbers = 4, (k+1)^2 = 4
Verifying for k = 2...
Inductive Hypothesis Check: Sum of first 2 odd numbers = 4, k^2 = 4
Inductive Step Check: Sum of first 3 odd numbers = 9, (k+1)^2 = 9
Verifying for k = 3...
Inductive Hypothesis Check: Sum of first 3 odd numbers = 9, k^2 = 9
Inductive Step Check: Sum of first 4 odd numbers = 16, (k+1)^2 = 16
Induction completed successfully. Nicomachus' theorem holds for all k from 1 to 3.
Sum of Odd Numbers up to k:
k Sum of Odd Numbers k^2
-----------------------------------------------
1 1 1
2 4 4
3 9 9
Detailed Verification for k = 1:
Sum of the first 1 odd numbers: 1
k^2 (square of 1): 1
The theorem holds for k = 1.
Sum of the first 2 odd numbers: 4
(k+1)^2 (square of 2): 4
The theorem holds for k = 2.
Detailed Verification for k = 2:
Sum of the first 2 odd numbers: 4
k^2 (square of 2): 4
The theorem holds for k = 2.
Sum of the first 3 odd numbers: 9
(k+1)^2 (square of 3): 9
The theorem holds for k = 3.
Detailed Verification for k = 3:
Sum of the first 3 odd numbers: 9
k^2 (square of 3): 9
The theorem holds for k = 3.
Sum of the first 4 odd numbers: 16
(k+1)^2 (square of 4): 16
The theorem holds for k = 4.
Optimized verification for large k values:
Sum of first 1 odd numbers (Optimized): 1, k^2 = 1
Sum of first 2 odd numbers (Optimized): 4, k^2 = 4
Sum of first 3 odd numbers (Optimized): 9, k^2 = 9   

说明

• sumOddNumbers(int k)
  此函数计算前 k 个奇数或数字之和。第 n 个奇数的公式是 2i − 1，其中 i 是序列的索引，i 从 1 开始。在第一次迭代中，我们遍历前 'k' 个奇数，将它们加在一起并返回总和。
• verifyBaseCase()
  此函数检查 k=1 的数学归纳法基本情况。它将第一个奇数 (即 1) 的和与 1² (即 1) 进行比较。如果它们匹配，则基本情况有效，定理对于 k=1 成立。
• verifyInductiveStep(int k)
  在此函数中，我们首先检查前 k 个奇数之和是否等于 k²。之后，我们通过确保前 k+1 个奇数之和等于 (k+1)² 来验证归纳步骤。这个过程确保如果定理对于 k 成立，那么它也对于 k+1 成立。
• inductionVerification(int maxK)
  此函数对从 1 到 maxK 的所有值执行归纳验证过程。它首先验证基本情况，然后检查每个 k 到 maxK 的归纳步骤。如果定理在任何一点失败，它将停止并输出错误。
• printSumTable(int maxK)
  此函数打印一个格式化的表格，显示高达 k 的奇数之和以及每个 k 从 1 到 maxK 的相应 k² 值。使用 <iomanip> 的 setw() 函数，表格以美观的格式打印，并调整列项的宽度。
• detailedVerification(int k)
  它为特定的 k 提供单个定理，并给出奇数之和与 k² 的详细输出。它还包括一个 k+1 的断言，以逐步证明该定理。
• optimizedSumOddNumbers(int k)
  与前面的函数类似，此函数直接根据公式 𝑘² 计算前 k 个奇数之和。

复杂度分析

时间复杂度

• sumOddNumbers(int k)
  它遍历前 k 个奇数。循环运行 k 次，每次迭代执行一个常数时间操作，即 (添加一个奇数)。因此，时间复杂度为 O(k)。
• verifyBaseCase()
  此函数只对 k=1 进行基本情况检查，将和 (1) 与 1² (即 1) 进行比较。这些都是常数时间操作，因此时间复杂度为 O(1)。
• verifyInductiveStep(int k)
  第一个函数计算前 k 个奇数之和，并将其与 k² 进行比较 (由于调用了 sumOddNumbers(k)，因此需要 O(k))。其次，它对 k+1 执行相同的步骤，并且每次验证的复杂度仍然是 O(k)。

空间复杂度

每个 函数 都被存储 变量 的存储所支配，因此空间复杂度也受到支配。由于我们的所有函数只使用常数空间 (例如，和与计数器)，因此除了输入和输出数据之外，空间复杂度为 O(1)。

方法二：基于公式的方法

Nicomachus 定理指出，前 k 个奇数之和等于 k²。前 k 个奇数之和可以直接表示为：S(k)=1+3+5+⋯+(2k−1)=k²。

与其逐个求和每个奇数，不如直接使用公式计算总和。为此，我们只需将 k² 的结果与使用前 k 个奇数之和的直接数学公式计算出的总和进行比较。

示例

让我们举一个例子来说明使用基于公式的方法在 C++ 中实现的 Nicomachus 定理。

输出

Enter the value of k (positive integer) up to which to verify Nicomachus' theorem: 3
Verifying Nicomachus' Theorem using the mathematical formula:
For k = 1:
Sum of first 1 odd number (calculated): 1
k^2 (calculated): 1
The theorem holds for k = 1.
For k = 2:
Sum of first 2 odd numbers (calculated): 4
k^2 (calculated): 4
The theorem holds for k = 2.
For k = 3:
Sum of first 3 odd numbers (calculated): 9
k^2 (calculated): 9
The theorem holds for k = 3.
Verifying Nicomachus' Theorem using the iterative approach:
For k = 1:
Sum of first 1 odd numbers (iterative): 1
k^2 (calculated): 1
The theorem holds for k = 1.
For k = 2:
Sum of first 2 odd numbers (iterative): 4
k^2 (calculated): 4
The theorem holds for k = 2.
For k = 3:
Sum of first 3 odd numbers (iterative): 9
k^2 (calculated): 9
The theorem holds for k = 3.
Sum of first k odd numbers for k = 1 to 3:
         k    Sum of first k odd numbers                k^2
         1                             1                   1
         2                             4                   4
         3                             9                   9
   

说明

• sumOddNumbersIterative(int k) 函数通过逐个迭代前 k 个奇数来对它们求和。这将帮助我们了解如何获得结果。
• verifyTheoremFormula(int maxK) 函数对从 1 到 maxK 的所有值 k 运行定理公式并进行验证。之后，我们证明我们计算出的总和公式对于每个找到的 k (我们称之为 verifyTheoremIterative) 等于 k²，因为该定理对于任何 k 都成立。
• printSumTable(int maxK) 函数为表格结果添加了视觉表示。每对都显示计算出的高达 k 的 k 个奇数之和，以及旁边的 k²。
• 在 getMaxK() 函数中，我们提示用户输入一个正整数。如果输入无效，我们会反复询问直到提供有效输入。一旦输入了有效数字，我们将打印结果，妥善处理用户输入，并调用必要的函数来测试定理并显示结果。

复杂度分析

时间复杂度

• 函数 sumOddNumbers 和 sumOddNumbersIterative 决定了代码的复杂度。它使用直接公式 k² 计算总和，这是一个常数时间操作，因此现在是 O(1)。另一方面是 sumOddNumbersIterative(int k)，它循环遍历前 k 个奇数并为每个奇数执行加法，因此其时间复杂度为 O(k)。使用直接公式 k²，这是一个常数时间操作，其时间复杂度为 O(1)。
• 另一方面，sumOddNumbersIterative(int k) 函数涉及遍历前 k 个奇数并为每个奇数执行加法运算，从而导致 O(k) 的时间复杂度。
• 对于每个 k，sumOddNumbers(k) 函数的复杂度为 O(1)。verifyTheoremFormula(int maxK) 函数从 1 开始迭代。该函数的总复杂度为 O(maxK)。
• 类似地，sumOddNumbersIterative 为每个 k 调用自身，这使得时间复杂度为 O(k⋅maxK)，因为后者对每个都运行 O(k)。
• printSumTable(int maxK) 函数将从 1 到 maxK 进行迭代，为每个 k 执行一个常数时间操作。因此，该算法的复杂度为 O(maxK)。

空间复杂度

• 该程序的空间复杂度为 O(1)，因为它使用恒定的内存来执行诸如整数之类的操作，不使用内存密集型操作，也不使用任何额外的 数据结构。