Числа Фибоначчи

Материал из SoftTimeINFO
Перейти к: навигация, поиск

В компьютерных вычислениях и дискретной математике числам Фибоначчи традиционно уделяется большое внимание. Задача больше академическая, из теории чисел, и в практическом программировании используется не часто, главным образом для создания менеджеров памяти и оптимизационном поиске. Кратко — это целые ряд целых чисел, в котором число равно сумме двух предыдущих чисел. Числа нарастают в соответствии с золотым сечением, поэтому на практике в большинстве случаев проще воспользоваться правилом золотого сечения, чем непосредственно числами Фибоначчи.

Содержание

[править] История

Первые работы, посвященные числам Фибоначчи, восходят к индийским и арабским источникам. Однако свое современное название числа получили благодаря европейскому математику. В Западной цивилизации первое упоминание о них появляется в работе 1202 года «Liber abacci» (Книга об Аббаке) итальянского математика Леонарда, известного под именем Fibocacci, сокращение от filius Bonacci (сын Боначчи).

«Liber abacci» представлял исчерпывающее изложение почти по всем раздела арифметики и алгебры, доступных на то время и внес значительный вклад в развитие математики в Западной Европе. В частности, именно по этой книге европейцы познакомились с индусскими («арабскими») цифрами. Книга представляет собой сборник практических задач, числа фибоначчи вводились на примере задачи о подсчете прироска популяции кроликов.

Сколько пар кроликов в один год от одной пары рождается?
Некто поместил пару кроликов в неком месте, огороженном со всех сторон стеной, чтобы узнать, сколько пар кроликов родится при этом в течение года, если природа кроликов такова, что через месяц пара кроликов производит на свет другую пару, а рождаются кролики со второго месяца после своего рождения. Так как первая пара в первом месяце дает потомство, удвой, и в этом месяце окажутся 2 пары; из них одна пара, а именно первая, рождает и в следующем месяце, так что во втором месяце оказывается 3 пары; из них в следующем месяце 2 пару будут давать потомство, так что в третьем месяце родятся еще 2 пары кроликов, и число пар кроликов в этом месяце достигнет 5; из них в этом же месяце будут давать потомство 3 пары, и число пар кроликов в четвертом месяце достигнет 8; из них 5 пар произведут другие 5 пар, которые сложенные с 8 парами, дадут в пятом месяце 13 пар; из них 5 пар, рожденных в этом месяце, не дадют в этом же месяце потомства, а остальные 8 пар рождаются, так что в шестом месяце оказывается 21 пара; сложенные с 13 парами, которые родятся в седьмом месяце, они дают 34 пары; в восьмом месяце, они дают в этом месяце 55 пар; сложенные с 34 парами, рожденными в девятом месяце, они дают в этом месяце 144 пары; снова сложенные с 89 парами, которые рождаются в одиннадцатом месяце, они дают в этом месяце 233 пары; сложенные вновь с 144 парами, рожденными в последнем месяце, они дают 344 пар; столько пар пар произвела первая пара в данном месте к концу одного года. Действительно, на этих полях ты можешь увидеть, как мы это делаем; именно, мы складываем первое число со вторым, т.е. 1 и 2; и второе с третьим; и третье с четвертым; и четвертое с пятым; и так одно за другим, пока не сложим десятое с одиннадцатым, т.е. 144 с 233; и мы получим общее число упомянутых кроликов, т.е. 377; и так можно делать по порядку до бесконечного числа месяцев.
Пара Первый Второй Третий Четвертый Пятый Шестой Седьмой Восьмой Девятый Десятый Одиннадцатый Двенадцатый
1 2 3 5 8 13 21 34 55 89 144 233 377

[править] Математические свойства

В современной трактовке последовательность чисел Фибоначчи определяется как рекуррентное соотношение, в котором каждый член равен сумме двух предыдущих членов.

u_{1}, u_{2}, ..., u_{n}
u_{n} = u_{n - 1} + u_{n - 2}, n > 2
u_{1} = 1, u_{2} = 1
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

Данная последовательность имеет множество интересных математических свойств (например, числа Фибоначчи можно вычислять по восходящим диагоналям треугольника Паскаля). Однако, в данной статье нас будет интересовать не столько математические свойства последовательности, сколько возможность вычисления произвольного числа последовательности. На практике, вычислить число Фибоначчи произвольного порядка позволяет формула Бине:

U_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}}

Первый член числителя есть не что иное как φ — золотое сечение:

\varphi = \left(\frac{1 + \sqrt{5}}{2}\right)

Золотое сечение φ = 1.6180339887 является специальным числом, обладающим рядом уникальных свойств. Прямоугольники с соотношением сторон равным золотому сечению выглядят «пропорционально» и приятны на вид. Вещами, имеющим такую форму, удобно пользоваться. Поэтому многим «прямоугольным» предметам нашего обихода (книгам, спичечным коробкам, чемоданам), да и просто диалоговым окнам программ, часто придается именно такая форма.

Используя обозначение золотого сечения φ, формулу для U_n можно переписать следующим образом:

U_{n} = \left(\frac{\varphi^n + \frac{1}{\varphi^n}}{\sqrt{5}}\right)

Не в даваясь в доказательство, можно показать, что второй член 1/\varphi^n при любых n, меньше 0.5, таким образом

U_{n} \approx \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n}{\sqrt{5}} \approx \frac{\varphi^n}{\sqrt{5}}

Таким образом, числа Фибоначчи — это ближайшее целое геометрической прогрессии, первый член которой равен \varphi/\sqrt{5}. Сами числа Фибоначчи растут в соответствии с соотношением золотого сечения.

Отношение же ближайших чисел Фибоначчи приблизительно равно золотому сечению φ и чем выше номер n, тем ближе отношение к золотому сечению.

\frac{U_{10}}{U_9} = \frac{55}{34} = 1.6176 \varphi = 1.6180

[править] Реализация

При создании программ, вычисляющих число Фибоначчи произвольного порядка обычно пользуются формулой Бине, позволяющей избежать сложение ряда. Однако, в 32-х разрядной операционной системе размер целых чисел ограничен, приходится либо ограничиваться теми числами, которые убираются в 32-разрядное число. Если использовать не целые, а числа с плавающей точкой, падает точность вычисления числа, как из-за накапливающихся ошибок вычисления, так и из-за ограничения мантиссы. Поэтому для точного вычисления числа следует хранить вычисляемое значение в массиве или строке.

[править] PHP

<?php
  error_reporting(E_ALL & ~E_NOTICE); 
  // Номер числа Фибоначчи
  $n = 200;
  // К-во разрядов
  $digit = intval($n / 4) + 5;
  // Вычисление числа Фибоначчи в массиве
  $a1[0] = 1;
  $a2[0] = 1;
  for($j = 2; $j < $n; $j++)
  {
    for($i = 0; $i < $digit; $i++)
    {
      $b = intval(($a1[$i] + $a2[$i])/10);
      $a3[$i] = $a1[$i] + $a2[$i] - $b * 10;
      $a1[$i + 1] += $b;
    }
    for($i = 0; $i < $digit; $i++)
    {
      $a1[$i] = $a2[$i];
      $a2[$i] = $a3[$i];
      $a3[$i] = 0;
    }
  }
  $flg = false;
  for($i = count($a2) - 1; $i >= 0; $i--)
  {
    if($a2[$i] >= 1) $flg = true;
    if($flg) echo $a2[$i];
  }
  echo "<br />\r\n";
?>

[править] Python

# -*- coding: utf-8 -*-
import sys
# Вычисление числа Фибоначчи произвольного порядка
def fibonacci(n):
  # К-во разрядов
  digit = int(n / 4) + 5
  # Подготавливаем списки
  a1 = [0 for x in range(digit)]
  a2 = [0 for x in range(digit)]
  a3 = [0 for x in range(digit)]
  # Первые два числа
  a1[0] = 1;
  a2[0] = 1;
  for j in range(n):
    if j < 2: continue
    for i in range(digit):
      b = int((a1[i] + a2[i]) / 10)
      a3[i] = a1[i] + a2[i] - b * 10
      if i < len(a1) - 1:
        a1[i + 1] += b;
    for i in range(digit):
      a1[i] = a2[i]
      a2[i] = a3[i]
      a3[i] = 0
  # Убираем лишние нули в конце
  i = len(a2) - 1
  while i >= 0:
    if a2[i] == 0: del a2[i]
    i = i - 1
  a2.reverse()
  return a2
# Вывод элементов массива, без перевода строк
def printlist(numlist):
  i = 0
  while i < len(numlist) - 1:
    sys.stdout.write(str(numlist[i]))
    i = i + 1
# N числа
n = 200
# Получаем список с разрядами числа
result = fibonacci(n)
# Выводим число
printlist(result)

[править] C#

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
 
namespace WinFormsFibonachi
{
  public partial class frmMain : Form
  {
    public frmMain()
    {
      InitializeComponent();
    }
 
    private void txtNumber_TextChanged(object sender, EventArgs e)
    {
      int n = Convert.ToInt32(this.txtNumber.Text);
      double rac5 = Math.Sqrt(5);
      double alfa = (1 + rac5) / 2;
      double beta = (1 - rac5) / 2;
      try
      {
          Int64 result = Convert.ToInt64((Math.Pow(alfa, (double)n) - Math.Pow(beta, (double)n)) / rac5);
          this.txtResult.Text = result.ToString();
      }
      catch (OverflowException exc)
      {
          this.txtResult.Text = "Переполнение";
      }
    }
  }
}

[править] C++ (Qt)

// main_form.h
#ifndef _main_form_h_
#define _main_form_h_
 
#include <QObject>
#include <math.h>
#include <QVector>
#include <QtCore>
#define UNI(x) (const QChar *)L##x
 
class FibonacciForm : public QObject
{
  Q_OBJECT
public:
  FibonacciForm();
  long long getFibonacci(int);
  QString getLongFibonacci(long);
public slots:
  void setValue(const QString &);
signals:
  void valueChanged(const QString &);
private:
  int m_iNumber;
};
 
#endif
// main_form.cpp
#include "main_form.h"
 
FibonacciForm::FibonacciForm() : QObject(), m_iNumber(0)
{
}
// Слот для приема числа и преобразования его в число Фибоначчи
void FibonacciForm::setValue(const QString &txtNumber)
{
  int Number = txtNumber.toInt();
  if(Number != m_iNumber)
  {
    m_iNumber = Number;
//    emit valueChanged(QString::number(getFibonacci(Number)));
    emit valueChanged(getLongFibonacci(Number));
  }
}
// Вычисление числа Фибоначчи
long long FibonacciForm::getFibonacci(int Number)
{
  // Вычисляем число Фибоначчи по формуле Бине
  double rac5 = sqrt(double(5));
  double alfa = (1 + rac5) / 2;
  double beta = (1 - rac5) / 2;
 
  return (long long)((pow(alfa, (double)Number) - pow(beta, (double)Number)) / rac5);
}
// Вычисление числа Фибоначчи произвольного порядка
QString FibonacciForm::getLongFibonacci(long Number)
{
  // Если число пятизначное - прекращаем вычисления
  if(Number / 10000) return QString(UNI("Число слишком велико"));
  // Вычисляем примерное значение числа Фибоначчи
  long digit = long(Number / 4) + 5;
  int b = 0, i = 0, j = 0;
  // Подготавливаем вспомогательные вектора
  QVector<int> a1(digit, 0);
  QVector<int> a2(digit, 0);
  QVector<int> a3(digit, 0);
  // Первые два числа
  a1[0] = 1;
  a2[0] = 1;
  for(int j = 2; j < Number; j++)
  {
    for(int i = 0; i < digit; i++)
    {
      b = int((a1[i] + a2[i]) / 10);
      a3[i] = a1[i] + a2[i] - b * 10;
      if(i < a1.size() - 1)
        a1[i + 1] += b;
    }
    for(int i = 0; i < digit; i++)
    {
      a1[i] = a2[i];
      a2[i] = a3[i];
      a3[i] = 0;
    }
  }
  // Убираем лишние нули в конце и преобразуем число в строку
  QString result;
  bool flg = true;
  for(int i = a2.size() - 1; i >= 0 ; --i)
  {
    if(flg && a2[i] != 0) flg = false;
    if(!flg || a2[i] != 0) result.append(static_cast<char>(a2[i] + 0x30));
  }
 
  return result;
}
// main.cpp
#include <QtGui>
#include "main_form.h"
 
#define UNI(x) (const QChar *)L##x
 
int main(int argc, char *argv[])
{
    QApplication a(argc, argv);
    QWidget *wdt = new QWidget();
    // Обработчик формы Числа Фибоначчи
    FibonacciForm *fib = new FibonacciForm();
 
    QVBoxLayout *vbxLayout = new QVBoxLayout;
    vbxLayout->setMargin(10);
    vbxLayout->setSpacing(5);
 
    QLabel *lblFibonacci = new QLabel();
    lblFibonacci->setText(QString(UNI("Число Фибоначчи")));
    vbxLayout->addWidget(lblFibonacci);
    QLineEdit *txtFibonacci = new QLineEdit();
    txtFibonacci->setEnabled(false);
    vbxLayout->addWidget(txtFibonacci);
 
    QLabel *lblNumber = new QLabel();
    lblNumber->setText(QString(UNI("Номер")));
    vbxLayout->addWidget(lblNumber);
    QLineEdit *txtNumber = new QLineEdit();
    vbxLayout->addWidget(txtNumber);
    // Устанавливаем обработчик
    QObject::connect(
      txtNumber,
      SIGNAL(textChanged(const QString &)),
      fib,
      SLOT(setValue(const QString &)));
    QObject::connect(
      fib,
      SIGNAL(valueChanged(const QString &)),
      txtFibonacci,
      SLOT(setText(const QString &)));
 
    wdt->setLayout(vbxLayout);
 
    // Устанавливаем название программы
    QString title(UNI("Числа Фибоначчи"));
    wdt->setWindowTitle(title);
    // Устанавливаем фиксированные размеры формы и
    // кнопки сворачивания и выключения
    wdt->setWindowFlags(Qt::Window | Qt::WindowMinimizeButtonHint);
    wdt->setFixedSize(250, 120);
    // Отображаем форму
    wdt->show();
 
    return a.exec();
}

[править] В природе

Соотношение золотого сечения и чисел Фибоначчи часто наблюдаются в биорешениях. Биосфера за миллиарды лет обнаружила и реализовала в живых организмах массу инженерных решений и оптимальных конструкций. Не были обойдены стороной и числа Фибоначчи.

В крупных шишках, плодах, вроде ананаса количество спиралей в которые закручены чешуйки, соответствуют числам Фибоначчи: 5, 8, 13.

Тоже самое касается сложноцветных цветов, количество спиралей в корзинках которых достигает 13, 21, 34.

В подсолнухе количество спиралей может достигать 55 и 89.

[править] См. также

[править] Литература

  • Н.Н. Воробьев Числа Фибоначчи. — М.: Наука, 1992. — 192 с. — ISBN 978-5-8459-1640-2
Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты