75 lines
1.9 KiB
Java
75 lines
1.9 KiB
Java
import java.util.Scanner;
|
|
|
|
public class FiboBin {
|
|
|
|
/**
|
|
* Computes the n-th Fibonacci number using recursion.
|
|
* This method is intended only for internal use and is not optimized.
|
|
*
|
|
* @param f index of Fibonacci number (must be >= 0)
|
|
* @return the n-th Fibonacci number
|
|
*/
|
|
private static int Fib(int f){
|
|
if (f < 2) {
|
|
return 1;
|
|
}
|
|
int st = 1;
|
|
int sec =1;
|
|
int thi = 0;
|
|
for (int k = 3; k <= f; k ++){
|
|
thi = st + sec;
|
|
st = sec;
|
|
sec = thi;
|
|
}
|
|
return sec;
|
|
}
|
|
|
|
/**
|
|
* Counts the number of bits set to '1' in the binary representation of the given integer.
|
|
*
|
|
* @param b the input number (must be non-negative)
|
|
* @return the number of 1-bits in x
|
|
*/
|
|
private static int Bin(int b){
|
|
int ones = 0;
|
|
while (b > 0){
|
|
ones += b%2;
|
|
b = (int) b/2;
|
|
}
|
|
return ones;
|
|
}
|
|
|
|
/**
|
|
* Determines whether the given number n is a FiboBinary number.
|
|
*
|
|
* @param n the number to test (must be non-negative)
|
|
* @return true if fib(n) equals the number of ones in the binary form of n, false otherwise
|
|
*/
|
|
public static boolean isFiboBin(int n){
|
|
int i = 1;
|
|
while (true){
|
|
int fib = Fib(i);
|
|
if (fib > n){
|
|
break;
|
|
}
|
|
int bin = Bin(fib);
|
|
if ( bin + fib == n){
|
|
return true;
|
|
}
|
|
i++;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
Scanner sc = new Scanner(System.in);
|
|
int number = sc.nextInt();
|
|
if (isFiboBin(number)){
|
|
System.out.println(number+ " is FiboBinary.");
|
|
}
|
|
else{
|
|
System.out.println(number+ " is not FiboBinary.");
|
|
}
|
|
}
|
|
}
|