Head Pic: [特殊能力統轄学院 -叛逆の優等生と悪魔を冠する少女の共犯契約- / December 6th, 2019 - pixiv](https://www.pixiv.net/en/artworks/78162147)

用途

用于系统化的求解埃及分数问题(尽管求得的序列不一定是最短的)

原理

如果$0<\frac{m}{n}<1$,那么:

$\frac{m}{n}=\frac{1}{q}+(\frac{m}{n}-\frac{1}{q})的表示(递归),q=\lceil\frac{n}{m}\rceil$

其实它是一个贪心算法,在每一步都选择一个可以想象到的最小的$q$

实现

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
package world.pixiv.math;

import java.math.BigInteger;
import world.pixiv.math.BasicFraction;

public class Fibonacci {
public static void main(String[] args) {
fibonacci(new BasicFraction(BigInteger.valueOf(9),BigInteger.valueOf(10)));
fibonacci(new BasicFraction(BigInteger.valueOf(99),BigInteger.valueOf(100)));
fibonacci(new BasicFraction(BigInteger.valueOf(999),BigInteger.valueOf(1000)));
fibonacci(new BasicFraction(BigInteger.valueOf(9999),BigInteger.valueOf(10000)));
fibonacci(new BasicFraction(BigInteger.valueOf(99999),BigInteger.valueOf(100000)));
}

public static void fibonacci(BasicFraction a) {
a = a.simplify();
if(a.up.equals(BigInteger.ONE)) {
System.out.print(a.toLatex() + "\n");
return;
}
BigInteger q = a.down.divide(a.up).add(BigInteger.ONE);
System.out.print("\\frac{1}{" + q.toString() + "}+");
a = a.subtract(new BasicFraction(BigInteger.ONE,q));
fibonacci(a);
}
}

例子:

$\frac{9}{10}=\frac{1}{2}+\frac{1}{3}+\frac{1}{15}$

$\frac{99}{100}=\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{73}+\frac{1}{9018}+\frac{1}{230409900}$

$\frac{999}{1000}=\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{44}+\frac{1}{12158}+\frac{1}{1404249000}$

$\frac{9999}{10000}=\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}+\frac{1}{2205}+\frac{1}{5125136}+\frac{1}{30371235615000}$

$\frac{99999}{100000}=\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}+\frac{1}{1840}+\frac{1}{4317880}+\frac{1}{32027874900000}$

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
package world.pixiv.math;

import java.math.BigInteger;

public class BasicFraction {
public BigInteger up,down;

public BasicFraction() {
up = down = BigInteger.ONE;
}

public BasicFraction(long up,long down) {
this.up = BigInteger.valueOf(up);
this.down = BigInteger.valueOf(down);
}

public BasicFraction(BigInteger up,BigInteger down) {
this.up = up;
this.down = down;
}

private BigInteger gcd(BigInteger a,BigInteger b) {
return b.equals(BigInteger.ZERO) ? a : gcd(b,a.mod(b));
}

public BasicFraction simplify() {
BigInteger g = gcd(up,down);
up = up.divide(g);
down = down.divide(g);
return this;
}

public BasicFraction add(BasicFraction a) {
return new BasicFraction(up.multiply(a.down).add(a.up.multiply(down)),down.multiply(a.down)).simplify();
}

public BasicFraction subtract(BasicFraction a) {
return new BasicFraction(up.multiply(a.down).subtract(a.up.multiply(down)),down.multiply(a.down)).simplify();
}

public BasicFraction multiply(BasicFraction a) {
return new BasicFraction(up.multiply(a.up),down.multiply(a.down)).simplify();
}

public BasicFraction divide(BasicFraction a) {
return this.multiply(new BasicFraction(a.down,a.up));
}

public String toLatex() {
return "\\frac{" + up.toString() + "}{" + down.toString() + "}";
}
}

评论