Scala 公开课笔记

Coursera上的瑞士洛桑理工大学Scala函数式编程原理(Functional Programming Principles in Scala)课程笔记。

课程链接：https://class.coursera.org/progfun-005

Getting Started

Scala开发环境配置相关的几点经验：

1. 解决Scala编译太慢的问题：使用sbt构建，保持一个运行sbt的console。也就是说，让一个JVM常驻内存，可以显著提升编译效率。

2. sbt解决依赖的过程中出现sha1 error: 在build.sbt中增加如下内容：

   checksums in update := Nil
   

   或者在sbtconfig.txt中增加如下内容，禁用全局sha1 check:

   -Dsbt.ivy.checksums="" # 默认值为"md5, sha1"
   

3. 自定义sbt的缓存位置: 在sbtconfig.txt中增加如下内容：

   -Dsbt.ivy.home=d:/Java/sbt/
   -Dsbt.boot.directory=d:/Java/sbt/boot/
   

N皇后问题

N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。N皇后问题互不相同的解的个数可以用OEIS A000170序列来表示，如果将旋转和对称的解归为一种，那么独立解的个数符合序列OEIS A002562。

普通递归求解

N皇后问题的普通解法是通过枚举N的全排列，并判断是否符合条件来得到解的方案数。可以通过一些剪枝技巧来优化运算，提升效率。

Rust-Book Learn Rust

Guessing Game

Our program will generate a random integer between one and a hundred. It will then prompt us to enter a guess. Upon entering our guess, it will tell us if we’re too low or too high. Once we guess correctly, it will congratulate us.

Set Up

创建项目：

cargo new guessing_game --bin

--bin表示创建二进制可执行程序(binary)而不是程序库(library)。

项目目录结构(cargo build之后)：

Rust-Book Getting Started

从零开始学习Rust。

1. Rust的安装

略。

2. Rust版Hello World

fn main() {
    println!("hello world");
}

main函数是程序入口。println!中的!表示这是一个宏。

This is calling a Rust macro, which is how metaprogramming is done in Rust.

Rust-Book Effective Rust

The Stack and the Heap

栈内存访问比堆内存访问快，局部变量存放在栈上。

Box: A pointer type for heap allocation.可以使用Box<T> type来申请对内存空间。例如：

fn main() {
    let x = Box::new(5);
    ley y = 42;
}

Box分配的堆内存资源可以使用Drop来释放。Rust没有垃圾回收(GC)机制。

Rust使用jemalloc来进行内存分配，

Polya定理及应用

概念及定理

首先是群的概念：

设$G$是一个集合，$$是$G$上的二元运算，如果$(G,)$满足下面的条件：

1. 封闭性：对于任何$a,b \in G$有$a*b \in G$;
2. 结合律：对任何$a,b,c\in G$有$(a*b)c=a(b*c)$;
3. 单位元：存在$e\in G$,使得对所有的$a\in G$,都有$a*e=e*a=a$;
4. 逆元：对于每个元素$a\in G$,存在$x\in G$,使得$a*x=x*a=e$,这个时候记$x$为$a^{{-1}$，称为$a$的逆元，那么则称$(G,*)$为一个群。}

几种求解PI的概率算法的探究和对比

$\pi$是一个重要的随机数，在数学研究中占有重要地位。求解PI的数值值也一直是数学研究的经典问题之一。本文将主要探讨几种求解PI的概率算法的原理和实现，并对比其效率和准确度。

一、Mathematica中的$\pi$

我们发现，在Mathematica中可以使用$\pi$来做符号运算，很多运算都涉及到非常高深的数学知识，使用N[Pi, n]函数也能够求得$\pi$的前n位数值解。那么为什么Mathematica能够以如此高的精度求解$\pi$的值呢？

通过查阅Mathematica的文档，得知，Mathematica求解$\pi$使用的是Chudnovsky公式，因其具有很好的收敛速度而在数值计算中被广泛采用。Chudnovsky 算法的表述如下：

$$ \frac{1}{\pi} = 12\sum_{k=0}^{\infty} \frac{(-1)^k(6k)! (163\cdot 3344418k + 13591409)}{(3k)!(k!)^{3(6403203){k+1/2}}} $$

一类棋盘覆盖问题的动态规划求解

棋盘覆盖问题是算法研究和实践中一个很有意思的问题。在解决这一类问题时，往往需要用到动态规划、状态压缩、二进制拆分、快速幂等多种算法技巧。

1x2 - 2xn

首先考虑一个较为简单的问题，使用1x2的骨牌覆盖2xn的棋盘，问：有多少种方案。

自产生程序(Quine)

自产生程式（Quine），它以哲学家奎恩命名，指的是输出结果为程式自身源码的程式。

Quine 的想法最初出现在 Bratley, Paul and Jean Millo. "Computer Recreations; Self-Reproducing Automata", Software — Practice & Experience, Vol. 2 (1972). pp. 397-400 中。Bratley 在看到已知的第一个 这样的程序以后对 Quine 产生了兴趣。这个程序于二十世纪六十年代由爱丁堡 大学的 Hamish Dewar 以 Atlas Autocode 语言写成。

作为真正的 Quine ，有一些约定：程序不能接受输入或者是打开文件，因为那 样就可以直接输入源代码或者是把源代码文件直接打开再重新打印出来，就没有 什么意思了；同时，一个完全空白的程序(产生完全空白的输出，即没有输出)也 并不能称作 Quine。

Java 8 Lambda 代码片段

Java 8引入了lambda表达式，可以用来完成很多函数式编程的目的。本文的内容主要用来积累一些有用的Lambda表达式的应用代码片段。

可以使用下面语法实现Lambda表达式:

(params) -> expression
(params) -> statement
(params) -> { statements }

如果方法并不改变任何方法参数，比如只是输出，那么可以简写如下：

() -> System.out.println("Hello Lambda Expressions");

如果方法接受两个方法参数，如下：

(int even, int odd) -> even + odd