斐波那契数列 多语言实践

斐波那契数列

如果没听说过 斐波那契数列，那一定听说过黄金分割，数列样式：

0，1，1，2，3，5，8，13…

规律:

num3 = num2 + num1
5 = 3 + 2; 
3 = 2 + 1;
2 = 1 + 1；
1 = 1 + 0；
1
0
...

理清了规律，就可以用代码实现

Kotlin

kotlin 提供了数据类型，就想试试用这个特征

fun main(arg: Array<String>) {
   val fib = fiboData(FibonacciData(2));
   println(fib.numOne) // 结果 1
}

// 定义一个数据类型 position 记录要返回的具体第几位的 斐波拉契数，每次递减
data class FibonacciData(var position: Int, val numOne: Int = 0, val numTwo: Int = 0);

fun fiboData(fib: FibonacciData = FibonacciData(0, 0, 0)): FibonacciData {
   if (fib.position <= 0) {
      return fib;
   }
   val newFibo = if (fib.numTwo <= 0) {
      FibonacciData(fib.position - 1, 0, 1)
   } else {
      FibonacciData(fib.position - 1, fib.numTwo, fib.numOne + fib.numTwo)
   }
   return fiboData(newFibo)
}

Rust

rust 语言第一时间想到了 元组 复合类型

fn main() {
    let num = fibonacci_num(10);
    println!("{}", num); // 输出 34
}

fn fibonacci_num(position: u32) -> u32 {
    let (_, num_one, _) = fibonacci_data((position, 0, 0));
    num_one
}

fn fibonacci_data(fibo: (u32, u32, u32)) -> (u32, u32, u32) {
    let (position, num_one, num_two) = fibo;
    if position <= 0 {
        return fibo;
    }
    if num_two <= 0 {
        fibonacci_data((position - 1, 0, 1))
    } else {
        fibonacci_data((position - 1, num_two, num_one + num_two))
    }
}

上面代码虽然实现了功能, 但是可读性极差, 一点都不自然, 仔细想了下, 这个地方应该使用结构体来组织代码:

fn main() {
    assert_eq!(34, Fibonacci::new(10).get_fibonacci_num());
}

struct Fibonacci {
    position: u32,
    num_one: u32,
    num_two: u32,
}

impl Fibonacci {
    fn new(position: u32) -> Fibonacci {
        Fibonacci {
            position,
            num_one: 0,
            num_two: 0,
        }
    }

    fn get_fibonacci_num(mut self) -> u32 {
        if self.position <= 0 {
            return self.num_one;
        }

        self.position -= 1;
        if self.num_two == 0 {
            self.num_two = 1;
            self.get_fibonacci_num()
        } else {
            let temp = self.num_one + self.num_two;
            self.num_one = self.num_two;
            self.num_two = temp;
            self.get_fibonacci_num()
        }
    }
}

php

想着减少代码量，用递归，虽然有点慢，且耗性能，但算是能跑

    /**
     * 获取指定位置的 斐波拉契数
     * @param int $position 位置
     * @return int
     */
    protected function fibonacci(int $position = 0): int
    {
        // 0,1,1,2 前面几位需要做下特殊处理
        if ($position <= 0) {
            return 0;
        } elseif ($position <= 3) {
            return 1;
        }
        // 效率低,$position 越大，就越慢,但代码量少。
        return $this->fibonacci($position - 1) + $this->fibonacci($position - 2);
    }

PHP 匿名函数实现起来更方便，所以重新写了一版,考虑到 int 存储数据大小有限，所以用 string 来存储，理论上不会出现数据溢出。

整型数 int 的字长和平台有关，尽管通常最大值是大约二十亿（32 位有符号）。64 位平台下的最大值通常是大约 9E18。

/**
     * Execute the console command.
     * [环境 php7.4 + laravel 8 artisan ]
     *
     */
    public function handle()
    {
        $this->line($this->fibonacci(1000));
    }

    /**
     * 斐波拉契数
     * @param int $position 定位置
     * @return string
     */
    public function fibonacci(int $position): string
    {
        $fn = function(int $position, string $numOne = '0', string $numTwo = '0') use (&$fn) {
            if ($position <= 0) {
                return [$position, $numOne, $numTwo];
            }
            $position -= 1;
            if ((int)$numTwo <= 0) {
                return $fn($position, "0", "1");
            }
            return $fn($position, $numTwo, $this->numStrAdd($numTwo, $numOne));
        };
        return $fn($position)[1] ?? '0';
    }

    /**
     * 数值字符串相加
     * @param string $numOne 第一个数
     * @param string $numTwo 第二个数
     * @return string
     */
    public function numStrAdd(string $numOne, string $numTwo): string
    {
        $numOneArr = array_reverse((array)$numOne);
        $numTwoArr = array_reverse((array)$numTwo);
        if (count($numOneArr) < count($numTwoArr)) {
            $tempArr = $numOneArr;
            $numOneArr = $numTwoArr;
            $numTwoArr = $tempArr;
            unset($tempArr);
        }

        $newNumArr = [];
        $tempNum = 0;
        foreach ($numOneArr as $k => $v) {
            $needSumNumber = $numTwoArr[$k] ?? 0;
            $v += $needSumNumber;
            $v += $tempNum;
            $tempNum = 0;
            $v = (array)(string)$v;

            $needUnSiftNum = 0;
            if (count($v) > 1) {
                $tempNum = $v[0];
                $needUnSiftNum = $v[1];
            } else {
                $needUnSiftNum = $v[0];
            }
            array_unshift($newNumArr, $needUnSiftNum);
        }
        if ($tempNum > 0) {
            array_unshift($newNumArr, $tempNum);
        }
        return implode('',$newNumArr);
    }

本作品采用《CC 协议》，转载必须注明作者和本文链接