ID #5704

单链表实现Farey序列

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);
  }
}


2011-07-01 18:29
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

递归的应用 - 最简单分形图形实现

老调重提,利用SDK实现迷宫算法

CRC算法与实现

汉诺塔的C语言实现以及冒泡排序

二叉查找树的解析与实现