2014-01-28 65 views
0

我正在編程一個字符串的斐波那契表示,它會輸入一個字符串,並根據每個字母出現的頻率輸出字符串的位串形式(因此,例如,如果一個類型: 「卡內基梅隆」 那麼輸出將是:斐波那契位串表示

頁眉/ 01011/1011/000011/011 /十萬〇十一分之十一/ 00011/11/001011/010011/11/0011/0011/10011/011

在我們的任務中,我們也被要求計算頻率字符的數量,並排列它們。我已經完成了這部分,但是將這些char轉換爲斐波那契表示(我的程序根據rank輸出fib序列)感到困惑。

在任何情況下,由位字符串表示的意思混淆,這裏是一個簡單的例子:

2,7,4,3爲f(n)的就等於10,1010,101,100 我的老師要我們到一個1附加到它們中的每然後將等於011,01011,1011,0011

這是我的代碼:

import java.io.*; 
import java.util.*; 
import java.util.Map.Entry; 
public class Freq 
{ 
    public static void main(String args[])throws IOException 
    { 
     //read input stream 
     BufferedReader in=new BufferedReader(new InputStreamReader(System.in)); 
      System.out.println("Enter your String"); 
      String line = in.readLine(); 
      HashMap<Character,Integer> counts = new HashMap<>(); 
      for(char c : line.toCharArray()) {     //cycle through char array 
       Integer count = counts.get(c);     
       if (count == null) { 
        count = 0; 
       } 
       counts.put(c, ++count);       //count increments and places into map 
      } 
      List<Entry<Character,Integer>> list = new ArrayList<>(counts.entrySet()); 
      Collections.sort(list, new Comparator<Entry<Character,Integer>>() { 
       //@Override 
       public int compare(Entry<Character, Integer> o1, 
         Entry<Character, Integer> o2) { 
        return o2.getValue() - o1.getValue(); 
       } 
      }); 
      for(Entry<Character,Integer> entry : list) { 
       System.out.println("The character "+entry.getKey() +" has occured for "+ entry.getValue()+" times"); 
      } 

      int index = 0;       //fibanocci base case 
      for(Entry<Character,Integer> entry2 : list){ 
       System.out.println(fibonacci(index)); 
       index++; 
      } 
    } 
    public static long fibonacci(int i){ 
     if(i == 0){ 
      return 0;  //base case 
     } 
     if(i <= 2){ 
      return 1;  //base case 
     } 
     long fibTerm = fibonacci(i -1) + fibonacci(i-2); 
     return fibTerm; 
    } 
} 

輸出示例:

Enter your String 
this is a string 
The character has occured for 3 times 
The character s has occured for 3 times 
The character i has occured for 3 times 
The character t has occured for 2 times 
The character g has occured for 1 times 
The character r has occured for 1 times 
The character a has occured for 1 times 
The character n has occured for 1 times 
The character h has occured for 1 times 
0 
1 
1 
2 
3 
5 
8 
13 
21 

如何讓我的計算FIB#表示分爲斐波那契序列的這個位串的形式? 讓我知道,如果我能清除任何東西或添加信息的問題,以幫助你們完全理解我想要做的。

+0

如果我正確理解你的問題,你的問題是如何向後打印一個數字的二進制表示? – Njol

+0

@Njol不是二進制的,而是一種'斐波納契'二進制表示。每個數字位置對應1,2,3,5,8,13等等。所以斐波那契7 = 1010,因爲5 + 2 = 7。 – AOE

+0

編碼一個整數N: 找到等於或小於N的最大斐波那契數;從N中減去這個數字,跟蹤其餘部分。 如果減去的數字是第ith斐波那契數F(i),則在代碼字中將i-2置於1(將最左邊的數字計爲0的位置)。 重複之前的步驟,將餘數替換爲N,直到達到0的餘數。 在代碼字的最右邊數字之後再加1。 – Willmore

回答

0

我增加了一些功能的代碼:

基於 http://en.wikipedia.org/wiki/Fibonacci_codinghttp://en.wikipedia.org/wiki/Fibonacci_number

import java.io.*; 
import java.util.*; 
import java.util.Map.Entry; 

public class Freq { 
    public static void main(String args[]) 
     throws IOException { 

     /* read input stream */ 
     BufferedReader in = new BufferedReader(
       new InputStreamReader(
        System.in)); 

     /* System.out.println("Enter your String"); */ 
     String line = "carnegie mellon"; //in.readLine(); 

     Map<Character,Integer> counts = new HashMap<Character, Integer>(); 

     int ci = 0; 
     for(char c : line.toCharArray()) { /* cycle through char array */ 
      ci = counts.containsKey(c) 
       ? counts.get(c) + 1 
       : 1; 
      counts.put(c, ci); /* count increments and places into map */ 
     } 

     List<Entry<Character,Integer>> list = new ArrayList<>(
       counts.entrySet()); 
     Collections.sort(list, new Comparator<Entry<Character,Integer>>() { 
      @Override 
      public int compare(Entry<Character, Integer> o1, 
        Entry<Character, Integer> o2) { 
       return o2.getValue() - o1.getValue(); 
      } 
     }); 

     Map<Character, Integer> sorted = new HashMap<Character, Integer>(); 
     int i = 1; 
     for (Entry<Character,Integer> entry : list) { 
      System.out.println(
        "The character "  + entry.getKey() 
        + " has occured for " + entry.getValue() 
        + " times"); 
      /** count occurencies of character */ 
      sorted.put(
        entry.getKey(), i++); 
     } 


     System.out.print("Header/"); 
     for (String s : encode(line, sorted)) { 
      System.out.print(s + "/"); 
     } 
    } 

    /** 
    * Encode a given string. 
    */ 
    public static List<String> encode(
      String text, Map<Character, Integer> counts) { 
     List<String> encoded = new ArrayList<String>(); 
     for (char c : text.toCharArray()) { 
      encoded.add(
        bitSetAsString(
         numberToBits(
          counts.get(c)))); 
     } 
     return encoded; 
    } 

    /** 
    * Convert number to bits 
    */ 
    public static BitSet numberToBits(long n) { 
     /** next Fibonacci */ 
     long nextf = 0; 
     int i  = 0; 
     /** remainder */ 
     long rem = n; 
     /** 
     * Fibonacci numbers that encode the given n. 
     */ 
     List<Integer> fibs = new ArrayList<Integer>(); 

     /** temporary Fibonacci number */ 
     long tf ; 
     /** index of Fibonacci number */ 
     int fi ; 

     do { 
      /** Find largest Fibonacci smaller than rem. */ 
      i  = 2; 
      fi = i; 
      tf = Fibonacci.fibonacci(i); 
      nextf = tf; 
      while (tf < rem) { 
       tf = Fibonacci.fibonacci(i+1); 
       if (tf > rem) { 
        break; 
       } else { 
        nextf = tf; 
        fi = i+1; 
       } 
       i++; 
      } 

      rem = rem - nextf; 
      /** If found Fibonacci number collect it. */ 
      if (Fibonacci.isFibonacci(nextf)) { 
       fibs.add(fi); 
      } 
     } while (rem > 0); 

     /** make a bitset represenation */ 
     BitSet encoded = new BitSet(); 
     for(Integer j : fibs) { 
      encoded.set(j-2); 
     } 
     /** place an additional 1 after the rightmost digit in the code */ 
     encoded.set(
       encoded.length()); 

     return encoded; 
    } 

    public static String bitSetAsString(BitSet bs) { 
     StringBuilder sb = new StringBuilder(); 
     for (int i = 0; i < bs.length(); i++) { 
      sb.append(
        bs.get(i) 
        ? '1' 
        : '0'); 
     } 
     return sb.toString(); 
    } 


    static class Fibonacci { 
     public static long fibonacci(long i){ 
      return (0 == i || 1 == i) 
        ? i 
        : (fibonacci(i-1) + fibonacci(i-2)); 
     } 

     public static boolean isFibonacci(long n) { 
      long i  = 0; 
      long nextf = fibonacci(i); 
      while (nextf < n) { 
       nextf = fibonacci(++i); 
      } 
      return nextf == n; 
     } 
    } 
} 
+0

非常感謝你!當我到達一個編譯器時,我將分析並嘗試一下!這些Wiki資源非常豐富! – AOE