判断子序列

  1. /// Fibonacci via Dynamic Programming
  2. /// fibonacci(n) returns the nth fibonacci number
  3. /// This function uses the definition of Fibonacci where:
  4. /// F(0) = F(1) = 1 and F(n+1) = F(n) + F(n-1) for n>0
  5. ///
  6. /// Warning: This will overflow the 128-bit unsigned integer at n=186
  7. pub fn fibonacci(n: u32) -> u128 {
  8. // Use a and b to store the previous two values in the sequence
  9. let mut a = 0;
  10. let mut b = 1;
  11. for _i in 0..n {
  12. // As we iterate through, move b's value into a and the new computed
  13. // value into b.
  14. let c = a + b;
  15. a = b;
  16. b = c;
  17. }
  18. b
  19. }
  20. /// fibonacci(n) returns the nth fibonacci number
  21. /// This function uses the definition of Fibonacci where:
  22. /// F(0) = F(1) = 1 and F(n+1) = F(n) + F(n-1) for n>0
  23. ///
  24. /// Warning: This will overflow the 128-bit unsigned integer at n=186
  25. pub fn recursive_fibonacci(n: u32) -> u128 {
  26. // Call the actual tail recursive implementation, with the extra
  27. // arguments set up.
  28. _recursive_fibonacci(n, 0, 1)
  29. }
  30. fn _recursive_fibonacci(n: u32, previous: u128, current: u128) -> u128 {
  31. if n == 0 {
  32. current
  33. } else {
  34. _recursive_fibonacci(n - 1, current, current + previous)
  35. }
  36. }
  37. /// classical_fibonacci(n) returns the nth fibonacci number
  38. /// This function uses the definition of Fibonacci where:
  39. /// F(0) = 0, F(1) = 1 and F(n+1) = F(n) + F(n-1) for n>0
  40. ///
  41. /// Warning: This will overflow the 128-bit unsigned integer at n=186
  42. pub fn classical_fibonacci(n: u32) -> u128 {
  43. match n {
  44. 0 => 0,
  45. 1 => 1,
  46. _ => {
  47. let k = n / 2;
  48. let f1 = classical_fibonacci(k);
  49. let f2 = classical_fibonacci(k - 1);
  50. match n % 4 {
  51. 0 | 2 => f1 * (f1 + 2 * f2),
  52. 1 => (2 * f1 + f2) * (2 * f1 - f2) + 2,
  53. _ => (2 * f1 + f2) * (2 * f1 - f2) - 2,
  54. }
  55. }
  56. }
  57. }
  58. /// logarithmic_fibonacci(n) returns the nth fibonacci number
  59. /// This function uses the definition of Fibonacci where:
  60. /// F(0) = 0, F(1) = 1 and F(n+1) = F(n) + F(n-1) for n>0
  61. ///
  62. /// Warning: This will overflow the 128-bit unsigned integer at n=186
  63. pub fn logarithmic_fibonacci(n: u32) -> u128 {
  64. // if it is the max value before overflow, use n-1 then get the second
  65. // value in the tuple
  66. if n == 186 {
  67. let (_, second) = _logarithmic_fibonacci(185);
  68. second
  69. } else {
  70. let (first, _) = _logarithmic_fibonacci(n);
  71. first
  72. }
  73. }
  74. fn _logarithmic_fibonacci(n: u32) -> (u128, u128) {
  75. match n {
  76. 0 => (0, 1),
  77. _ => {
  78. let (current, next) = _logarithmic_fibonacci(n / 2);
  79. let c = current * (next * 2 - current);
  80. let d = current * current + next * next;
  81. match n % 2 {
  82. 0 => (c, d),
  83. _ => (d, c + d),
  84. }
  85. }
  86. }
  87. }
  88. #[cfg(test)]
  89. mod tests {
  90. use super::classical_fibonacci;
  91. use super::fibonacci;
  92. use super::logarithmic_fibonacci;
  93. use super::recursive_fibonacci;
  94. #[test]
  95. fn test_fibonacci() {
  96. assert_eq!(fibonacci(0), 1);
  97. assert_eq!(fibonacci(1), 1);
  98. assert_eq!(fibonacci(2), 2);
  99. assert_eq!(fibonacci(3), 3);
  100. assert_eq!(fibonacci(4), 5);
  101. assert_eq!(fibonacci(5), 8);
  102. assert_eq!(fibonacci(10), 89);
  103. assert_eq!(fibonacci(20), 10946);
  104. assert_eq!(fibonacci(100), 573147844013817084101);
  105. assert_eq!(fibonacci(184), 205697230343233228174223751303346572685);
  106. }
  107. #[test]
  108. fn test_recursive_fibonacci() {
  109. assert_eq!(recursive_fibonacci(0), 1);
  110. assert_eq!(recursive_fibonacci(1), 1);
  111. assert_eq!(recursive_fibonacci(2), 2);
  112. assert_eq!(recursive_fibonacci(3), 3);
  113. assert_eq!(recursive_fibonacci(4), 5);
  114. assert_eq!(recursive_fibonacci(5), 8);
  115. assert_eq!(recursive_fibonacci(10), 89);
  116. assert_eq!(recursive_fibonacci(20), 10946);
  117. assert_eq!(recursive_fibonacci(100), 573147844013817084101);
  118. assert_eq!(
  119. recursive_fibonacci(184),
  120. 205697230343233228174223751303346572685
  121. );
  122. }
  123. #[test]
  124. fn test_classical_fibonacci() {
  125. assert_eq!(classical_fibonacci(0), 0);
  126. assert_eq!(classical_fibonacci(1), 1);
  127. assert_eq!(classical_fibonacci(2), 1);
  128. assert_eq!(classical_fibonacci(3), 2);
  129. assert_eq!(classical_fibonacci(4), 3);
  130. assert_eq!(classical_fibonacci(5), 5);
  131. assert_eq!(classical_fibonacci(10), 55);
  132. assert_eq!(classical_fibonacci(20), 6765);
  133. assert_eq!(classical_fibonacci(21), 10946);
  134. assert_eq!(classical_fibonacci(100), 354224848179261915075);
  135. assert_eq!(
  136. classical_fibonacci(184),
  137. 127127879743834334146972278486287885163
  138. );
  139. }
  140. #[test]
  141. fn test_logarithmic_fibonacci() {
  142. assert_eq!(logarithmic_fibonacci(0), 0);
  143. assert_eq!(logarithmic_fibonacci(1), 1);
  144. assert_eq!(logarithmic_fibonacci(2), 1);
  145. assert_eq!(logarithmic_fibonacci(3), 2);
  146. assert_eq!(logarithmic_fibonacci(4), 3);
  147. assert_eq!(logarithmic_fibonacci(5), 5);
  148. assert_eq!(logarithmic_fibonacci(10), 55);
  149. assert_eq!(logarithmic_fibonacci(20), 6765);
  150. assert_eq!(logarithmic_fibonacci(21), 10946);
  151. assert_eq!(logarithmic_fibonacci(100), 354224848179261915075);
  152. assert_eq!(
  153. logarithmic_fibonacci(184),
  154. 127127879743834334146972278486287885163
  155. );
  156. }
  157. #[test]
  158. /// Check that the itterative and recursive fibonacci
  159. /// produce the same value. Both are combinatorial ( F(0) = F(1) = 1 )
  160. fn test_iterative_and_recursive_equivalence() {
  161. assert_eq!(fibonacci(0), recursive_fibonacci(0));
  162. assert_eq!(fibonacci(1), recursive_fibonacci(1));
  163. assert_eq!(fibonacci(2), recursive_fibonacci(2));
  164. assert_eq!(fibonacci(3), recursive_fibonacci(3));
  165. assert_eq!(fibonacci(4), recursive_fibonacci(4));
  166. assert_eq!(fibonacci(5), recursive_fibonacci(5));
  167. assert_eq!(fibonacci(10), recursive_fibonacci(10));
  168. assert_eq!(fibonacci(20), recursive_fibonacci(20));
  169. assert_eq!(fibonacci(100), recursive_fibonacci(100));
  170. assert_eq!(fibonacci(184), recursive_fibonacci(184));
  171. }
  172. #[test]
  173. /// Check that classical and combinatorial fibonacci produce the
  174. /// same value when 'n' differs by 1.
  175. /// classical fibonacci: ( F(0) = 0, F(1) = 1 )
  176. /// combinatorial fibonacci: ( F(0) = F(1) = 1 )
  177. fn test_classical_and_combinatorial_are_off_by_one() {
  178. assert_eq!(classical_fibonacci(1), fibonacci(0));
  179. assert_eq!(classical_fibonacci(2), fibonacci(1));
  180. assert_eq!(classical_fibonacci(3), fibonacci(2));
  181. assert_eq!(classical_fibonacci(4), fibonacci(3));
  182. assert_eq!(classical_fibonacci(5), fibonacci(4));
  183. assert_eq!(classical_fibonacci(6), fibonacci(5));
  184. assert_eq!(classical_fibonacci(11), fibonacci(10));
  185. assert_eq!(classical_fibonacci(20), fibonacci(19));
  186. assert_eq!(classical_fibonacci(21), fibonacci(20));
  187. assert_eq!(classical_fibonacci(101), fibonacci(100));
  188. assert_eq!(classical_fibonacci(185), fibonacci(184));
  189. }
  190. }