斐波那契数列

2014年蓝桥杯本科C/C++组预赛第9题是很好的一道关于斐波那契(Fibonacci)数列的题目。本文将从这一题母出发，探讨一些与斐波那契数列相关的性质。

题目

题目链接：斐波那契 http://lx.lanqiao.org/problem.page?gpid=T121

题目内容：

问题描述

斐波那契数列大家都非常熟悉。它的定义是：

　　$$ f(x) = 1 .... (x=1,2) $$ 　　$$ f(x) = f(x-1) + f(x-2) .... (x>2) $$

对于给定的整数 n 和 m，我们希望求出：$ f(1) + f(2) + \dots + f(n) $ 的值。但这个值可能非常大，所以我们把它对 $ f(m) $取模。

公式如下: $$ (\sum_{i=1}^n{f(i)}) \ mod \ f(m) $$

但这个数字依然很大，所以需要再对$ p $求模。

输入格式

输入为一行用空格分开的整数 n m p (0 < n, m, p < 10¹⁸⁾

输出格式

输出为1个整数，表示答案

样例输入

2 3 5

样例输出

0

样例输入

15 11 29

样例输出

25

组合博弈与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。

社交网站站内排名与社区演化

社交网站站内排名一直是一个热门的话题，一套好的排名机制有助于将社区中精华的内容(如博客、帖子、评论等)优先推送给网站用户，从而有效促进社区的良性发展。本文将以Reddit和知乎这两个热门社交网站为例，分析其站内排名算法的优缺点，并探讨其对整个社区内社团形成以及同质化的作用和影响。

知乎排名算法

知乎是一个基于问答的社交网站，以“创造有价值的内容”和“保持友善和尊重”为核心原则：

创造有价值的内容：知乎的初衷是帮助人们可以更好的分享彼此的知识、经验和见解，发表有用、有帮助、有质量的内容，不仅可以帮助他人，也会让自己获益。

保持友善和尊重：不要攻击、故意贬低用户或者他写的内容，尊重不同的观点，不恶意揣测动机。

Java 多线程

随着多核芯片逐渐成为主流，大多数软件开发人员不可避免地需要了解并行编程的知识。而同时，主流程序语言正在将越来越多的并行特性合并到标准库或者语言本身之中。我们可以看到，JDK 在这方面同样走在潮流的前方。从JDK 5到JDK 7，越来越多的线程相关的新API加入到了标准库中，为不同场景下对线程实现与调度提供了完善的支持。我们可以充分利用这些类库，来提高开发效率，改善程序性能。

Java中使用线程

Java的多线程基于以下两个重要的机制：

1. 父线程结束，如果子线程正在运行，子线程不会跟着结束。
2. 每个线程拥有一个线程栈，会维护引用，用于GC。

约数个数加倍

最近在Project Euler上看到一道很有意思的题目，题目大意是找到一个最小的正整数，这个正整数有 $2^{500500}$ 个约数。将原题摘引如下：

The number of divisors of 120 is 16.

In fact 120 is the smallest number having 16 divisors.

Find the smallest number with 2⁵⁰⁰⁵⁰⁰ divisors.

Give your answer modulo 500500507.

欧拉路径

总结下欧拉路径相关的算法。

相关的定义

1. 欧拉环：图中经过每条边一次且仅一次的环；
2. 欧拉路径：图中经过每条边一次且仅一次的路径；
3. 欧拉图：有至少一个欧拉环的图；
4. 半欧拉图：没有欧拉环，但有至少一条欧拉路径的图。

社区发现与K-means聚类

将机器学习中的概率算法模型引入社区发现和网络图划分算法的研究--以K-means算法为例。

摘要

社区发现(Community Detection)作为社会网络科学的经典问题之一，长期以来一直受到领域内研究者的广泛关注，近二十多年来，社区发现以及社交网络图的划分算法一直是定义期刊、会议的热点之一。本文旨在阐述如何将机器学习的概率算法模型引入社区发现和网络图划分的研究中来，通过合理利用成熟的机器学习技术来改善传统算法面对超大规模社交网络时在效率、性能和准确性上的不足。