Head Pic: 特殊能力統轄学院 -叛逆の優等生と悪魔を冠する少女の共犯契約- / December 6th, 2019 - pixiv

用途

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

原理

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

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

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

实现

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}$

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() + "}";
    }
}
最后修改:2020 年 01 月 01 日 02 : 50 PM