00:00
各位,我们现在呢,来写一个斐波纳器的应用案例,我们还以前面这个数组为例来给大家讲好不好?就说现在有一个有序数组,注意非波拉器呢,仍然要满足它是个有序的,我们才可以用菲波拉器,那么我们输一个数,看看该数是否存在,并求出下标,如果没有呢,我们就提示没有啊,那这样我们就呃返回下标啊,如果没有,我们可以提示这句话。或者说直接返回一个负一都可以,那同学们思路有了,我们现在用代码将其实验打开我们eclipse,现在呢,我们在search这个包包下面新建一个类,我们叫做斐波纳器查找。这个应该怎么讲,斐波那?气是不是这样写的啊,菲波纳气。Search ch飞波飞波那算法。非拉去算法,那现在呢,我们把这个主方法勾上。好的。把这个删掉,那现在首先我们把这个数组写出来对不对。
01:04
等于什么呢?是不是就用我们这里幻灯片提供的这个数列就可以了。他看清楚了啊,同学们。好呃,有了这个东西过后呢,我们紧接着写它的一个方法,因为注意啊,因为后边后面我们这个公式,大家有没有发现,我们这刚才分析的时候,这个公式里面会用到我们斐波纳气的数列,因此呢,我先我先要构建一个非波拉器数列才可以。对不对,需要什么,需要使用到非非波纳器数列。数列,是不是我要有这个菲布拉数列。因此,因此我们需要先。获取到,获取到一个菲波拉希数列。获取到非波拉契数列。好,所以说我先呢写给写一个方法,我们把它全屏一下。
02:04
我先写个方法,这个方法呢,叫public static int,菲布拉去苏联返回一个数组嘛,对不对,不就叫菲波拉。那这个怎么得到一个斐波纳契数列呢?我们这里使用一个非递归的方法,大家知道斐波那契数列可以用递归得到,也可以用非递归,我们这儿呢,用非递归的方式。方式得到一个非波纳器数列。好了,大家明白我的意思了,现在开始写代码,首先呢,我们先创建一个斐波拉奇数列。好,呃,那斐波拉我就写一个F6,一个int,那斐波拉些数列有多大呢?我们可以事先先定一个变量。我们先定一个变量,表示一个自己将来需要用到的变量就可以了,比如说我定一个,呃。
03:00
A public static int什么呢?Markx size,好吧,我们先写这么一个变量,Mark size。我初始化我一个20吧。好,然后呢,我在这里就直接放进去。那我怎么得到它呢?非常的简单。我先根据。前面写的如果下标为零,它是一,这个没问题吧,如果下标为一,是不是它也等于一啊同学们,那下面我们就用for循环搞定就可以了,从I等于二,也就下边等于二的地方开始呢。到我们马赛。然后我挨家家。然后我I加加好,然后Fi等于多少呢?Fi就应该等于Fi减去一个一,再加上对I减二。同学们,最后把这个菲波拉器返回就可以了。同学们,这个代码应该很好理解吧?这个代码应该很好理解,就是得到一个大小为20个。
04:04
20个元素的斐波纳器数列,那这个写完了过后呢,下面我们就可以开始写斐波纳器查找算法了,那么编写什么呢?编写斐波纳器。查找算法。好,大家跟上我的思路。那首先呢,我们写public sta怎么样?Int,因为刚才我们讲过,我们得到了就返回一个对应的下标,如果没有得到,我们返回一个负一,是这意思吧,然后写啊飞波10RCH。那现在呢,首先你把数组传给我,比如说A,然后呢,你要找的这个值K给我。我做一个说明。我做一个说明,首先这个A呢,就是我们的数组,这个很好理解,K就是我们需要查找的关键关键码,我们需要查找找的啊,查找的关键码。
05:01
关键码字,关键码字。其实就是我们的那个值啊,就是你要找哪个数,说白了就是那返回值就是嗯就是呃,返回对应下标返回对应。对应的下标。对不对,如果没有,如果没有就返回负一。好,这是我们的一个确定,那下面就开始写了,首先呢,我们先让这个no写成一个零,注意啊,现在我想使用的是非递归的方法来写,所以说大家注意听啊,我现在用的是非递归,我们现在使用什么呢?使用非递归。非递归的方式编写。编写这个算法。那首先我们先定一个no no,那么我们再定一个hi,因为你这个数组的,诶这个写错了,数组的刚开始是从哪找的,你得告诉我是不是一个no,一个hi,也就是我们前面写的left和right,那hi是多少呢?显示NS减一是不是你最高的位应该是一个,最低位是零。
06:08
那现在呢?我们再定一个K等于零,这个K是干什么的呢?我先做一个注释,这个表示表示斐波那契数列。说诶斐波纳器分割。分割数值,数值的那个下标。其实我就是要找这个嘛,因为我不知道将来是在哪个地方,所以说我先确定一个K。这个K是指的我们将来要取的那个那个斐波纳器分割数值对应的下标啊,这点大家清楚,也就是谁呢。哎,说的再急,直接就他。啊,就是它,因为我要知道它,我才能从斐波拉西数列里面拿到这个值,然后再进而得到密的,明白我意思吧,也就是我关键要求的这个K。
07:00
其实这个K是我们最关键的地方,明白吗?因为no很好拿,减一这个也没什么,关键是要拿到F,而这个这个K,而我们这个F呢,其实就是这个数列嘛,我通过一个方法就可以返回这个斐波拉器数列,关键是K看清楚了没有,所以这个K呢,表示斐波拉器分割数值的下标。每次都会变化的,然后呢,首先我们大把密初始化为零。这个就是待会儿我们要。得到的这个东西我先初始化为零,要定义一个啊,就是存放什么呢?存放我们的,存放我们的幂的值。这个很好理解。那现在呢?我们上来过后二话不说,我们先把斐波拉奇数列拿到。因为后面反正要用这个非波拉数列,怎么得到呢?其实就是调这个方法就可以拿到了。是这个意思吧?同学们,我写个注释啊,这是干什么呢?获取到非波拉契数列很好理解。
08:00
很好理解,好,现在拿到这个供货过后呢,我们现在要做件事情到获取到现在获取到什么呢?获取到这个课K,就是现在我们要拿这个K了,获取到斐波纳器分割数值的下标,怎么获取呢?刚才我其实已经讲过了,因为你在这个地方做的时候,不一定N刚好等于它,因此呢,你要用国外循环来处理。因为它有可能不足,所以说你这个地方要买,要写这么一句,这个这么一句话啊,大家看能不能减,如果这个high它大于了FK。减掉一个一,因为我刚开始呢,这个K是零,是不是是零,因此我只要这个条件满足,说明我找到没有,说明没有找到,所以加。就这个条件版说明我还没有找到这个K,只有这个条件不成立,也就是说氦小于等于FK减一时,我们才找到了这个下标。理解吧。好,这个有点不好理解是不是啊,这个大家再想想,拿到这个值过后呢,现在呢,我们要去。
09:06
做件事情,做件什么事情呢?同学们,就是你这个FKFK对应的那个值不一定。就是说FK这个对应的值呢。他不一定跟你这个数组的大小相同。大家理解我的意思吧,就有可能比你大。对不对,所以说这样子我们要开始做一个拷贝工作,因为我说一下啊,因为FK注意听FK这个值可能对不对,可能大于。大于什么呢?大于我们这个数组的长度,就是哪个数组呢?就是我们这个I的。A的这个程度。因此呢,因此因此我们需要干什么呢?使用使用一个一一个这个R类。
10:01
二这个类干什么呢?我们构造,构造一个新的新的这个数组,并指向。B指向A。啊,并指向。并指向谁呢?指向这个A,好,这句话呢,我们就开始可以写了,这样写啊,同学们,呃,这写上这个东西大家看能不能看懂,等于。AL。意思点什么呢?Copy of。Copy,那现在元素组是A,然后长度是多少呢?长度就是我们求的这个K。大家看到没有这个方法我再说一遍啊,如果我这个A小FK大,那么返回到这个就会temp呢,就会用零补充。零补齐,如果不足的部分啊,不足的不足的部分会。会使用零填充。
11:02
对吧,会使用零填充。好的,那他使用零填充,咱们怎么玩呢这个事儿。Very的easy,那就这样做了。我拿到这个事情,下面我们就干什么呢,对。对,这个新的。他初始的时候会用零填充对不对,但是呢,我们我们真实的不能用零,我们需要干什么呢?把这个新构建的数组进行。用用最后那个数来进行填充,就是用a.hi来填充,明明白我的意思吧,这个有点不好理解,注意听啊,实际上呢,我们还要做一个处理,就是实际上需要需要使用哪个呢?就是A。数组的最后,最后的数填充,填充什么呢?Temp。因为你后面可能会对这个数进行比较。好,现在呢,我们写一个for循环,For循环int I等于high。
12:06
家一。是不是还加一,如果I它小于了吞点。在这种情况下,我们就哀家家。二加加情况怎么做呢?各位同学,那就是temp I等于a hi。啊,现在不好测试,也就是说你可以这样理解,打个比方啊,我举个例子。比如说你你这个数组是长的这个样子的。先前你拷贝给这个temp,我举例。举例,比如说你你这个数这样子的,但是因为这个FK呢,有可能大,如果有可能大的话,你这个temp拷贝完了过后,这个temp是不是长这个样子的,假如假如大大的话,后面假设有假设有两个零啊,我不知道有没有几个零,我不知道假设三个零吧。是不是就是FK它的这个,它的这个值大于A的这个长度,那么你拷拷贝过来这个程度变这样子了,那变这样子不是我要的,我希望它变成什么样子呢?我希望它变成这样子。
13:11
变成用后面这个是1234来填充的。12346题,就这意思,这个工作就在做这个事情。这个工作就在做这个事情。好,那有了这个东西过后呢,下面我们就呃这个填充事情也完成了,好下面我们可以使用了什么呢?使用这个Y循环,因为分割点已经找到了Y循环来来循环的处理,循环处理查找。找到什么呢?找到我们的。这个这个数。就是这个K循环啊,循环退出的条件显然是我们这个no,如果no尔小于等于汉就不停的去做。这个跟原先是很类似的是吧,只要这个条件满足就可以一直找。
14:00
啊,只要。这个条件满足就可以找。那怎么找呢?同学们,是不是我们现在终于可以拿到这个东西了?我们是不是辛辛苦苦干这件事情就想得到它呀?这个密就可以拿到了。那显然这个地方我们应该写成F,因为上面我定的是F嘛,对不对,这个很好理解。拿到了。好,这个F在哪呢,我看看啊。他说没有定义过,是不是没有定义过FK,哦哦,对,这不是这个问题,是粘过来我们粘错了对吧,应该是这样才对,这样才对,这个很好理解吧。好的,那这个。把这个格式化一下。把这个格式化一下啊。那这个拿到以后,是不是相当于我们中间这个下标就拿到了,现在就可以比较了,怎么比较呢?各位同学请看啊,如果说如果说我们这个K它小于了ten密,说明什么问题?
15:04
这个说明什么问题?这个条件一旦成立,说明说明我们应该应该继续向。像什么呢?像这个数组的前部分前面查找向数组的前面。全面查找。对不对,也就是说我们所说的左边。左边。左边哎,写错了啊左边。左边查找。是这意思吧,同学们,那现在向左边插找,你应该怎么写呢?那就应该是把这个高位改成密的减一,这个是不是以前也是很类似的。然后呢,干什么,K减减。因为为什么要K减减呢?好,这个地方我要强调一下,这个K减减不好理解,确实不好理解,我要做一点做事,为什么是K减减,为什么为什是。
16:03
注意听啊,为什么是K减减。这个有点不好理解,我说一下啊,来同学们呃,我做几点说明,大家一下就明白为什么是K减减了第一点。第一点就是大家知道全部元素,它是不是等于前面的元素。前面的元素加上我们后后部的后后面的后边的元素,这个大家应该是理解的。对不对,全部一个前面后面加上,那么而而我们的FK是怎么得到呢?FK它是等于FK减一。再加上FK减二拿到的是这样子的吧,同学们好,现在呢,我们看看因为因为什么呢,因为前面。我直接写啊,因为前面呢,诶前面干什么呀,有F。
17:01
K减一个元素。因为你进行分割嘛,是不是FK减一个元素,所以。所以什么呢?所以我们可以继续拆分,因为你你你你你现在不是向前向左左边去找,也说前面去找吗?前面有FK减一个元素,因为你你原先分割点在这,那你前面是不是就就是这个值对应的呀,那前面的元素是不是这么多个,那你就所以可以继续什么呢?可以继续拆分。拆分,你可以继续拆分成什么呢?同学们,是不是你可以继续拆分成这样一个东西,就是K减。一。等于FK减二。找加上FK减三,这样得到的。是是不是这样子的,是不是这样猜的,那集什么呢?即这样一个意思,即在。
18:01
注意听啊,其在F。F。K减一。最近这句话这个有点暴力,FK减K减一。FK减一到前部。前前面继续查找。对不对,继续继续继续查找,那如果是在FK切减前面查找,所以说就是K减K减1K减减了。是不是K减减,因为你你往前面去一位,咱们就K减减,呃,那如果说的再再直接一点就是什么呢?即下次。下次我们循环的时候呢,这个密的就应该等于什么呢?就应该等于F。K减一,再减一,再再减一。这样一个逻辑。因为你K减一了,原先这个你K你K回来过,他再去,他下一步循环的时候,因为你这个不会再上去了吗?在下一步就是因为你这K减一,就K减一再减一,好这个幂的位置就是正确的。
19:05
这样才行的明白好else。第二是如果这个条件不满足是什么呢?是这样一个条件,如果我们的K。好K,它干什么呢?它大于了temp。密这个条件成立,这个条件成立说明我们应该干什么呢?诶说明我们应该继续向数组的后面查找,是不是这个意思啊。后面就是我们所说的右边。后面。这个后边查找,也就是我们所说的右边查找。能理解吗?那如果是你向右边查找,大家想你应该怎么做呢,是不是把no。把no改成我们的密的干什么?加一氦不变?Hi不变,Hi不变的话,这个时候K要怎么处理呢?K要等于。K要等于减二。
20:00
好,这个为什么是又是减二,前面是K减减,现在是K减二,为什么呢?好,我们还要做说明,为什么我做一个说明啊,为什么是K减二呢。为什么是K减二呢?好,这个呢,我要给大家解释一下,那我还是做几点说明,第一点地点说明,第一点说明呢,仍然跟前面一样,乙的全部元素仍然是。前面加后面这个很好理解对吧,那大家想想,如果你这样做了过后,你下一次你你现在是你现在现在每次是不是咱们是K减一加上FK减二这个条件是不是也是。呃,也是一样的呀,第三一个地方大家看第三个地方,因为因为后边后面我们还有多少个元素,后面我们有F,注意看这一个是K减二个元素。
21:03
因为你你FK是中是这个黄金分割点,那你后边有的元素是不是有这么多个FK减二个元素是不是。你有FK减二个元素,所以我们也可以继续拆分,所以我们可以继续拆分,那么这个时候继续拆分会拆分成什么样子呢?同学们。大家想想是不是应该是K减三,后面这个是K减四了呀,这个能理解吗?你看到没有,那你你看你这个相差的位置是不是相差二个呀,相差二个好,因此同学们看到,诶,因为。你你像这样拆分过后呢,即我们的我们集什么呢?即就是在哪里呢?在FK减二。FK减二这个的前面,前面可以继续。啊进行查找,那这个时候呢,K显然就应该是减二的一个操作了,而不能是减一。
22:04
明白吧,也就是说,也就也就是说,即什么呢?即下次循环我们这个密的应该等于多少了呢?各位同学,应该等于的是F。K减一再减二是不是这个意思啊,那当然还要减个一,因为米是这样算出来的嘛。密是这样算出来是不是啊,是这样的一个逻辑,这样的一个逻辑,好,那既然如这个K减二,我们就没有问题了,紧接着我们再来看S,好这个时候就意味着我们找到了。找到了,但是找到了过后,你到底是返回哪个值是要需要注意的,到底是返回幂的值还是hi这个值呢?需要注意,这个时候要需要确定,需要确定干什么呢?返回的是哪个下标。明白,那就我写个条件,如果说me小于等于hi,说明我们这个时候返回的下标应当是me。
23:06
应当是密,因为小返回小的嘛,否则的话我们应该返回氦。也就返回小一点的,明白这意思吧,好的,嗨。H。HIGE。好,这就是我们这个代码就写完了,写完了,那现在呢,我们可以来测试一把,看看我们这个代码到底写的OK还是不OK,我们再检查一下代码。OK啊,我们再检查一下代码。好,最后还是句号,如果整个Y循环,整个Y循环结束了,过后没有返回,是不是我们应该还要返回一个负一啊?这个地方就代表说在整个这个Y循环里面,没有遇到这个语句,说明你没有找到,就返回,返回一个负一代码就写完了,好,现在呢,我们来玩一把,我们来玩一把,来同学们看一下system,我直接上代码了啊,那就是飞拉。
24:01
查找把数组传进去,我们查找。比如说查找一。插到一,现在应该返回的是零运行之,我们给同学们运行吧。我们看反馈的事情呢,0VERY的good,诶就是说这个下标我们找出来啊。就是index等于加。运行一返回零是正确的,没有问题,我们再找这个最边缘的1234看一下同学们。它返回几呢?返回五也是正确的,我们再找一个中间的值,比如说是89,我们看一下对吗?应该是返回三正确的,我们再找一个不存在的189运行值,发现负一正确,好代码是没有任何问题。代码没有任何问题,好了,那关于斐波纳器呢,我们就说到这儿,大家知道啊,斐波纳器呢,有点不好理解,它的主要的目的,它是借助于我们这个菲波纳奇数列找到这个分割点。啊,所以说他在这个过程中呢,他需要先把这个数组扩成。
25:02
能够找到分割点的这么一个数列。然后才开始做,你看这个逻辑是吧,上来过后他二话不说,他先根据你这个实际的情况,把这个数组呢进行了一个。好,进行了一个这个处理啊,诶这个我这写错了啊,并指向temp temp就说后面我们实实际上是整个这个查找过程呢,是在哪里呢?是在这个temp数组里边去找的,看到没有,一直是在数组里面比较。明白这意思吧,好的,为什么要,为什么要去做这个工作呢?就是因为配合,就是为了让他能够和我们菲波拉契数列配合,就是这个目的,这点有点相对来说不是很好理解。就这地方稍微有点难度,稍微有点难度好了,那同学们嗯嗯,要是看不懂,你把这个代码呢,Debug一下,一点一点看就行了,比如说我我给大家d bug一下,你们看是不是这样子的啊,来玩一把。
26:02
来玩一把啊,我们简单的给同学们debug一下。A。走一个,看啊看,老师给简单bug一下,走走走走,好同学们看,现在呢,我们已然拿到飞波大气了,这个数列呢,一共有20个。是不是好,我们紧接着继续往下走,好往下走这个这个K呢,亥现在是几还是五。好,这个K。处理了,看到没有,再处理再处理。再处理这个K由零变到几了呢?我们退出来它应该变到了五。变到五了,变到五过后,大家知道如果K等于五的话,这个值其实是几呢?一共有八个数据,也就是说我们这个数组需要有八个才可以去使用我们非波拉器,那它怎么办的呢?他先拷贝过来,拷贝过来我讲过你原先只有你A数组,一共有几个数组,呃,有几个数,一共有六个数,但是人家要八个数,你不够怎么办呢?
27:04
这个时候temp应该是后面有两个零的,有两个零不行呢,怎么办呢?我们怎么办呢?我们把最后这个数给它填充进去,填充完了过后,那我这写错了啊,应该。我这是估算的,刚才。那这样的话,他把1234。补到天,把这两个零给他干掉了好,是不是样子走一下,一次两次出来好,出来你看现在他不是变成这个德行了,跟我说的是一样的吧,然后在这个基础上一步一步的进行。变换这个密的这个值,密的呢,始终是按我们黄金就是按照斐波纳气的数列来获取的啊,不管是向左还是要用始终保持黄金分割点这样来玩的,明明白这意思吧。好,呃,这个呢,应该同学们再再想一想,应该能想明白啊,也不是特别难,好了,同学们,我把飞波纳气的这个代码的整,呃代码的一个思路给他整理,整理完毕了,把这个说完了,啊说完了那我们截取一段视频。
我来说两句