Rust 练习册：平方差与数学公式应用

2025-11-29 10:31:46 分类：rust 热度：984 评论： 0

Rust 练习册：平方差与数学公式应用

在数学中，有许多优美的公式可以帮助我们快速计算复杂的问题。平方差问题是一个经典的数学问题，它涉及计算前n个自然数的和的平方与前n个自然数的平方和之间的差值。在 Exercism 的 “difference-of-squares” 练习中，我们将实现这个问题的解决方案，这不仅能帮助我们掌握数学公式的程序化应用，还能深入学习 Rust 中的数值计算和算法优化技巧。

什么是平方差问题？

平方差问题要求我们计算以下三个值：

  1. 前n个自然数的和的平方：(1 + 2 + … + n)²
  2. 前n个自然数的平方和：1² + 2² + … + n²
  3. 两者的差值：(1 + 2 + … + n)² - (1² + 2² + … + n²)

例如，对于 n=5：

  • 前5个自然数的和的平方：(1 + 2 + 3 + 4 + 5)² = 15² = 225
  • 前5个自然数的平方和：1² + 2² + 3² + 4² + 5² = 1 + 4 + 9 + 16 + 25 = 55
  • 差值：225 - 55 = 170

让我们先看看练习提供的函数签名：

pub fn square_of_sum(n: u32) -> u32 {
    (n*(1 + n)/2).pow(2)
}

// https://en.wikipedia.org/wiki/Square_pyramidal_number
pub fn sum_of_squares(n: u32) -> u32 {
    n*(n+1)*(2*n+1)/6
}

pub fn difference(n: u32) -> u32 {
    square_of_sum(n) - sum_of_squares(n)
}

这些实现已经使用了数学公式来优化计算，避免了循环。

数学公式解析

1. 前n个自然数的和

前n个自然数的和有一个著名的公式，由数学家高斯发现：

1 + 2 + 3 + ... + n = n(n+1)/2

这个公式的推导可以通过配对来理解：

  • 首尾配对：(1+n), (2+(n-1)), (3+(n-2)), …
  • 每一对的和都是 n+1
  • 总共有 n/2 对（如果n是偶数）或 (n-1)/2 对加上中间的数（如果n是奇数）

2. 前n个自然数的平方和

前n个自然数的平方和也有一个公式：

1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6

这个公式可以通过数学归纳法证明，或者通过生成函数的方法推导。

3. 平方差公式

平方差可以直接通过上述两个公式计算：

(1 + 2 + ... + n)² - (1² + 2² + ... + n²)

算法实现

1. 基础实现（使用循环）

pub fn square_of_sum(n: u32) -> u32 {
    let sum: u32 = (1..=n).sum();
    sum * sum
}

pub fn sum_of_squares(n: u32) -> u32 {
    (1..=n).map(|x| x * x).sum()
}

pub fn difference(n: u32) -> u32 {
    square_of_sum(n) - sum_of_squares(n)
}

2. 优化实现（使用数学公式）

pub fn square_of_sum(n: u32) -> u32 {
    let sum = n * (n + 1) / 2;
    sum * sum
}

pub fn sum_of_squares(n: u32) -> u32 {
    n * (n + 1) * (2 * n + 1) / 6
}

pub fn difference(n: u32) -> u32 {
    square_of_sum(n) - sum_of_squares(n)
}

3. 更高效的实现

pub fn square_of_sum(n: u32) -> u32 {
    // 使用 u64 防止中间计算溢出
    let n = n as u64;
    let sum = n * (n + 1) / 2;
    (sum * sum) as u32
}

pub fn sum_of_squares(n: u32) -> u32 {
    // 使用 u64 防止中间计算溢出
    let n = n as u64;
    (n * (n + 1) * (2 * n + 1) / 6) as u32
}

pub fn difference(n: u32) -> u32 {
    square_of_sum(n) - sum_of_squares(n)
}

测试用例分析

通过查看测试用例，我们可以更好地理解需求：

#[test]
fn test_square_of_sum_1() {
    assert_eq!(1, squares::square_of_sum(1));
}

最简单的情况，1的平方是1。

#[test]
fn test_square_of_sum_5() {
    assert_eq!(225, squares::square_of_sum(5));
}

前5个自然数的和是15，15的平方是225。

#[test]
fn test_sum_of_squares_5() {
    assert_eq!(55, squares::sum_of_squares(5));
}

前5个自然数的平方和是1+4+9+16+25=55。

#[test]
fn test_difference_5() {
    assert_eq!(170, squares::difference(5));
}

差值是225-55=170。

#[test]
fn test_square_of_sum_100() {
    assert_eq!(25_502_500, squares::square_of_sum(100));
}

对于较大的数，公式的优势更加明显。

完整实现

考虑所有边界情况的完整实现：

pub fn square_of_sum(n: u32) -> u32 {
    // 处理边界情况
    if n == 0 {
        return 0;
    }
    
    // 使用 u64 防止溢出
    let n = n as u64;
    let sum = n * (n + 1) / 2;
    (sum * sum) as u32
}

pub fn sum_of_squares(n: u32) -> u32 {
    // 处理边界情况
    if n == 0 {
        return 0;
    }
    
    // 使用 u64 防止溢出
    let n = n as u64;
    (n * (n + 1) * (2 * n + 1) / 6) as u32
}

pub fn difference(n: u32) -> u32 {
    // 处理边界情况
    if n == 0 {
        return 0;
    }
    
    square_of_sum(n) - sum_of_squares(n)
}

错误处理和边界情况

考虑更多边界情况的实现：

#[derive(Debug, PartialEq)]
pub enum MathError {
    Overflow,
}

pub fn square_of_sum(n: u32) -> Result<u32, MathError> {
    if n == 0 {
        return Ok(0);
    }
    
    // 检查是否会溢出
    let n = n as u64;
    let sum = n * (n + 1) / 2;
    let square = sum * sum;
    
    if square > u32::MAX as u64 {
        Err(MathError::Overflow)
    } else {
        Ok(square as u32)
    }
}

pub fn sum_of_squares(n: u32) -> Result<u32, MathError> {
    if n == 0 {
        return Ok(0);
    }
    
    // 检查是否会溢出
    let n = n as u64;
    let result = n * (n + 1) * (2 * n + 1) / 6;
    
    if result > u32::MAX as u64 {
        Err(MathError::Overflow)
    } else {
        Ok(result as u32)
    }
}

pub fn difference(n: u32) -> Result<u32, MathError> {
    if n == 0 {
        return Ok(0);
    }
    
    let square_sum = square_of_sum(n)?;
    let sum_squares = sum_of_squares(n)?;
    
    if square_sum < sum_squares {
        Err(MathError::Overflow)
    } else {
        Ok(square_sum - sum_squares)
    }
}

性能优化版本

考虑性能的优化实现：

pub fn square_of_sum(n: u32) -> u32 {
    if n == 0 {
        return 0;
    }
    
    let n = n as u64;
    let sum = (n * (n + 1)) >> 1; // 使用位移代替除法
    (sum * sum) as u32
}

pub fn sum_of_squares(n: u32) -> u32 {
    if n == 0 {
        return 0;
    }
    
    let n = n as u64;
    // 重新排列计算顺序以减少溢出风险
    let term1 = n * (n + 1);
    let term2 = (2 * n + 1);
    
    if n % 2 == 0 {
        ((term1 >> 1) * term2 / 3) as u32
    } else if (2 * n + 1) % 3 == 0 {
        (term1 * (term2 / 3) >> 1) as u32
    } else {
        (term1 * term2 / 6) as u32
    }
}

pub fn difference(n: u32) -> u32 {
    if n == 0 {
        return 0;
    }
    
    square_of_sum(n) - sum_of_squares(n)
}

扩展功能

基于基础实现，我们可以添加更多功能：

pub struct SquareCalculator;

impl SquareCalculator {
    pub fn new() -> Self {
        SquareCalculator
    }
    
    pub fn square_of_sum(&self, n: u32) -> u32 {
        if n == 0 {
            return 0;
        }
        
        let n = n as u64;
        let sum = n * (n + 1) / 2;
        (sum * sum) as u32
    }
    
    pub fn sum_of_squares(&self, n: u32) -> u32 {
        if n == 0 {
            return 0;
        }
        
        let n = n as u64;
        (n * (n + 1) * (2 * n + 1) / 6) as u32
    }
    
    pub fn difference(&self, n: u32) -> u32 {
        if n == 0 {
            return 0;
        }
        
        self.square_of_sum(n) - self.sum_of_squares(n)
    }
    
    // 计算立方和公式
    pub fn sum_of_cubes(&self, n: u32) -> u32 {
        if n == 0 {
            return 0;
        }
        
        let n = n as u64;
        let sum = n * (n + 1) / 2;
        (sum * sum) as u32
    }
    
    // 验证平方差公式
    pub fn verify_formula(&self, n: u32) -> bool {
        let direct_square_of_sum: u32 = (1..=n).sum::<u32>().pow(2);
        let formula_square_of_sum = self.square_of_sum(n);
        
        let direct_sum_of_squares: u32 = (1..=n).map(|x| x * x).sum();
        let formula_sum_of_squares = self.sum_of_squares(n);
        
        direct_square_of_sum == formula_square_of_sum && 
        direct_sum_of_squares == formula_sum_of_squares
    }
}

实际应用场景

平方差问题在实际开发中有以下应用：

  1. 算法优化：展示数学公式如何优化算法性能
  2. 数值分析：在数值计算中应用数学公式
  3. 教育工具：作为数学和编程教学的经典示例
  4. 性能基准测试：比较公式计算和循环计算的性能差异
  5. 统计计算：在方差计算等统计方法中应用相关公式

算法复杂度分析

  1. 时间复杂度：

    • 循环实现：O(n)
    • 公式实现：O(1)

  2. 空间复杂度：O(1)

与其他实现方式的比较

// 使用迭代器的实现
pub fn square_of_sum_iterator(n: u32) -> u32 {
    let sum: u32 = (1..=n).sum();
    sum * sum
}

pub fn sum_of_squares_iterator(n: u32) -> u32 {
    (1..=n).map(|x| x * x).sum()
}

// 使用递归的实现
pub fn square_of_sum_recursive(n: u32) -> u32 {
    fn sum_recursive(n: u32) -> u32 {
        if n == 0 {
            0
        } else {
            n + sum_recursive(n - 1)
        }
    }
    
    let sum = sum_recursive(n);
    sum * sum
}

pub fn sum_of_squares_recursive(n: u32) -> u32 {
    fn sum_squares_recursive(n: u32) -> u32 {
        if n == 0 {
            0
        } else {
            n * n + sum_squares_recursive(n - 1)
        }
    }
    
    sum_squares_recursive(n)
}

// 使用记忆化的实现
use std::collections::HashMap;

pub struct MemoizedCalculator {
    square_of_sum_memo: HashMap<u32, u32>,
    sum_of_squares_memo: HashMap<u32, u32>,
}

impl MemoizedCalculator {
    pub fn new() -> Self {
        MemoizedCalculator {
            square_of_sum_memo: HashMap::new(),
            sum_of_squares_memo: HashMap::new(),
        }
    }
    
    pub fn square_of_sum(&mut self, n: u32) -> u32 {
        if let Some(&result) = self.square_of_sum_memo.get(&n) {
            return result;
        }
        
        let result = if n == 0 {
            0
        } else {
            let n = n as u64;
            let sum = n * (n + 1) / 2;
            (sum * sum) as u32
        };
        
        self.square_of_sum_memo.insert(n, result);
        result
    }
    
    pub fn sum_of_squares(&mut self, n: u32) -> u32 {
        if let Some(&result) = self.sum_of_squares_memo.get(&n) {
            return result;
        }
        
        let result = if n == 0 {
            0
        } else {
            let n = n as u64;
            (n * (n + 1) * (2 * n + 1) / 6) as u32
        };
        
        self.sum_of_squares_memo.insert(n, result);
        result
    }
}

总结

通过 difference-of-squares 练习，我们学到了：

  1. 数学公式应用：掌握了如何将数学公式转化为程序实现
  2. 算法优化：理解了公式计算相对于循环计算的优势
  3. 数值处理：学会了处理大数计算时的溢出问题
  4. 性能优化：了解了不同实现方式的性能特点
  5. 边界处理：学会了处理各种边界情况
  6. 错误处理：理解了如何处理计算溢出等错误情况

这些技能在实际开发中非常有用，特别是在进行数值计算、算法优化和数学问题求解时。平方差问题虽然是一个简单的数学问题，但它涉及到了算法优化、数值处理和错误处理等许多核心概念，是学习 Rust 数值计算的良好起点。

通过这个练习，我们也看到了 Rust 在数值处理和性能优化方面的强大能力，以及如何用安全且高效的方式实现数学算法。这种结合了安全性和性能的语言特性正是 Rust 的魅力所在。

转载请说明出处内容投诉
CSS教程网 » Rust 练习册：平方差与数学公式应用
qqy

qqy

分享到：

发表评论

欢迎 访客 发表评论

一个令你着迷的主题！

查看演示 官网购买