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

javalearner

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);
     }
}
      
     
   
  
    本文出自 “子 孑” 博客，请务必保留此出处http://zhangjunhd.blog.51cto.com/113473/54836
   
   

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/14/000830531.zip