Метод Фибоначи

From

Alexey Tigarev (2:467/106.60)

To

Denis N. Voituk

Date

2002-12-08T21:27:54Z

Area

RU.ALGORITHMS

Здравствуй, Denis!

09 Дек 02 21:00, Denis N. Voituk писал(а|о)? All:

 DNV> Есть такое задание:
 DNV> Дана функция f(x). Нужно найти ее минимум (если он есть) и посчитать
 DNV> количество шагов, за которое это делается. Все сделать методом
 DNV> Фибоначи (естественно, имеется ввиду использование чисел Фибоначи).
 DNV>
 DNV> У кого-нить есть алгоротим? От исходника тоже бы не отказался :) Хотя
 DNV> по-любому придется во всем разбираться...

Было у меня в курсовом, вот решение на Питоне.
Пример использования, например, в test().
Суть алгоритма очевидна из функции minimise(). Питон - почти что псевдокод :)

/*─═>/* Здесь начинается FIBONA~1.PY /*<═─/*
#!/usr/local/bin/python

"""  Метод Фибоначчи """

__version__ = '$Id: fibonaccii.py,v 1.1.1.1 2001/01/08 09:52:52 tigra Exp $'

import fib


def F(n): return float(fib.F[n])

def findN(a, b, epsilon):
    """ Поиск параметра N метода Фибоначчи

    N, такое, что F(N+1) < (b-a)/epsilon <= F(N+2)
    """
    z = float(b-a)/epsilon
    N = 0
    while 1:
       if F(N+1) < z <= F(N+2):
          return N
       N = N + 1

SMALLEST = 1e-16

def equal(x, x_):
    return abs(x - x_) <= SMALLEST

def minimise(a1, b1, f, epsilon):
    """ Сузить отрезок (a1, b1) """

    a, b = a1, b1
    x1 = x2 = (b+a)/2

    N  = findN(a1, b1, epsilon)
    for k in range(1, N+1):
        x1 = a + F(N-k+1)/F(N+2)*(b1-a1)
        x2 = a + F(N-k+2)/F(N+2)*(b1-a1)
        print "k=%2d x1=% 02.5f x2=% 02.5f a=% 02.5f b=% 02.5f"  \
              % (k, x1, x2, a, b)
        if x2 < x1:
           if f(x2) <= f(x1):
              b = x2
           else:
              a = x1
        else:
           if f(x2) <= f(x1):
              a = x1
           else:
              b = x2
        if equal(x1, x2):
           break
    return x1

f = lambda x: x*x # Функция для минимизации

def min(a, b, f, e):
    return minimise(float(a), float(b), f, float(e))

def test():
    minimise(-1.0, 1.1, lambda x: x*x, 0.01)

#if __name__ == '__main__' : test()

/*─═>/* А здесь, видимо, не начинается FIBONA~1.PY /*<═─/*


/*─═>/* Здесь начинается FIB.PY /*<═─/*
from  LazySequence import *

class Fib(LazySequence):
      """  lazy Fibonaccii sequence """

      def __init__(self):
          self.data = [None, 1L, 1L]

      def calculate(self, number):
          return F[number-1] + F[number-2]

F = Fib()

/*─═>/* А здесь, видимо, не начинается FIB.PY /*<═─/*


/*─═>/* Здесь начинается LAZYSE~1.PY /*<═─/*
"""  Ленивые последовательности """

__version__ = '$Id: LazySequence.py,v 1.1.1.1 2001/01/08 09:52:52 tigra Exp $'

class LazySequence:
    """ Ленивая последовательность """

    data = []
    """ Уже вычисленные элементы последовательности """

    def calculate(self, number): pass
    """ вычисляет элемент последовательноси с указанным номером """

    def __getitem__(self, number):
        if number > len(self.data)-1:
           for i in range(len(self.data), number+1):
               self.data.append(self.calculate(i))
        return self.data[number]

/*─═>/* А здесь, видимо, не начинается LAZYSE~1.PY /*<═─/*

    C уважением, Тигра        <tigra@ibis.odessa.ua>        ICQ# 9555092
... На каждой линии есть станция PeaceDeath, и кто туда доехал - молодец (Умка)
--- [ODESSA.PROGRAMMING] [ODESSA.PSYCHOLOGY]
 * Origin: http://informatics.od.ua/ http://nlp.od.ua/ (2:467/106.60)