第44题-五角数

本文包含欧拉项目第44题解法

问题描述

第44题图

翻译为中文就是

五角数通过 P(n) = n(3n-1)/2 这个公式生成，前10个五角数是：1,5,12,22,35,51,70,92,117,145...

可以看出P(4) + P(7) = 22 + 70 = 92 = P(8)，但是它们的差 70 - 22 = 48不是五角数

找出五角数对P(j)和P(k)，使得它们之和是五角数，之差的绝对值D = |P(k) - P(j)| 最小，返回最小的D

解题思路

数论的题目，没有特别好的办法，只能按要求挨个遍历测试

rust语言实现

p44.rs

pub fn solution_of_p44() -> usize {
    let len = 3000;
    let pentagon_arr = gen_pentagon(len);
    let mut min_distance = 999999999;
    for i in 1..len - 1 {
        for j in i + 1..len {
            let add_value = pentagon_arr[j] + pentagon_arr[i];
            let sub_value = pentagon_arr[j] - pentagon_arr[i];
            if is_pentagon(sub_value) && is_pentagon(add_value) {
                if sub_value < min_distance {
                    min_distance = sub_value;
                }
            }
        }
    }
    return min_distance;
}

fn gen_pentagon(n: usize) -> Vec<usize> {
    let mut arr = vec![];
    for i in 1..=n {
        arr.push(pentagon(i));
    }
    arr
}

fn pentagon(i: usize) -> usize {
    let v = i * (3 * i - 1) / 2;
    v
}

fn is_pentagon(num: usize) -> bool {
    let exp_i = ((1.0 + ((1 + 24 * num) as f64).sqrt()) / 6.0) as usize;
    if pentagon(exp_i) == num {
        return true;
    }
    false
}

单测自行补上，理论上来说对每个方法都要有对应的单测，这方面rust的工具链做得很好。

代码很直观，先是生成一个五角数组，然后遍历这个五角数组，判断之和和之差是否是五角数，因为没有办法推导到底要遍历到何种地步，目前我是只测试了前3000个五角数，很幸运就得出了答案，程序运行时间也不会很长。

在这里有一个小技巧，生成一个数组再遍历，这样不会需要反复计算，从数组中取值是常数时间。这种方法有点类似于动态规划