-
几种求解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(640320^3)^{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 -
斐波那契数列
2014年蓝桥杯本科C/C++组预赛第9题是很好的一道关于斐波那契(Fibonacci)数列的题目。本文将从这一题目出发，探讨一些与斐波那契数列相关的性质。
题目
题目链接：斐波那契 http://lx.lanqiao.org/problem.page?gpid=T121
题目内容：
问题描述
斐波那契数列大家都非常熟悉。它的定义是：
\[f(x) = {\begin{cases} 1 & x = 1, 2 \\ f(x-1) + f(x-2) & x > 2 \end{cases}}\]对于给定的整数 $n$ 和 $m$，我们希望求出：\(f(1) + f(2) + \dots + f(n)\) 的值。但这个值可能非常大，所以我们把它对 $f(m)$ 取模。
公式如下:
\[(\sum_{i=1}^n{f(i)}) \textit{ mod } f(m)\]但这个数字依然很大，所以需要再对 $p$ 取模。
- 输入格式 输入为一行用空格分开的整数 n m p ($0 < n, m, p < 10^{18}$)
- 输出格式 输出为1个整数，表示答案
- 样例输入
2 3 5 - 样例输出
0 - 样例输入
15 11 29 - 样例输出
25
-
子模性(Submodular)
$A$ 是 $B$ 的子集，则对于函数 $f()$，如果：
\[f(A+e)-f(A)>=f(B+e)-f(B)\]成立，则说 $f()$ 函数是子模的。
子模性描述的是一种增益递减的现象。例如：
\[\begin{aligned} u &= {1,2,3,4,5,6,7,8} \\ A &= {1,2,3} \\ B &= {1,2,3,5,6} \end{aligned}\]$f(A)=|A|$ 表示集合 $A$ 的个数，那么：
\[f(A+e)-f(A)>=f(B+e)-f(B)\]例如 $e={3,4,5}$。
-
组合博弈与SG函数
在算法研究领域博弈论占有很重要的地位，本文将围绕 $SG$ 函数和NIM博弈分析积累典型的博弈论问题模型，并给出这一类问题的一般建模方法。
Bash Game基于同余理论，Nim Game基于异或理论，Wythoff Game基于黄金分割理论。这三种博弈问题都可以通过 $SG$ 函数的通用理论来解决。
-
一致性哈希算法
在一个分布式服务系统中，当有一台Server宕机时，需要将其数据、服务等迁移到别的主机上。不难想到，可以对整个集群的任务重新做一次Hash，使得数据重复分布，但这样往往会造成大规模的数据迁移，并且在数据迁移完成之前所有的服务都不可用。一致性Hash算法很好的解决了这一问题。
-
Python实现docx2txt
对于一些Linux平台，特别是没有安装桌面的Linux系统，查看MS Office的文档是一件非常痛苦的事情，如果能够将.dox格式的文件转化成一个文本文件，将会解决很多问题。我们知道，.docx文件实质上是一个.zip压缩包，里面包含了各种各样的XML结构化文本文件、资源文件、XML样式表，等等。文档中的所有内容都集中在压缩包中的
word/document.xml文件中，然而这是一个复杂的XML文件，并不适合直接阅读。因此，需要将其中的文本提取出来。我们知道，Python作为一门强大的脚本语言，很擅长处理与字符串相关的问题。因此使用Python来实现一个docx2txt的小工具。
-
实现2+2=5
Java、Python都采取了常量实例池优化的技术，也就是预先生成-128~127之间的所有常量对象，每次创建这个范围内的对象时直接返回其引用即可。在一般的程序中，这个范围内的常量使用很频繁，因此，这个常量池可以取得非常好的效果。
然而，Java、Python都会允许程序员做一些很Hacker的事情，例如，利用常量池优化使得2+2=5。
2015-05
Subscribe via RSS