Go语言视频零基础入门到精通

五菱

The Farey sequences of orders 1 to 8 are
F1 = {0⁄1, 1⁄1}
F2 = {0⁄1, 1⁄2, 1⁄1}
F3 = {0⁄1, 1⁄3, 1⁄2, 2⁄3, 1⁄1}
F4 = {0⁄1, 1⁄4, 1⁄3, 1⁄2, 2⁄3, 3⁄4, 1⁄1}
F5 = {0⁄1, 1⁄5, 1⁄4, 1⁄3, 2⁄5, 1⁄2, 3⁄5, 2⁄3, 3⁄4, 4⁄5, 1⁄1}
F6 = {0⁄1, 1⁄6, 1⁄5, 1⁄4, 1⁄3, 2⁄5, 1⁄2, 3⁄5, 2⁄3, 3⁄4, 4⁄5, 5⁄6, 1⁄1}
F7 = {0⁄1, 1⁄7, 1⁄6, 1⁄5, 1⁄4, 2⁄7, 1⁄3, 2⁄5, 3⁄7, 1⁄2, 4⁄7, 3⁄5, 2⁄3, 5⁄7, 3⁄4, 4⁄5, 5⁄6, 6⁄7, 1⁄1}
F8 = {0⁄1, 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, 1⁄1}

在第n级上,仅当c+d<=n时,才将一个新的分数a+b/c+d插到两个相邻的分数a/c和b/d之间.下面的程序,对给定的自然数n,通过不断扩展以创建第n级的分数链表.

所使用的数据结构为一个链表节点

public class Node {

private int upval;//分子

private int dnval;//分母

private Node next;

public Node(int up, int down) {

upval = up;

dnval = down;

next = null;

}

public Node(int up, int down, Node next) {

upval = up;

dnval = down;

this.next = next;

}

public int getUpval() {

return upval;

}

public void setUpval(int upval) {

this.upval = upval;

}

public int getDnval() {

return dnval;

}

public void setDnval(int dnval) {

this.dnval = dnval;

}

public Node getNext() {

return next;

}

public void setNext(Node next) {

this.next = next;

}

}

下面是Farey序列的具体实现
1.构造子先设定了两个节点,即n=1的情况;
2.generate(int n)用于生成序列,每次会遍历当前序列,如果具备插入的点,则插入之,且将added设置为真;
3.如果遍历完后布尔值added为假,则说明序列已构造完成;
4.整型数turn表示每次需要判断插入的次数,它和前一轮得到的链表长度有关;

public class FareyList {

private Node head;

private int size;

public FareyList() {

head = new Node(0, 1);

Node next = new Node(1, 1);

head.setNext(next);

size = 2;

}

public void insertAfter(Node newNode, Node prev) {

newNode.setNext(prev.getNext());

prev.setNext(newNode);

size++;

}

public void generate(int n) {

if (n <= 0)

throw new UnsupportedOperationException();

if (n == 1) {

printList();

return;

}

boolean added = true;

while (added) {

int turn = size - 1;

added = false;

Node node1 = head;

Node node2 = head.getNext();

for (int i = 1; i <= turn; i++) {

if ((node1.getDnval() + node2.getDnval()) <= n) {

Node newNode = new Node(

node1.getUpval() + node2.getUpval(), node1

.getDnval()

+ node2.getDnval());

insertAfter(newNode, node1);

added = true;

}

node1 = node2;

node2 = node2.getNext();

}

}

printList();

}

private void printList() {

Node node = head;

while (node != null) {

System.out.print(node.getUpval() + "  ");

node = node.getNext();

}

System.out.println();

node = head;

while (node != null) {

System.out.print(node.getDnval() + "  ");

node = node.getNext();

}

System.out.println();

}

public static void main(String[] args) {

new FareyList().generate(8);

}

}