未登录,请登录后再发表信息
最新评论 (0)
播放视频

编程面试题1:在斐波那契数列中寻找第n个数

Interview Question 1: Write a function to find the nth number in a fibonnacci sequence

大家今天怎么样?
How are you guys doing today?
我今天要做一个视频 关于
What I wanted to do today was to creat a video on
我在一次面试中被要求做的一道编程面试题
a coding interview assignment I was asked to complete during an interview.
这就是他们让我做的
Here is what they want me to do.
他们要我完成一个函数 它返回斐波那契数列的第n个数
They want me to implement a function that returns the nth number in a Fibonacci sequence.
我要做的第一件事是分析问题
So the first thing I have to do was break down the problem.
如你所见 屏幕上是一张表格
As you can see on the screen, there’s a chart.
这张表格分成两个区域
This chart is divided up into two sections:
一个写着n 它代表一个数
one section will be n which represents a number.
另一个写着fib(n) 它代表斐波那契数
And another section is fib n which represents the Fibonacci number.
当说到斐波那契数列
So when it comes to the Fibonacci sequence
数列当前的数等于前两个数之和
the current number of the fib sequence will be equal to the sum of previous two numbers.
但那有两个基本条件
But there are two base cases.
如果n是1 斐波那契数就是1
If the number entered n is one, the Fibonacci number is one
如果n是2 斐波那契数就是1
And if the number entered n is two the Fibonacci number is one.
如果我们输入3
But let’s just say we enter in three if we enter in three
我们必须把前两个斐波那契数相加来得到当前这个斐波那契数
we have to add the Fibonacci the previous two Fibonacci numbers together in order to get that current Fibonacci number.
下一件事是我需要创建一个公式
So next thing I have to do was create a formula.
举例来说 我们有同一张表 但我们不知道第四个斐波那契数是什么
So let’s just say for example we have the same chart but we don’t know what the Fibonacci number of four is
我们怎样去做
how we go about doing that.
第一步 我们需要创建公式
The first thing we need to do is create a formula.
现在我们用这个公式 来寻找第四个斐波那契数
Now with this formula let’s just say we’re looking for Fibonacci number of four
我们代入4 我们得到 Fib(4)=Fib(4-1)+Fib(4-2)
We’ll pass in four and we get Fibonacci 4 equals Fibonacci 4 minus 1 plus Fibonacci 4 minus 2
它表示当前的斐波那契数等于前两个斐波那契数之和
which pretty much states that the current Fibonacci number is going to be equal to the sum of the previous two numbers.
然后我们简化它 Fib(4)=Fib(3)+Fib(2)
So we then simplify this we then get Fibonacci 4 equals Fibonacci 3 plus Fibonacci 2.
我们已经知道第三个和第二个斐波那契数
We already know what Fibonacci 3 is and we also know what Fibonacci 2 is.
我们看一下表格 第3个斐波那契数等于2
If we just look at the chart Fibonacci 3 is going to be equal to 2
第2个斐波那契数等于1
Fibonacci 2 is going to be equal to 1.
我们把这两个值相加
So we add these two values together.
最终我们得到第4个斐波那契数等于3
And we ultimately we ultimately get Fibonacci 4 equals to three.
现在我们开始编程
So let’s get to the code now.
我要做的第一步是写一个函数
The first thing that I want to do is write a function.
它返回一个数
This function is going to return a number.
它同样会接收一个数
And the function will also take in a number.
现在我开始写这个函数
Now when I put together the method
第一步是检查基本情况
the first thing I want to do is check for the base cases.
现在和我在陈述中说的一样
Now as I stated in my presentation,
有两个基本条件 1和2
there are two base cases 1 and 2.
我要做的就是添加条件语句
So what I want to do is add conditional statement that is
如果n小于等于2 那么返回值是1
if n is less than or equal to 2 then I want to return 1
所以 “if (n <= 2)"
so if n is less than or equal to 2
然后 “return 1”
then I want to return 1.
现在我要写else语句
Now I also want to write an else condition
这一条件将会包含实际的
and this else condition is going to contain the actual formula for calculating
基于给定的数求斐波那契数的计算公式
the Fibonacci number based on the given number.
你要输入 “return fib(n-1)+fib(n-2)”
So you want to return fib n minus 1 plus fib n minus 2
保存
let’s save this.
基本上 我们这里用的是一个递归的方法
And basically what we have here is a recursive method
它将调用它本身这个函数 直到
that is going to invoke a method call upon itself until it comes up with
找到我们要的斐波那契数
the Fibonacci number that we are looking for.
我们要向上回到主函数那里
So what we want to do is to go up to this main method.
打印出这个函数的值
And print the value of this method out.
比如输入 fib(4)
Let’s just say fib of 4.
如果一切正确 我们就会得到
So if we do this correctly this is what we should get.
Fib(4)返回3
Fib 4 is supposed to return 3.
我们输入4 这是我们的公式
we enter in 4 this is our formula that we have
现在运行程序
And now we just simply run the application.
确实得到了3
We have 3 exactly what we wanted.
在面试中 当实现函数后
During the interview after implementing the function
我被问到一些关于这个函数的问题
I was then asked what are some problems with the function that I have written
我当时脑袋空空的 不知道怎么回答
my mind went blank and I didn’t know how to respond.
做了一些研究后 我明白有三件事是在写完函数后需要注意的
After doing some research I learned there were 3 things I need to take note of after writing the function.
第一件事 检查小于1的数
The first thing checking for numbers below 1.
让我们回到代码里
Now let’s go back to the code.
我需要检查小于1的数的理由是
Now the reason I want to check for numbers below 1 is because
在斐波那契数列中 没有哪个斐波那契数的相关序列号
when it comes to Fibonacci sequence there is no Fibonacci number associated with
是负的 或是小于1的
numbers that are negative or any numbers that are less than one.
所以修正的方法 就是写一个if的条件语句
So how I’m going to fix that is by writing an if condition
如果n小于1
if n is lesser than one
然后我们要抛出一个新的非法异常
then what I want to is throw a new illegal exception.
[打字中]
[typing]
就写” no numbers”
Just write no no numbers.
[打字中]
[typing]
或是小于1的数是不允许的 我们就写 ” numbers below one not allowed”
Or just numbers below one not allowed let’s just write that numbers below one not allowed.
如果我在这里检查这个小于1的条件 那么我也必须改变这里的条件语句
And if I’m checking for this condition below one , I also have to change this conditional here.
它们冲突了
So you know conflict.
如果n=1或n=2
So if n is equal to one or n is equal to two
那就返回1
then I want to return 1.
所以这里 我具体检查了这几个数字
So from here in this condition, I’m checking for these numbers specifically.
现在我们输入一个小于1的数 比如-5
Now let’s just enter in a number below one, let’s just say negative 5.
保存并运行程序
Save now we run the application.
我们将会得到我们所期待的非法参数异常 小于1的数是不允许的
And we’ll get the illegal argument exception that we were expecting: numbers below one not allowed.
好 另一件我必须注意的事是
Alright so another thing that I had to take note of was
对于大数字 递归调用的次数也相当大
the number of recursive calls for large numbers.
它意味着 如果你输入一个非常巨大的数
So it pretty much means that if you enter in a very large number
你最后将会遇到一个栈溢出的异常 特别当函数是
you’re eventually going to get a stack overflow exception especially if the function is
使用递归调用
Well the function has a recursive call.
你就会遇到栈溢出 我们可以在代码中尝试一下
You’re going to get stack overflow, so let’s try this out in the code.
比如我们输入10000
So let’s just say up here we enter in ten thousand.
我们输入10000 保存并运行
We enter in ten thousand, we save it and we run the application.
程序在得出结果前需要花费一些时间
It’s going to take a while for this application to produce a result.
但由于递归调用的次数以指数方式增长的关系
But due to the fact that the number of recursive calls grows exponentially
最终它会导致一个栈溢出的异常
is going to eventually lead to a stack overflow exception.
现在我们要停止这个程序
So we’re going to stop this application.
我回到这里 向你们展示如何解决它
And I’m going back to this and show you how to resolve that.
我们回到之前的介绍
Let’s go back to the representation.
另一件事你必须注意的就是时间复杂度
And another thing you have to take note of is time complexity.
像我以前说的 如果有很多递归调用
So as I said before if there’s a number of recursive calls.
函数将以指数方式增长
The function is going to grow exponentially.
这有一个方法来解决它
And there is a way to resolve that so that
使函数呈线性时间复杂度
the function can have a time complexity, a linear time complexity.
现在我会试着向你们展示怎样做
So I’m going to try to show you how to do that now.
好 我们要做的第一件事
Alright, so the first thing we want to do.
我们要创建另一个函数
We want to create an another function.
我们把它命名为 fibNonRecursive
We’re going to name this function fibNumRecursive.
它同样将会接收一个整数
This is also going to take in an interger.
创建它的方法和第一个函数有点类似
And we want to set this up kind of similar to the way that we set up the first function.
我将加入一个条件语句
So I’m going to add a conditional statement
如果n小于等于2
if n is less than or equal to 2
然后我要返回 1
then I want to return 1.
下一步 我要做的是把三个变量相加
Next thing I want to do is add three variables
first second 和nth
first and second and nth.
现在这些变量将会用于计算下一个数字
Now these variables are going to be used in order to calculate the next number or
或基于给定数字的斐波那契数列
the number of Fibonacci sequence based on the given number.
我要把变量first设置为1
So I want to set this first variable equal to one
变量second设置为2
you want to set this second variable equal to two
我们要变量nth同样设置为2
and we want to set this nth variable equal to 2 as well.
现在我们要做的下一步是写一个for循环
Now what we want to do next is write a for loop.
在这个for循环里我们将输入 “int i =”
In this for loop we’re going to have int I equals.
我们要从3开始计算它
And we want to start this at three.
现在我们从3开始的一个理由是 因为我们已经处理了两个基础情况
Now a reason that we’re starting at three is because we’ve already handled the base case of two here.
这里我就只要从3开始 那就是我们将要完成的
So I just want to start off with three right here, that’s what we are going to be done
现在输入 “if (i <= n-1)" 接着 "i++"
Now if i is lesser than or equal to n minus 1 then i plus plus.
基本上 如果你在这里输入一个数字
So basically if they if you enter in a number here
它将会检查这个数字
it’s going to check this number.
是否在从3到所输入的数字的范围里
But within this range between 3 and the number that’s passed in.
第一步我要做的是
So the first thing I want to do is say or you know right
“nth = first + second”
nth equals first plus second
“first = second”
first equals second
“second = nth”
and second equals nth
然后 “return nth”
and I want to return nth.
现在这里正在做的
Now what’s going on here
这变量nth将会是所要计算的斐波那契数
This nth variable is going to be the variable that calculates the Fibonacci number.
所以你将会把first和second加起来
So you’re going to add the first and the second.
最终你就会得到你所要的结果
And that’s ultimately going to give you the number that you are looking for
这个变量nth将会基于迭代的次数
So this nth value is going to be based on the number of iterations
和当前的first和second的数值
as well as the current number of the first and the second number.
你很快就会知道这个fibNonRecursive函数
So you’ll also realize that this fibNonRecursive method
将能处理这儿的这个数 10000
is going to be able to handle this 10000 right here.
因为没有递归调用 而只有一个简单的循环
Because there are no recursive calls, there’s just a simple loop
这个循环根据输入的数字 迭代一定次数
which iterates a certain number of times based on the number that’s passed in
最终分解求得斐波那契数
in order to eventually split out the Fibonacci number.
如果我调用这个函数 并代入10000
So if I were to call this method and then pass in 10000
这就是得到的结果
here’s what we get.
第10000个斐波那契数
The Fibonacci number of 10000.
没有栈溢出 它的时间复杂度是O(n)
There’s no stack overflows, the time of complexity of this is n
它的时间复杂度比指数式的时间复杂度要好得多
which is the way better time complexity than exponential time complexity.
为了解释得更深入一点 实际上我要回到我的讲解那里
And to explain this a little bit further, I actually want to go back to the presentation that I have.
这里讲这个无递归的方法如何工作
So for this non recursive method this is how it works.
对于这个无递归的方法
So for for this non recursive method.
像我以前说的 first等于1 second等于2 nth等于2
As I said before, the first is going to be equal to 1, the second is going to be equal to 2, the nth is going to be equal to 2.
现在我要做的是从3开始
Now what I’m doing here is I’m starting at three.
因为我已经在第一个if条件语句里处理了2以上的情况
Because I’ve already handled that case for two up in that first if condition.
现在解释它的最好方式是使用例子
Now the best way to explain this is by using an example.
让我们来输入数字4
So let’s just say I pass into number 4.
由于我从3开始的关系 在我输入4时那只会有一个迭代
So due to the fact that I started at three, there’s only going to be one iteration since I’m passing in four.
在第一个迭代中 “nth = 1 + 2”
So in this first iteration, n the Nth variable is going to be set equal to one plus two
“first + second” 第1个加第2个 这里你可以看到 “nth = first + second”
first plus second, first plus second which you can see here nth equals first plus second.
现在first设置成等于2 second设置成等于nth 也就是3
Now the first is going to be set equal to two, and the second is going to be set equal to the nth which is 3.
Fib(4)将会等于nth
And fib of four is going to be equal to nth.
看 然后我们返回nth 它最终等于3
See and then we’re returning nth which will ultimately be three.
如果你输入另一个数 比如说你输入5
And if you enter in another number, let’s just say you enter in five
你必须通过它循环两次 而不只是一次
you would have to loop through this twice instead of only once.
如果你有任何问题 在下面的评论里留言
If you have any questions, leave them in the comments below.
如果你认为它有用 别忘了订阅和点赞
Don’t forget to subscribe and like the video if you found it helpful.
实际上我正在考虑创建一个对话 是特别针对编程面试题的 就像这一题一样
I am actually thinking about creating a chat that is specifically dedicated to coding interview questions just like this one.
如果你认为我应该那样做 在评论里留言 谢谢观看 下次再见
If you think I should do that, leave the comments below, see you next time, thanks for watching

发表评论

译制信息
视频概述

编程面试题:如何在斐波那契数列中寻找第n个数。分别使用递归和非递归方式,以及一些需要注意的问题。

听录译者

[B]倔强

翻译译者

B11101001

审核员

审核团O

视频来源

https://www.youtube.com/watch?v=3jWPmxEJUP0

相关推荐