通过欧拉计划学习Rust编程语言(2)

最近想学习Libra数字货币的MOVE语言,发现它是用Rust编写的,所以先补一下Rust的基础知识。学习了一段时间,发现Rust的学习曲线非常陡峭,不过仍有快速入门的办法。

学习任何一项技能最怕没有反馈,尤其是学英语、学编程的时候,一定要“用”,学习编程时有一个非常有用的网站,它就是“欧拉计划”,网址: https://projecteuler.net

这个网站提供了几百道由易到难的数学问题,你可以用任何办法去解决它,当然主要还得靠编程,编程语言不限,论坛里已经有Java、C#、Python、Lisp、Haskell等各种解法,当然如果你直接用google搜索答案就没任何乐趣了。

学习Rust最好先把基本的语法和特性看过一遍,然后就可以动手解题了,解题的过程就是学习、试错、再学习、掌握和巩固的过程,学习进度会大大加快。

前六题的解题过程:

第2题改进

上一篇文章中的第2题求400万之内所有偶数的斐波那契数字之和,当时提供的代码是这样的:

let mut fib = vec![1, 2];

let mut i = 2; // 已经有2个元素
let mut sum = 2;
loop {
    let c = fib[i - 1] + fib[i - 2];
    if c >= 4_000_000 {
        break;
    }
    fib.push(c);
    if c % 2 == 0 {
        sum += c;
    }
    i += 1;
}
println!("{}", sum);

这里可以利用rust的延迟评价特性,有起始值无终止值的无限序列可以用for语句搞定,原来的代码可以再精练一些,这种“2..”的语法在其它语言是无法想像的。

let mut fib = vec![1, 2];

let mut sum = 2;
for i in 2.. {
    let c = fib[i - 1] + fib[i - 2];
    if c >= 4_000_000 {
        break;
    }
    fib.push(c);
    if c % 2 == 0 {
        sum += c;
    }
}
println!("{}", sum);

如果再使用函数式编程,还可以更精练一点:

let mut fib = vec![1, 2];
for i in 2.. {
    let c = fib[i - 1] + fib[i - 2];
    if c >= 4_000_000 { break; }
    fib.push(c);
}
println!("{}", fib.iter().filter(|&x| x % 2 == 0).sum::<u32>());

第7题

问题描述:

求第10001个素数。

按通常的逐个试余法,效率极差,需要用著名的筛子求素数算法,请自行百度。从网上找来其它语言的源代码,稍做修改即可。

let max_number_to_check = 1_000_000;

let mut prime_mask = vec![true; max_number_to_check];
prime_mask[0] = false;
prime_mask[1] = false;

let mut total_primes_found = 0;

const FIRST_PRIME_NUMBER: usize = 2;
for p in FIRST_PRIME_NUMBER..max_number_to_check {
    if prime_mask[p] {
        // println!("{}", p);
        total_primes_found += 1;
        if total_primes_found == 10001 {
            println!("the 10001st prime number is : {}", p);
            break;
        }
        let mut i = 2 * p;
        while i < max_number_to_check {
            prime_mask[i] = false;
            i += p;
        }
    }
}

筛子算法需要提前分配内存空间,所以指定一个足够大的搜索范围 max_number_to_check,还需要一个数组 prime_mask 存放素数的标识位,另外还用 total_primes_found 对找到的素数进行计数。

这里有一个常量声明的语法点:

const FIRST_PRIME_NUMBER : usize = 2;

第8题

问题描述:

在1000位的大整数里找到相邻的13个数字,使其乘积最大。

首先系统内建的u32, u64或u128整数肯定无法保存1000位的整数,我们用字符串来表示这个大整数,为了让代码好看些,用数组表示,并用concat()函数合并。

let digits = vec![
    "73167176531330624919225119674426574742355349194934",
    "96983520312774506326239578318016984801869478851843",
    "85861560789112949495459501737958331952853208805511",
    "12540698747158523863050715693290963295227443043557",
    "66896648950445244523161731856403098711121722383113",
    "62229893423380308135336276614282806444486645238749",
    "30358907296290491560440772390713810515859307960866",
    "70172427121883998797908792274921901699720888093776",
    "65727333001053367881220235421809751254540594752243",
    "52584907711670556013604839586446706324415722155397",
    "53697817977846174064955149290862569321978468622482",
    "83972241375657056057490261407972968652414535100474",
    "82166370484403199890008895243450658541227588666881",
    "16427171479924442928230863465674813919123162824586",
    "17866458359124566529476545682848912883142607690042",
    "24219022671055626321111109370544217506941658960408",
    "07198403850962455444362981230987879927244284909188",
    "84580156166097919133875499200524063689912560717606",
    "05886116467109405077541002256983155200055935729725",
    "71636269561882670428252483600823257530420752963450",
].concat();

找到相邻的13个数字,需要用到字符串的切片(slice)功能,比如找到从i开始的13个字符形成了一个子串。这里面的“&”符号是容易出错的地方,digits变量有所有权,如果被借用后,就不能再被使用,熟悉C++的朋友,可以把“&”理解为引用,这样不破坏原来的所有权。

let x = &digits[i .. i + 13];

现在需要用到函数式编程的思路,将13个字符分离出来,并转换成数字,再相乘起来,用到chars(), map(), to_digit(), unwrap(), fold()等一连串的函数,请自行体会。

x.chars()
 .map(|c| c.to_digit(10).unwrap())
 .fold(1u64, |p, a| p * a as u64);

to_digit(10) 可用于将字符转换为数字,例如'9'转换为9,需要注意这里的转换有可能出现异常,而rust处理异常的方式很特别,要重点学习 Option<T> 的用法。

用unwrap()函数可以将Option<u64>类型转换成u64类型。

最后是这样:

const ADJACENT_NUMBERS: usize = 13;

let mut max = 0;
for i in 0..digits.len() - ADJACENT_NUMBERS {
    let x = &digits[i..i + ADJACENT_NUMBERS];
    let prod = x
        .chars()
        .map(|c| c.to_digit(10).unwrap())
        .fold(1u64, |p, a| p * a as u64);
    if prod > max {
        println!("index: {}   x: {}   prod: {}", i, x, prod);
        max = prod;
    }
}

第9题

问题描述:

找到和为1000的勾股数,并求积。

简单粗暴地遍历求解即可。

for a in 1..1000 {
    for b in a..1000 {
        let c = 1000 - a - b;
        if c > 0 && a*a + b*b == c*c {
            println!("{} = {} x {} x {}", a*b*c, a, b, c);
            return;
        }
    }
}

在Python中,用列表推导语法可以写成一行语句:

print([a*b*(1000-a-b) for a in range(1,1000 ) for b in range(a,1000) if 1000-a-b>0 and a*a+b*b==(1000-a-b)*(1000-a-b)])

第10题

问题描述:

求小于2百万的所有素数之和

在第7题的基础上稍做修改即可,为防止溢出,需要用u64保存累计值sum。

let max_number_to_check = 2_000_000;

let mut prime_mask = vec![true; max_number_to_check];
prime_mask[0] = false;
prime_mask[1] = false;

let mut sum: u64 = 0;

const FIRST_PRIME_NUMBER: usize = 2;
for p in FIRST_PRIME_NUMBER..max_number_to_check {
    if prime_mask[p] {
        sum += p as u64;
        let mut i = 2 * p;
        while i < max_number_to_check {
            prime_mask[i] = false;
            i += p;
        }
    }
}
println!("{}", sum);

第11题

问题描述:

在一个矩阵里,找到一条线上、相邻的、乘积最大的4个数,求积。

先把数值用二维数组表示。

let arr = [ 
    [08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08],
    [49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00],
    [81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65],
    [52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91],
    [22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80],
    [24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50],
    [32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70],
    [67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21],
    [24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],
    [21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95],
    [78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92],
    [16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57],
    [86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58],
    [19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40],
    [04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66],
    [88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69],
    [04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36],
    [20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16],
    [20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54],
    [01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48]
];

先不考虑代码的啰嗦和美观性,4个方向都比较一遍,找出最大的即可。

let mut max = 0;
for i in 0..20 {
    for j in 0..20 {
        if i+4<=20 {
            let p = arr[i][j] * arr[i+1][j] * arr[i+2][j] * arr[i+3][j];
            if p > max {
                max = p;
                println!("下 {} {} {}",i,j, max);
            }
        }
        if j<=20-4 {
            let p = arr[i][j] * arr[i][j+1] * arr[i][j+2] * arr[i][j+3];
            if p > max {
                max = p;
                println!("右 {} {} {}",i,j, max);
            }
        }
        if i<=20-4 && j<=20-4 {
            let p = arr[i][j] * arr[i+1][j+1] * arr[i+2][j+2] * arr[i+3][j+3];
            if p > max {
                max = p;
                println!("右下 {} {} {}",i,j, max);
            }
        }
        if i<=20-4 && j>=3 {
            let p = arr[i][j] * arr[i+1][j-1] * arr[i+2][j-2] * arr[i+3][j-3];
            if p > max {
                max = p;
                println!("左下 {} {} {}",i,j, max);
            }
        }
    }
}
println!("{}", max);

代码里存在大量的与max比较的重复代码,可以用k=0,1,2,3代表四个方向,多一个内层循环,让代码简洁一点。

for k in 0..4 {
    let mut p = 0;
    if k == 0 && i+4<=20 {
        p = arr[i][j] * arr[i+1][j] * arr[i+2][j] * arr[i+3][j];
    }
    if k == 1 && j<=20-4 {
        p = arr[i][j] * arr[i][j+1] * arr[i][j+2] * arr[i][j+3];
    }
    if k == 2 && i<=20-4 && j<=20-4 {
        p = arr[i][j] * arr[i+1][j+1] * arr[i+2][j+2] * arr[i+3][j+3];
    }
    if k == 3 && i<=20-4 && j>=3 {
        p = arr[i][j] * arr[i+1][j-1] * arr[i+2][j-2] * arr[i+3][j-3];
    }

    if p > max {
        max = p;
        println!("{} {} {}",i,j, max);
    }
}

问题12

问题描述:

求有超过500个因子的三角数。

三角数就是从1一直累加之后的数,比如第7个三角数,就是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。

而28一共有6个因子:1,2,4,7,14,28

求所有因子,可以试着取余数就行。

fn factors(num :u32) -> Vec<u32> {
    (1..=num).filter(|x| num % x == 0).collect::<Vec<u32>>()
}

然后暴力尝试即可,但效率非常差,我等了10分钟也没算出来。

fn main() {
    for i in 1.. {
        let num = (1..=i).sum::<u32>();
        let f = factors(num);
        if f.len() > 500 {
            println!("i:{} num:{} len:{} {:?}", i, num, f.len(), f );
            println!("{}", num );
            break;
        }
    }
}

可以稍做优化,只尝试一半的因子就行,速度大幅提高,几秒钟可以计算完成。

fn main() {
    for i in 2.. { // 12375
        let num = (1..=i).sum::<u32>();
        let f = half_factors(num);
        if f.len() * 2 > 500 {
            println!("i:{} num:{} len:{} half of factors:{:?}", i, num, 2 * f.len(), f );
            println!("{}", num );
            break;
        }
    }
}

fn half_factors(num :u32) -> Vec<u32> {
    let s = (num as f32).sqrt() as u32;
    (1..=s).filter(|x| num % x == 0).collect::<Vec<u32>>()
}

实际上还可以利用因子的数学性质进一步优化,提高上千倍不止,这里不展开讨论了。


在projecteuler中注册一个账号,可以添加好友,一些讨论学习,我的Key是:

1539870_KBNiIXymh4SnmDEDZmUTg7tu1MTBVlLj

原文发布于微信公众号 - 申龙斌的程序人生(slbGTD)

原文发表时间:2019-08-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券