当前位置:网站首页>牛客网 Fibonacci数列
牛客网 Fibonacci数列
2022-07-22 05:49:00 【怠惰的未禾丶】
一. 题目
1. 题目
F i b o n a c c i Fibonacci Fibonacci数列是这样定义的:
F [ 0 ] = 0 F[0] = 0 F[0]=0
F [ 1 ] = 1 F[1] = 1 F[1]=1
f o r e a c h i ≥ 2 : F [ i ] = F [ i − 1 ] + F [ i − 2 ] for each i ≥ 2: F[i] = F[i-1] + F[i-2] foreachi≥2:F[i]=F[i−1]+F[i−2]
因此, F i b o n a c c i Fibonacci Fibonacci数列就形如: 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , . . . , 0, 1, 1, 2, 3, 5, 8, 13, ..., 0,1,1,2,3,5,8,13,...,在 F i b o n a c c i Fibonacci Fibonacci数列中的数我们称为 F i b o n a c c i Fibonacci Fibonacci数。给你一个 N N N,你想让其变为一个 F i b o n a c c i Fibonacci Fibonacci数,每一步你可以把当前数字 X X X变为 X − 1 X-1 X−1或者 X + 1 X+1 X+1,现在给你一个数 N N N求最少需要多少步可以变为 F i b o n a c c i Fibonacci Fibonacci数。
输入描述:
输入为一个正整数 N ( 1 ≤ N ≤ 1 , 000 , 000 ) N(1 ≤ N ≤ 1,000,000) N(1≤N≤1,000,000)
输出描述:
输出一个最小的步数变为 F i b o n a c c i Fibonacci Fibonacci数"
示例 1 1 1
输入
15 15 15
输出
2 2 2
2. 原题链接
二. 解题思路
1. 思路分析
( 1 ) (1) (1)找某一个数n变成最近的 F i b o n a c c i Fibonacci Fibonacci数的最小步数 n u m num num
( 2 ) (2) (2)找到与这个数相邻的两个 F i b o n a c c i Fibonacci Fibonacci数,并求出这个数与二者差值的绝对值 a b s 1 , a b s 2 abs1,abs2 abs1,abs2,二者的较小值就是最小步数 n u m num num
( 3 ) (3) (3) n n n的范围在 ( 0 , 1000000 ) (0,1000000) (0,1000000)之间, n n n是 0 0 0时最小步数直接就是 0 0 0,主要是要找到 n n n在哪两个相邻的 F i b o n a c c i Fibonacci Fibonacci数之间
( 4 ) (4) (4)已经知道 F i b o n a c c i Fibonacci Fibonacci数的前两项,后面的 F i b o n a c c i Fibonacci Fibonacci数可以由前两项推出;可以递归或循环得出除前两项的数
( 5 ) (5) (5)用两个变量 a 、 b a、b a、b记录两个初始的 F i b o n a c c i Fibonacci Fibonacci数 0 0 0和 1 1 1,在一个循环中判断 n n n与 b b b的大小关系
( 6 ) (6) (6) n 大于 b n大于b n大于b时说明不在这两个数之间,借助中间变量得到的新的 F i b o n a c c i Fibonacci Fibonacci数来更新这两个数,直到 n n n在这两个数之间,判断差值的绝对值之后再输出。
2. 代码详解
#include <stdio.h>
int main(){
int a = 0;
int b = 1;
int c = 0;
int n = 0;
scanf("%d", &n);
while(1){
if(n==0){
printf("0");
break;
}
else if(n<=b){
if((n-a) > (b-n)){
printf("%d", b-n);
}
else{
printf("%d", n-a);
}
break;
}
else{
c=a+b;
a=b;
b=c;
}
}
return 0;
}
三. 本题知识与收获
本题是斐波那契数列的应用,当知道所求步数与相邻斐波那契数的关系后,关键就是到输入的数在哪两个相邻的斐波那契数之间。
另一种思路是创建两个变量n1,n2记录n的初始值,两个计数器cnt1、cnt2分别记录左右的步数。每次判断n1、n2是否是斐波那契数。如果有一个是就输出两个计数器的较小值;如果两个都不是,则两个计数器都加1,数n1减1,n2加1。
E N D END END
边栏推荐
- Some new features in ES6
- NVIDIA hardware architecture
- JSON_ Incorrect problem returned by extract
- Win11闪白屏无法控制如何解决?
- 活动推荐| Apache Pulsar 在 vivo 的探索与实践 即将开播
- Simple use of UE4 terrain tool
- UE4 use of vegetation tools
- Hande x Jiuli special materials | work together to create a collaborative office portal and help it internal standardized management
- 分享我们的首次Otherside之旅
- UE4 writes the blueprint in the actor class to realize reuse
猜你喜欢
Apache自带的ab压力测试工具如何实现
keepalived
codeforce D2. RGB Substring (hard version) 滑動窗口
Hande enterprise PAAS platform hzero released version 1.5.0.release
vivo官网APP全机型UI适配方案
力扣刷题:dfs递归解决二叉树剪枝
Simple use of UE4 terrain tool
Server network performance tuning cases
Spark高级特性,220720,
Crack PLSQL by deleting the registry
随机推荐
LVS, this is enough
What is I18N and what is its function
怎么使用js实现计算器和计时器功能
Nvidia 硬件架构
tf.reduce_ sum()
UE4 level blueprint realizes door opening and closing
Qt5.9.2 initial import using msvc2017_ 64 record of problems encountered by compiler
Repair version of Dynamic Video Wallpaper wechat applet source code download, supporting various types of traffic main revenue
UE4 merge static mesh body
UE4 面试基础知识(三)
电子信息工程专业毕设题目选题推荐
重装Win11系统如何在线一键进行?
[paper translation] generalized radio representation learning via cross supervision between images
The aboveboard water stickers come from people's perception of summer vacation
tf.set_ random_ seed()
Hande enterprise PAAS platform hzero released version 1.5.0.release
Opencv supports H264 video coding
从0到1建设智能灰度数据体系:以vivo游戏中心为例
DOF depth of field Foundation
Write a sequencer plug-in sequence subtitle (1)