Fibonacci数列是这样定义的：
F[0] = 0
F[1] = 1
for each i ≥ 2: F[i] = F[i-1] + F[i-2]
因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, ...，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。
[编程题]Fibonacci数列
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int[] fibs=new int[n];
fibs[0]=0;
if (n>1) {
fibs[1] = 1;
getFibs(fibs);
}
int i=1;
while (i<n){
if (fibs[i]>=n){
break;
}
i++;
}
if (n>1) {
System.out.println(Math.min(n - fibs[i - 1], fibs[i] - n));
}else {
System.out.println(0);
}
}
private static void getFibs(int[] arr){
for (int i=2;i<arr.length;i++){
arr[i]=arr[i-1]+arr[i-2];
}
}
}
发表于 2022-12-10 17:35:58
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int f1 = 0;
int f2 = 1;
int f3 = 0;
while(f2 < n){
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
if(Math.abs(n - f1) > Math.abs(f2 - n)){
System.out.println(Math.abs(f2 - n));
}else{
System.out.println(Math.abs(f1 - n));
}
}
}
发表于 2022-03-29 15:17:24
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int num=sc.nextInt();
int i=0;
int j=1;
int temp=0;
while(j<num){
temp=i;
i=j;
j=temp+j;
}
System.out.println(Math.min(j-num,num-i));
}
}
}
发表于 2021-08-31 20:57:57
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int f1 = 0;
int f2 = 1;
int f3 = 0;
while(f2 < n){
f3 = f1+f2;
f1 = f2;
f2 = f3;
}
if(Math.abs(f1-n)<Math.abs(f2-n)){
System.out.println(Math.abs(f1-n));
}else{
System.out.println(Math.abs(f2-n));
}
}
}
发表于 2021-06-16 17:01:07
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int res = minStepToFib(n);
System.out.println(res);
}
sc.close();
}
private static int minStepToFib(int n){
int pre = 0;
int cur = 1;
while(cur < n){
int temp = pre;
pre = cur;
cur = cur + temp;
}
return Math.min(cur - n, n - pre);
}
}
发表于 2020-08-17 17:09:42
回复(0)
- 一开始自己的斐波那契数列有误，没注意索引为0的情况
- 第一大类，输入的数如果是负数，直接输出它的相反数。
- 第二大类，遍历斐波那契数列，输入的数n如果等于斐波那契数列的数，就输出0；
如果输入的数大于遍历到的斐波那契数列的数的话，就一直循环，直到输入的数小于斐波那契数列的数。将n与前一个斐波那契数数作差，再与当前的遍历到的数作差，取绝对值最小的那个。
import java.util.*;
public class Main
{
public static void main(String [] args)
{
Scanner sc=new Scanner(System.in);
while(sc.hasNextInt())
{
int n=sc.nextInt();
if(n<0)
{
System.out.println(-n);
}
else
{
for(int i=0;;i++)
{
int val=fib(i);
if(n==val)
{
System.out.println(0);
break;
}
else if(n<val)
{
int a=Math.abs(n-val);
int b=Math.abs(n-fib(i-1));
int min=a<b?a:b;
System.out.println(min);
break;
}
}
}
}
}
private static int fib(int n)//斐波那契函数
{
if (n==0)
{
return 0;
}
int a=0;
int b=1;
for(int i=1;i<n;i++)
{
b=a+b;
a=b-a;
}
return b;
}
}
发表于 2020-03-28 16:15:14
回复(0)
Java实现，已通过。动态规划法创建 Fibonacci数列，需要找到比 n 小和大的第一个数。比如 n=15,对应的数是 13 ，21 ，创建到 21 即可。
通过观察可发现，对于 15 这个数，”每一步可以把当前数字 x 变为 x-1 或者 x+1“，
第 0 步可以得到本身：15；
第 1 步可以得到：14，16;
第 2 步可以得到 13，15，17；
第 3 步可以得到 12，13，14，16，18；
第 4 步可以得到 11，13，12，14，15，17，19.
... ...
划线的是重复的，需要最小的步数，肯定要取之前的。可以发现规律，对于m ,最少需要 |m-n| 步，能变为n。所以需要知道：比 n 小和大的第一个数，哪个离 n 更近，它就是m。
对于n=0或1 ，本身就是Fibonacci数列的元素，输出0即可。代码如下：
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
if(n<=1) {System.out.println(0);
return;}
//构造fibonacci数组
int[] fibonacci=new int[n];
fibonacci[0]=0;
fibonacci[1]=1;
int flag=0;
for (int i=2;i<n;i++)
{fibonacci[i]=fibonacci[i-1]+fibonacci[i-2];
if(fibonacci[i-1]<=n&&fibonacci[i]>=n)
{flag=i;
break;
}}
int min=n-fibonacci[flag-1]<fibonacci[flag]-n?fibonacci[flag-1]:fibonacci[flag];
System.out.println(Math.abs(n-min));
}
}
编辑于 2020-02-06 14:50:33
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
int lo=1;
int hi=1;
Scanner in = new Scanner(System.in);
int N=in.nextInt();
while(N>hi){
hi=lo+hi;
lo=hi-lo;
}
System.out.println(((hi-N)>(N-lo))?(N-lo):(hi-N));
}
//当N一直大于hi时，不断extend数列；一直到N小于等于hi了，则比较N离lo和hi哪个更近
}
public class Main{
public static void main(String[] args){
int lo=1;
int hi=1;
Scanner in = new Scanner(System.in);
int N=in.nextInt();
while(N>hi){
hi=lo+hi;
lo=hi-lo;
}
System.out.println(((hi-N)>(N-lo))?(N-lo):(hi-N));
}
//当N一直大于hi时，不断extend数列；一直到N小于等于hi了，则比较N离lo和hi哪个更近
}
发表于 2018-10-11 04:14:06
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int f = 0;
int t = 1;
while(f + t < n){
int temp = f;
f = f + t;
t = temp;
}
int min = n - f < f+t-n?n-f:f+t-n;
System.out.println(min);
}
}
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int f = 0;
int t = 1;
while(f + t < n){
int temp = f;
f = f + t;
t = temp;
}
int min = n - f < f+t-n?n-f:f+t-n;
System.out.println(min);
}
}
发表于 2018-08-09 09:44:52
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String line = scanner.nextLine();
long n = Long.parseLong(line);
System.out.println(min(n));
}
public static long min (long n) {
for (int i = 1; i <= n;i ++) {
if (fib(i) >= n && fib(i - 1) <= n) {
return fib(i) - n > n - fib(i - 1) ? n - fib(i - 1) : fib(i) - n;
}
}
return 0;
}
public static long fib(int n) {
if (n == 1 || n == 0)return n;
long []dp = new long[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2;i <= n;i ++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
发表于 2018-05-21 16:45:39
回复(0)
http://www.cnblogs.com/52circle/p/9023647.html
import java.util.ArrayList;
import java.util.Scanner;import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int a=0;
int b=1;
int c=0;
ArrayList<Integer> m=new ArrayList<Integer>();
m.add(a);
m.add(b);
while (c<=1000000) {
c=a+b;
a=b;
b=c;
if (c<=1000000) {
m.add(c);
}
}
int l=m.size();
int s1=0;
int s2=0;
for (int i = 0; i < l; i++) {
if (m.get(i)<n&&m.get(i+1)>=n) {
s1=Math.abs(m.get(i)-n);
s2=m.get(i+1)-n;
}
}
if (s1>s2) {
System.out.println(s2);
}else {
System.out.println(s1);
}
}
}
发表于 2018-05-11 17:10:27
回复(0)
---------------------------------------Java---------------------------------
import java.util.Scanner;public class Main{ public static void main(String[] args) { Scanner in =new Scanner(System.in); System.out.println(getResult(in.nextInt())); } public static int getResult(int N) { int i=0,flag1=0,flag2=0; for(;;i++) {//寻找输入值N处于哪两个fibo数之间 flag2=fibo(i); if(flag2>N) break; flag1=flag2; } return N-flag1>flag2-N?flag2-N:N-flag1;//输出结果 } public static int fibo(int number)//递归斐波那契 { if(number==0 || number == 1) return number; else return fibo(number-1)+fibo(number-2); } }
编辑于 2018-05-04 18:28:42
回复(1)
思路：找到小于输入值和大于输入值的两个斐波那契数，然后从中挑出一个与输入值n相差较小的值
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int f0 = 0;
int f1 = 1;
int currFib = f1,prevFib = f0; //currFib记录当前的斐波那契数，prevFib记录前一个斐波那契数
while(currFib < n){
int temp = prevFib;
prevFib = currFib;
currFib += temp;
}//循环跳出表明currFib>=n，prevFib<n
System.out.println((currFib-n) >= (n-prevFib)?(n-prevFib):(currFib-n));
}
}
发表于 2018-03-17 13:37:10
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int i = 0;
//找到大于输入值的fib数为第几个
while(num > getNextFib(i)) {
i++;
}
//比较求出差值最小的数
int min = (getNextFib(i)-num) > (num - getNextFib(i-1)) ? (num - getNextFib(i-1)) : (getNextFib(i)-num);
System.out.println(min);
}
/**
* 获取fib数列的值
*/
public static int getNextFib(int n) {
if (n == 0) {
return 0;
}
if (n == 1){
return 1;
}
return getNextFib(n-1) + getNextFib(n-2);
}
}
//动态规划
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int s1 = 0, s2 = 1, s3;
while(num > s2) {
s3 = s1 + s2;
s1 = s2;
s2 = s3;
}
//比较求出
int min = (s2-num) > (num - s1) ? (num - s1) : (s2-num);
System.out.println(min);
}
}
编辑于 2018-03-14 14:11:26
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int N = sc.nextInt();
int a = 0,b = 1;
int c = 1,step1 = 0,step2 = 0;
while(c < N){
a = b;
b = c;
c = a + b;
}
while(c != N){
c--;
step2++;
}
while(b != N){
b++;
step1++;
}
System.out.println(step1<step2?step1:step2);
}
sc.close();
}
}
发表于 2018-01-23 12:59:08
回复(0)
//对于多次查询，查表法效率较高
import java.util.*;
public class Main {
public static void main(String[] args) {
int len = 32;
int[] table = new int[len]; //查表
table[1] = 1;
for (int i = 2; i < len; i++)
table[i] = table[i-1] + table[i-2];
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int num = in.nextInt();
int index = 0;
for (int i = 0; i < len; i++)
if (table[i] < num) index++;
int res = Math.min(Math.abs(table[index] - num), Math.abs(table[index - 1] - num));
System.out.println(res);
}
}
}
-----------------------------------------------------------------------
import java.util.*;
public class Main {
public static void main(String[] args) {
int f0 = 0, f1 = 1;
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int target = in.nextInt();
int res1 = 0, res2 = 0;
while (true) {
int f = f0 + f1;
f0 = f1;
f1 = f;
if (f < target) res1 = target - f;
else {
res2 = f - target; break;
}
}
System.out.println(Math.min(res1, res2));
}
}
}
编辑于 2017-12-07 16:08:10
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in=new Scanner(System.in);
int number=in.nextInt();
in.close();
int[] Fi=new int[100];
int i=2;
Fi[0]=0;
Fi[1]=1;
for(i=2;i<100;i++){
Fi[i]=Fi[i-1]+Fi[i-2];
if(Fi[i]>=number&&Fi[i-1]<=number){
break;
}
}
int MIN=Math.min(Fi[i]-number, number-Fi[i-1]);
System.out.print(MIN);
}
}
发表于 2017-09-12 18:11:16
回复(0)
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int step; for(int i=0;;i++){ //System.out.println(Fibonacci(i)); if(N<Fibonacci(i)){ //System.out.println(i); step = (Fibonacci(i)-N)<(N-Fibonacci(i-1))?(Fibonacci(i)-N):(N-Fibonacci(i-1)); break; } } System.out.println(step); } public static int Fibonacci(int i){ if(i == 0) { return 0; } else if (i == 1) { return 1; }else{ return Fibonacci(i-1) + Fibonacci(i-2); } } }
编辑于 2017-09-01 11:54:18
回复(0)
本题其实也就是寻找最短路径，给出一个值，找出F数中与该值相隔最小的数之间的距离值，通过将所有的F数进行依次判断并将距离值设置成正数进行比较即可找到最终结果
import java.util.Scanner;
public class Main {
//F数
public static void main(String[] args) {
int f[] = new int[1000];
f[0] = 0;
f[1] = 1;
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int dis = n-f[1];
if(dis < 0){
dis = -dis;
}
int i = 2;
while(true){
f[i] = f[i-1] + f[i-2];
int temp = n-f[i];
if(temp < 0){
temp = -temp;
}
if(temp > dis){
System.out.println(dis);
return ;
}
dis = temp;
i++;
}
}
}
发表于 2017-08-31 10:56:08
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-09 13:31:47
-
2023-02-19 11:48:47
-
2023-02-07 18:57:54 -
2023-02-04 12:32:18
-
2023-02-01 21:07:57
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
