Project Euler Problem 71 describes as follows:

Consider the fraction, n/d, where n and d are positive integers. If n < d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

Such sequences can be included to be a Stern–Brocot tree

It all starts with fractions and the number line. We start off with the interval [0,1]:

Now let’s play a little game. We’re going to take the fractions 0/1 and 1/1 and calculate their mediant by taking the sum of their numerators and denominators to get (0+1)/(1+1)=1/2:

With this new point on the line, we can do this mediant operation again to get (0+1)/(1+2)=1/3 and (1+1)/(2+1)=2/3:

Another iteration of this process gives:

But we can continue this process indefinitely! And instead of notating these fractions on the number line, we can put them into a tree:

Now of course, merely having fractions between zero and one isn’t satisfying enough, so we extend the construction of this tree to begin with the points 0/1 and 1/0, as nonsensical as that may sound. Then we get something like this:

This is the Stern-Brocot tree.

Here we use the subtree which root is 1/2:

We need to find a node between 2/5 and 3/7. first, take numerators as [2, 3], denominators as [5, 7]
so we can find a node between 2/5 and 3/7, that is $\frac {2+3} {5+7} = \frac 5 {12}$. Then iteratively we use the same strategy to find a node between 5/12 and 3/7. When we reach the condition that denominator > 1000,000, loop terminates.

Here is the code using coffeescript:

1
2
3
4
5
6
7

[n, d] = [2, 5]

while d <= 1000000
	n += 3
	d += 7
# go back if we exceeds 
console.log n - 3

Reference: http://hxhl95.github.io/stern-brocot-tree-part-1/

事实上，可以证明：
如果$\frac a b < \frac c d$，则$\frac a b < \frac {a+c} {b+d} < \frac c d$
证明如下：
由$\frac a b ①< \frac c d②$ 可以得到：$ad < bc$，那么$\frac a b = \frac {ab+ad} {b(b+d)} < \frac {ab+bc} {b(b+d)} = \frac{a+c}{b+d}③$
即① < ③

且：
$\frac{a+c}{b+d} = \frac {ad+cd} {d(b+d)} < \frac {bc+cd} {d(b+d)} = \frac c d$
即③ < ②

$\therefore ①<③<② that is \frac a b < \frac {a+c}{b+d} < \frac c d$

• 编码系统

字符就是我们看到的”文字“。世界上有很多种语言，比如英语，法语，中文，日语，韩语等等。’abcd’, ‘我’, ‘ả’等等都是字符。字符是人类理解的文字，而计算机则只能理解二进制位(010101…)，8个二进制位为一个字节(byte)。要将人类理解的字符转换成计算机理解的字节，就需要编码(encode)。英语世界里有一个著名的编码系统ASCII，使用一个字节来编码字符。ASCII码一共规定了128个字符的编码，比如空格”SPACE”是32（二进制00100000），大写的字母A是65（二进制01000001）。这128个符号（包括32个不能打印出来的控制符号），只占用了一个字节的后面7位，最前面的1位统一规定为0。但是在非英语语系中，像中文，日语和韩语等语言，一个字节并不能编码所有的字符，这时ASCII编码就不适用了。

不同的国家就创造了自己的编码系统。比如简体中文的GB2312，繁体中文的big5，俄语用koi8-r等。但是不同的编码系统会造成混乱，比如130在法语编码中代表了é，在希伯来语编码中却代表了字母Gimel (ג)。所以如果两个人在交换文件时用的编码却不同就会出现所谓的”乱码“。

这个时候，UNICODE出现了。当当当，救星出世！

Unicode编码系统为表达任意语言的任意字符而设计。它使用4字节的数字来表达每个字母、符号，或者表意文字(ideograph)。每个数字代表 唯一 的至少在某种语言中使用的符号。这样一来，每个字符对应一个数字，每个数字对应一个字符。即不存在二义性。不再需要记录“模式”了。U+0041总是代表’A’，即使这种语言没有’A’这个字符。

http://unicode-table.com/可以查看所有字符的Unicode码。

Unicode又有几种实现形式：

1. UCS-4(UTF-32) 使用4字节编码
2. UCS-2(UTF-16) 使用2字节编码
3. UTF-8 使用1-4字节编码

其中以UTF-8最流行。

UTF-8是一种为Unicode设计的变长(variable-length)编码系统。即，不同的字符可使用不同数量的字节编码。对于ascii字符(A-Z, &c.)utf-8仅使用1个字节来编码。事实上，utf-8中前128个字符(0–127)使用的是跟ascii一样的编码方式。像ñ和ö这样的“扩展拉丁字符(Extended Latin)”则使用2个字节来编码。中文字符比如“中”则占用了3个字节。很少使用的“星芒层字符”则占用4个字节。

这样既可以照顾到所有的字符又能节约存储空间，如果所有的计算机都使用UTF-8编码的话那就“沟通零距离”了。

• Python中的字符与字节

在Python 3中，所有的字符串都是使用Unicode编码的字符序列。utf-8是一种将字符编码成字节序列的方式。编码字符可以使用str.encode()，而解码则使用bytes.decode()

1
2
3
4
5
6

# 将'我'编码成字节序列(bytes)，使用utf-8
> '我'.encode('utf-8')
b'\xe6\x88\x91'
# 解码
> b'\xe6\x88\x91'.decode('utf-8')
'我'

• String vs. Bytes

字节即字节；字符是一种抽象。一个不可变(immutable)的Unicode编码的字符序列叫做string。一串由 0到255 之间的数字组成的序列叫做bytes对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 使用“byte字面值”语法b''来定义bytes对象。byte字面值里的每个字节可以是ascii字符或者是从\x00到\xff编码了的16进制数。
> by = b'abcd\x65'

# 一如列表和字符串，可以使用下标记号来获取bytes对象中的单个字节。对字符串做这种操作获得的元素仍为字符串，而对bytes对象做这种操作的返回值则为整数。确切地说，是0–255之间的整数。
> by[0] 
97

# bytes对象是不可变的；我们不可以给单个字节赋上新值。如果需要改变某个字节，
可以组合使用字符串的切片和连接操作(效果跟字符串是一样的)，或者我们也可以将bytes对象转换为bytearray对象。

> by[0] = 102   
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'bytes' object does not support item assignment
> barr = bytearray(by)
> barr[0] = 102 
> barr
bytearray(b'fbcde')

参考：http://sebug.net/paper/books/dive-into-python3/strings.html

• 二叉堆的定义

二叉堆是一棵完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。

这里我们实现 最小二叉堆堆 。

• 二叉堆的基本操作

下图是一个最小二叉堆，使用数组形式表示：数组索引从1开始。

1. 插入新元素

比如插入7，首先将7加在数组的末尾，然后与其父节点比较，如果小于父节点则与之交换，直到大于父节点或到达树的根部。

2. 删除最小元素

首先移除根部的元素。然后将最后一个元素移到根部，再向下过滤，遇到比它小的元素则交换，直到到达叶子节点或者没有比它更小的元素。

• 二叉堆实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

"""
BinaryHeap类：
方法：
delete_min：删除最小元素，时间复杂度为O(logN)
insert: 插入元素，时间复杂度为O(logN)
find_min: 返回最小元素，时间复杂度为O(1)
is_empty: 判断是否为空
"""

class BinaryHeap:
	def __init__(self, *args):
		i = len(args) // 2
		self.size = len(args)
		# index从1开始
		self.items = [None] + list(args)
		while i > 0:
			self.percolate_down(i)
			i -= 1

	def percolate_down(self, i):
		while i * 2 <= self.size:
			min_child_index = self.min_child(i)
			if self.items[i] > self.items[min_child_index]:
				self.items[i], self.items[min_child_index] = self.items[min_child_index], self.items[i]
			i = min_child_index

	def min_child(self, i):
		if 2 * i + 1 > self.size:
			return 2 * i
		else:
			if self.items[2*i] < self.items[2*i+1]:
				return 2 * i
			else:
				return 2 * i + 1

	def percolate_up(self, i):
		while i // 2 > 0:
			if self.items[i] < self.items[i // 2]:
				self.items[i], self.items[i // 2] = self.items[i // 2], self.items[i]
			i //= 2

	def delete_min(self):
		min_value = self.items[1]
		self.items[1] = self.items[self.size]
		self.size -= 1
		self.items.pop()
		self.percolate_down(1)
		return min_value

	def insert(self, data):
		self.size += 1
		self.items.append(data)
		self.percolate_up(self.size)

	def find_min(self):
		return self.items[1]

	def is_empty(self):
		return self.size == 0

# test
if __name__ == '__main__':
	binary_heap = BinaryHeap(9, 6, 5, 2, 3)

	# find_min
	# will print The minimum data of this Binary Heap is 2
	print("The minimum data of this Binary Heap is {0}".format(binary_heap.find_min()))

	# delete min
	binary_heap.delete_min()
	# will print The minimum data of this Binary Heap is 3
	print("The minimum data of this Binary Heap is {0}".format(binary_heap.find_min()))

	# insert 1
	# will print The minimum data of this Binary Heap is 1
	binary_heap.insert(1)
	print("The minimum data of this Binary Heap is {0}".format(binary_heap.find_min()))

	print(binary_heap.is_empty()) # False
	for i in range(5):
		binary_heap.delete_min()

	print(binary_heap.is_empty()) # True
	print(binary_heap.items) # [None]

我们知道，DOM对象只能使用原生JS的方法，而jQuery对象只能使用jQuery的方法。如果要在原生JS里使用jQuery对象或者对DOM对象使用jQuery方法的话就必须将二者进行转换。

• DOM对象转为jQuery对象

只需要将DOM对象用$()进行包装：
$(DOMObj)

• jQuery对象转为DOM对象

jQuery中介绍了一个get(index)的方法

> Retrieve the DOM elements matched by the jQuery object.

当然也可以使用数组形式的访问，如$("#selector")[0]

简单吧^_^