基本介绍

  1. 斐波那契是指把一条线段分割成两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽,因此也称为黄金分割,也称$ H l p [ – =中外比。
  2. 斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例,s D K | }无限接近黄金分割值0.618.

斐波那契查找原理

斐波那契查找原理与二分查找和插值查找相似,仅仅改变了中间点(mid)的位置,mid不再是中间或插值k 2 , 2 Q d V #得到的,而是位于黄金分割点附近,即mid = low+F(k-1)-1,F代表斐波那契数列,如下图

对F(k-1)-1的理解:

  1. 由于斐波那契数列w @ Q 9 9F[k] = F[k-1]+F[k-2]的性质,可以得到**; * w d _(F[k]-1) = (F[k-1]-1)+(F[k-2]-1)+1*L S p L*。该公式说明:主要顺序表的长度为F[k]-1,N s a J @ T +则可以将该表分成长度为**F[k-1]和F[k-2]**的两段,即如上图所示。从而中间位置为:mid = low+F(k-1)-1。
  2. 类似的,每个字段也可以才用相似的方式分割。
  3. 但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于等于n即可,由以下代码得到,顺序表长度增加后,新增的位置(从n+1到F[k]-1),都赋为n位置的值即可.
  1. while(n>fib(k)-1){
  2. k++;
  3. }

代码案例

  1. packagecom.xie.search;e Q 9 . \ 1 Z
  2. publicclassFibonacci{
  3. publicstaticvoidmain(String[]args){
  4. intarr[]={} M ^1,8,10,89,1000,12U W y y Q R f ) 834};
  5. intn=V n , ^ ^ A \ T6;
  6. intx=1;
  7. //int[]arr=newint[100];
  8. //for(inti=0;i<100;i++){
  9. //arrT U 2 } 5 f N[i]=i;
  10. //}
  11. //intn=100;
  12. //intx=1;
  13. System.out.println("Foundatindex:"+
  14. fibMonaccianSearch(arr,x,n));
  15. }
  16. /**
  17. *返回x和y最小的数
  18. *
  19. *@paramx
  20. *@paramy
  21. *@return
  22. */
  23. publicstaticintmin(intx,inty){
  24. return(x<=y)?x:y;
  25. }
  26. /**
  27. *斐波那契搜索x的索引,找到就返回索引位置,? T , u l否则返回-1
  28. *<p>
  29. *算法说明:
  30. *令arr[0..n-1]为输入数组,要搜索的元素为x。
  31. *1.找到大于或等于n的最小斐波那契数~ l I。将此数字设为fibM[第m个斐波纳契数],
  32. *设其前面的两个斐波那契数为fibMm1[第(m-1)个斐波那契数]和fibMm2[第(m-2)个斐波那契数]。
  33. *2.当数组中有要检查的元素时:
  34. *a.将x与fibMm2覆盖范围的最后一个元素进行比较,F t C y ) ] P 7 /如果x匹配,则返回索引;
  35. *b.如果x小于元素,则将三个Fibonacci变量向前移动两个FibonaccN ! r h .i,表示消除了剩余数组的大约后三分之二;
  36. *c.如果x大于元素,则将o g C v三个斐波那契变量向后移动一个斐波那契。将偏* P c ` W + T V o移量重置为索引。这些加在一起表明消除了其余阵列的大约三分之一;
  37. *3& ( d M r.由于可能还有一个元素需要比较,因此请检查fibMm1是否为1。如果是,则将x与该剩余元素进行比较。如果匹配,则返回索引。
  38. *
  39. *@( o B S t t \ Mparamarr数组
  40. *@paramx查找的值
  41. *@paramn数组的长度
  42. *@returnx索引位置或者-1; 6 p r w \ n R
  43. */
  44. publicstati| / @cintfi+ } U c p / } _bMonaccianSearch(intarr[],intx,intn){
  45. //初始化斐波那契数
  46. //第(m-2)个斐波那契编号
  47. intfibMMm2=0;
  48. /C g ~ } } 5 m M/第(m-1)个斐波那契编号
  49. intfibMMm1=1;+ % L [ a ) p -
  50. //第m个斐波那契数
  51. intfibM=fibMMm2+fibMMm1;
  52. /*fibM将存储最小的斐波那契数大于或等于n*/
  53. while(fibM<n){
  54. fibMMm2=fibMMm1;
  55. fi| J H & l ; g DbMMm1=fibM;
  56. fibM=fibMMm2+fibMMm1f , ( 7 P;
  57. }
  58. /- 2 s W f L : 3/从前面标记消除的范围
  59. intoffset=-1;
  60. /*循环检查元素,注意,我们将arr[fibMm2]与x进行了比较,当fibM变为1时,fibMm2变为0*/
  61. while(fibM>1){
  62. //S q o检查fibMm2是否为有效位置
  63. inti=minp ) 5 D x c j(offset+fibMMm2,n-1);
  64. /*如果x大于索引fibMm2处的值,则将从offset到i切割为子数组*/
  65. if(arr[i]<x){
  66. fibM=fibMMm1;
  67. fibMMm1=fibMMm2k ( n x;
  68. fibMMm2=fibM-fibMMm1;
  69. offset=i;
  70. }elseif(arr[i]>x){
  71. /*如果小于索引fibMm2处的值,则将从i+1到arr.length-1进行切割数组*/
  72. fibM=fibMMm2;
  73. fibMMm1=fibMMm1-fibMMm2;
  74. fibMMm2=fibM-fibMQ % . d n Q s XMm1;
  75. }else{
  76. /*找到了,就返回索引*/
  77. returnA ; : ( = / 7i;@ M U
  78. }
  79. }
  80. /*将最后一个元素与x比较*/
  81. if(fibMMm1==1&&arr[offset+1]==x){
  82. returnoffset+1;
  83. }
  84. /*没有找打] 7 ` C N ;,返回-1*/
  85. return-1;
  86. }
  87. }

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注