fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Scanner;
  4.  
  5. class Ideone
  6. {
  7.     public static void main(String[] args)
  8.     {
  9.         try (Scanner in = new Scanner(System.in))
  10.         {
  11.             while (in.hasNextInt())
  12.             {
  13.                 farey(in.nextInt());
  14.             }
  15.         }
  16.     }
  17.  
  18.     static void farey(int m)
  19.     {
  20.         ArrayList<String> farey = new ArrayList<>();
  21.         Stack stack = new Stack();
  22.         stack.push(fraction(1, 1));
  23.         stack.push(fraction(0, 1));
  24.  
  25.         while (true)
  26.         {
  27.             long l = stack.pop();
  28.             farey.add(fractionToString(l));
  29.             if (stack.isEmpty()) break;
  30.  
  31.             while (true)
  32.             {
  33.                 long r = stack.peek();
  34.                 if (!test(l, r, m)) break;
  35.                 stack.push(l + r);
  36.             }
  37.         }
  38.  
  39.         System.out.printf("Farey[%d] => %s%n", m, farey);
  40.     }
  41.  
  42.     static long fraction(int n, int d)
  43.     {
  44.         return (long) n << 32 | d;
  45.     }
  46.  
  47.     static boolean test(long l, long r, int m)
  48.     {
  49.         return (l & 0xFFFFFFFFL) + (r & 0xFFFFFFFFL) <= m;
  50.     }
  51.  
  52.     static String fractionToString(long l)
  53.     {
  54.         return (l >>> 32) + "/" + (l & 0xFFFFFFFFL);
  55.     }
  56.  
  57.  
  58.     static class Stack
  59.     {
  60.         long[] array = new long[64];
  61.         int ptr;
  62.  
  63.         void push(long l)
  64.         {
  65.             if (ptr == array.length) array = Arrays.copyOf(array, array.length * 2);
  66.             array[ptr++] = l;
  67.         }
  68.  
  69.         long pop()
  70.         {
  71.             return array[--ptr];
  72.         }
  73.  
  74.         long peek()
  75.         {
  76.             return array[ptr - 1];
  77.         }
  78.  
  79.         boolean isEmpty()
  80.         {
  81.             return ptr == 0;
  82.         }
  83.     }
  84. }
  85.  
Success #stdin #stdout 0.1s 2841600KB
comments (?)
stdin
copy 
3
5
8
stdout
copy 
Farey[3] => [0/1, 1/3, 1/2, 2/3, 1/1]
Farey[5] => [0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1]
Farey[8] => [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]
https://ideone.com/w0q7cN
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!