Переваги і недоліки методу Фібоначчі

 

ЗМІСТ

 

1 ПОСТАНОВКА ЗАДАЧІ……………………………………………………….4

    1.1 Інструкція на підготовку даних і користування програмою…………... 6

2. Числа та ряди Фібоначчі, їх застосування та роль в математиці……………………………………………………………………... 7

3 Характеристика програмного продукту та середовище програмування……………………………………………………………….10

4 Числа Фібоначчі в теорії пошуку……………………………………20

5 Реалізація методу безумовного екстремуму………………….25

 Висновок ……………………………………………………………………….27

 літературА………………………………………………………………………28

  Додатки…………………………………………………………………………29

  

 

 

 

 

 

 

1. Постановка задачі

 

В даний час велике значення має вирішення прикладних завдань, що дає поштовх до розвитку різних галузей науки.  Значна частина  прикладних завдань пов'язана з  методами оптимізації. Оптимізація  застосовується з різною метою, залежно  від тієї мети, яку поставила дана галузь.  У цій роботі розглядається  метод оптимізації, що застосовується при вирішенні завдань, пов'язаних із знаходженням мінімумів функцій, який відноситься до числових методів  пошуку безумовних екстремумів - це метод  Фібоначчі.  При розгляді практичних завдань функція f(x) невідома, а якщо відома, то задана не в аналітичному вигляді.

Завдання знаходження  безумовного екстремуму у вигляді  числа має велику складність. Такого роду завдання вирішуються за допомогою  методів одновимірної оптимізації, до яких відноситься метод Фібоначчі. Тому тема, що розглядається в даній роботі, є актуальною при вирішенні практичних завдань.

Метою даної роботи є розгляд  і побудова  алгоритму для знаходження  безумовних екстремумів заданих  функцій методом Фібоначчі, створення робочої програми на мові C++, яка дозволить вирішувати дану задачу, розгляд стратегій пошуку мінімумів в методі Фібоначчі, а також порівняння домінантного методу цієї роботи  з іншими методами знаходження наближеного значення точок мінімумів, виявлення переваг і недоліків методу Фібоначчі.

Метод Фібоначчі застосовується для чисельного пошуку безумовного екстремуму. Потрібно знайти  x для f(x) на інтервалі [a;b] , де існує мінімум даної функції, x повинен відповідати точці мінімуму.  Наше завдання зводиться до пошуку, а завдання пошуку має три важливі аспекти: 

1. Нехай ми маємо можливість  зробити n послідовних визначень значення f, вибираючи кожного разу точку визначення на свій розсуд. То виникають питання, в яких точках слід визначати значення функцій, щоб точка x визначалася з найбільшою точністю, і яка ця точність? 

2.Якщо  ми хочемо визначити  мінімізуючу функцію f  в точці x  із заданою точністю . Скільки визначень значень функції f для цього необхідно зробити і як ці визначення організувати? 

3. У яких умовах дані  можливості достатні для досягнення  поставленої мети? Тобто необхідно  вирішення декількох завдань.

Щоб побудувати метод одновимірної мінімізації, який повинен працювати  за принципом послідовного скорочення інтервалу невизначеності, потрібно задати правило вибору двох внутрішніх точок  на кожному інтервалі. Метод  Фібоначчі дозволяє скорочувати інтервал невизначеності при заданій кількості обчислень функцій. Скорочення інтервалів спирається на числа Фібоначчі.

Ще раз сформулюємо  поставлене завдання. У нас є функція  f(x) яка має мінімум на заданому інтервалі [a;b] необхідно знайти мінімум цієї функції на цьому інтервалі не більше ніж за N кроків.

 

 

1. Інструкція на підготовку даних і користування програмою

 

Для запуску програми  потрібно лише відкрити файл Fibonacci.exe . Спочатку треба вирішити хочете ви отримати всі N чисел з ряду Фібоначчі, чи одне N.  Далі ввести кількість вираховувань N  - це повинно бути число цілого типу, чим більше буде число тим більш точний ми отримаємо результат. Після цього ми повинні ввести початкову точку a та кінцеву b. В свою чергу ми  отримаємо N кількість чисел Фібоначчі, чи введене вами число із ряду Фібоначчі та погрішність. Після виконання всіх операцій програма видасть нам на екран мінімум функції на заданому відрізку не більш ніж за N кроків. На сам кінець ми відповідаємо на питання хочемо ми повторити вираховування чи ні, якщо ви відповіли «y», тобто «так», тоді всі операції які ми проводили з нашою програмою доведеться повторити інакше виконання програми закінчиться.

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Числа та ряди Фібоначчі, їх застосування та роль в математиці

 

Леонардо з Пізи, відомий  як Фібоначчі, був першим з великих математиків Європи пізнього Середньовіччя. Будучи народженим у Пізі в багатій купецькій сім’ї, він прийшов у математику завдяки суто практичної потреби встановити ділові контакти. У молодості Леонардо багато подорожував, супроводжуючи батька в ділових поїздках. Під час таких поїздок він багато спілкувався з місцевими вченими.

Числовий ряд, що носить сьогодні його ім’я, виріс із проблеми з кроликами, яку Фібоначчі виклав у своїй книзі «Liber abacci», написаної в 1202 році:

   Людина посадив  пару кроликів у загін, оточений  з усіх боків стіною. Скільки  пар кроликів за рік може  справити на світ ця пара, якщо  відомо, що кожен місяць, починаючи  з другого, кожна пара кроликів  створює на світ одну пару?

Можна переконатися, що кількість  пар в кожен з дванадцяти наступних  місяців  буде відповідно

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

 

Іншими словами, число  пар кроликів створює ряд, кожен  член в якому – сума двох попередніх. Він відомий як ряд Фібоначчі, а самі числа – числа Фібоначчі. Виявляється, ця послідовність має безліч цікавих з точки зору математики властивостей. Ось приклад: ви можете розділити лінію на два сегменти, так що співвідношення між більшим і меншим сегментом буде пропорційно співвідношенню між всією лінією і великим сегментом. Цей коефіцієнт пропорційності, приблизно рівний 1,618, відомий як золотий перетин. В епоху Відродження вважалося, що саме ця пропорція, дотримана в архітектурних спорудах, найбільше радує око. Якщо ви візьмете послідовні пари з ряду Фібоначчі і будете ділити більше число з кожної пари на менше, ваш результат буде поступово наближатися до золотого перетину.

З тих пір як Фібоначчі відкрив свою послідовність, були знайдені навіть явища природи, в яких ця послідовність, схоже, грає важливу роль. Одне з них – філлотаксис (листорозміщення) – правило, за яким розташовуються, наприклад, насіння в суцвітті соняшнику. Насіннячка впорядковані в два ряди спіралей, один з яких йде за годинниковою стрілкою, інший проти. І яке ж число насінин у кожному випадку? 34 і 55.

 

Окрім числової послідовності  Леонардо Пізанський зробив ряд відкриттів : 

- сформулював правило  для знаходження суми членів  довільної –  арифметичної  прогресії; 

- розглянув поворотну  послідовність, в якій кожне  число,  починаючи з третього, дорівнює сумі двох попередніх  йому чисел; 

- описав спосіб приведення  дробів до спільного знаменника  за допомогою  знаходження  найменшого спільного кратного  знаменника (раціональніший чим  використовували арабських математиків). 

Окрім цього, він розробив свої методи вирішення різних завдань. 

      Іменем  Фібоначчі названо астероїд 6765 Фібоначчі.

Принцип, закладений у процедурі  отримання послідовності Фібоначчі, широко використовується в математиці й програмуванні.

  

У математиці відома тотожність Брамагупти — Фібоначчі, яку отримав індійський математик Брамагупта, і описав у «Книзі квадратів» Леонардо Пізанський.

Фібоначчі познайомив Європу із позиційною системою числення, однак існує cистема числення Фібоначчі, в основі якої лежить послідовність Фібоначчі.

 Леонардо Пізанський  вніс великий вклад в математику  середньовічної Європи.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Характеристика програмного продукту та середовище програмування

 

Dev-C++ — це інтегроване середовище для програмування на мовах C/C++ , що працює під управлінням операційної системи Windows. Середовище       Dev-C++ поширюється вільно з вихідними кодами (на Delphi) за ліцензією GPL.  Сам Dev-C++ написаний на Delphi. Засновник проекту Колін Лаплас, компанія Bloodshed Software. У свій час був доступний Linux-порт, проте зараз актуалізована лише Windows-версія. На справжній момент не розробляється.[2]

Переваги Dev-C++:

• графічний інтерфейс
• російськомовне меню
• можливість створювати консольні і графічні програми.
• Підтримка компіляторів з набору GCC
• Вбудований відладчик (GDB)
• Менеджер проектів
• Браузер класів
• Автодоповнення коду
• Редактор з підтримкою синтаксису
• Профілізація
• Підтримка CVS

 Через свій невеликий  розмір і простоту установки  є ідеальним засобом для людей,  які лише роблять перші кроки  в програмуванні. У той же  час, програма володіє всіма  необхідними функціями для розробки  невеликих проектів.

Недоліки:

• досить складно написати програму, яка працює з графічними об’єктами
• не завжди стабільно працює відладчик

 

Дана програма розпочинається з препроцесора, ключове слово  include говорить компілятору, що треба підключити бібліотеки  iostream,stdlib,stdio,math

#include <iostream>

#include <stdlib.h>

#include<stdio.h>

#include <math.h>

 

Надалі в програмі йде  опис двох класів, перший клас  Fibonacci1 описує знаходження i-го числа Фібоначчі.

class Fibonacci1

{

 

 public: int i,N;

 long int *F;

 

 int metod1 ( int N )

{

F=( long int*)malloc((N)*sizeof(long int));//выделение памяти

F[0]=1;

 

F[1]=1;

for (i=2;i<=N;i++)

 

F[i]=F[i-1]+F[i-2];

 

for(i = 0; i <= N; i++)

                printf("Число Фибоначчи %d  = %d \n",

                        i,                   F[i]);

                        free(F);

                        };

                        };

 

Другий клас Fibonacci2  знаходить ряд із N чисел Фібоначчі.

 

class Fibonacci2

{

 

public: int i,N;

long int *F;

int AH;

 

 int metod2(int N){

 

F=( long int*)malloc((N)*sizeof(long int));//выделение памяти

F[0]=1;

 

F[1]=1;

for (i=2;i<=N;i++)

 

F[i]=F[i-1]+F[i-2];

 

                printf("число Фибоначчи  %d  = %d\n",

                        N,                   F[N]);

                        free(F);

};

 

};

 Затим йде прототип функції, в якій йде функція мінімум якої я буду знаходити.

 

float function (float);

 

float function (float x)

{

 

return (pow(x,3)-2*x*x+4*x+2);

}

 

Надалі йде функція, яка  розраховує мінімум вище описаної функції.

void kurs()

{

float   a=0,b=0,e=0, x1=0, x2=0, y1=0, y2=0, min=0;

char otvet;

int variant;

Fibonacci1 metod1;Fibonacci2 metod2;

 

 int  N=0, i=0,j=0;

 long int *F;

printf("Выбери вариант \n");

 printf("variant 1. A определенное число Фибоначчи \n");

 printf("variant 2. N чисел Фибоначчи\n");

 while ((scanf("%d",&variant)!=1)||(variant!=1)&&(variant!=2))

{  fflush(stdin);

cout<<" wrong "<<endl<<endl;

     printf("choose a variant\n");

 printf("variant 1. A определенное число Фибоначчи \n");

 printf("variant 2. N чисел Фибоначчи\n");

 cin>>variant;

 

}

if(variant==1)

{

 

printf("Введи N\n");

while ((scanf("%d",&N)!=1)||(N<2))

{  fflush(stdin);

 printf ("ОШИБКА \n");

printf ("Введи число ");

  }

  metod2.metod2 (N);

}

if(variant==2)

{

printf("Введи N\n");

while ((scanf("%d",&N)!=1)||(N<2))

{  fflush(stdin);

 printf ("Ошибка\n");

printf ("Введи число");

  }

 

  metod1.metod1(N);

}

 

printf (" 2*x*x*x-12*x*x+4*x+2\n ");

     

      

printf(" Начальная точка a = ");

while ((scanf("%f",&a)!=1)|| (a<0))

{  fflush(stdin);

 printf ("\n  Ошибка\n");

printf ("Введи число"); //защита от букв.

   } 

  

printf("\n Начальная точка b = ");

while ((scanf("%f",&b)!=1)|| (b<1)||(b<a))

{  fflush(stdin);

printf ("\n  Ошибка\n");

printf ("Введи число"); //защита от букв.

   } 

 

 

F=( long int*)malloc((N)*sizeof(long int));

F[0]=1;

 

F[1]=1;

e=(b-a)/(F[N]);

printf ("error = %f\n",e);

x1=F[N-2];

x1=(x1/F[N])*(b-a)+a;

y1=function(x1);

x2=F[N-1];

x2=(x2/F[N])*(b-a)+a;

y2=function(x2);  

free(F);//освобождение памяти

 

 

if (y1<y2)

{

b=x2;

x2=x1;

 

y2=y1;

x1=a+b-x2;

y1=function(x1);

}

 

else

{

a=x1;

x1=x2;

   y1=y2;

 

x2=a+b-x1;

  y2=function(x2);

}

 

if (y1<y2)

{

b=x2;

x2=x1;

y2=y1;

}

 

else a=x1;

x1=x2-e;

y1=function(x1);

 

if(y1<y2)

b=x2;

else  

a=x1;

 

min=(a+b)/2;

printf("минимум= %f\n",min);

cout<<" Хочешь  продолжить?"<<endl;

cin>>otvet;

cout<<endl<<endl;

while(otvet=='y')

{

 kurs();

}

}

 

Після всього цього йде  головна функція main, яка виводить рамку, та викликає функцію пошуку мінімуму.

 

main(void)

{

 

 int iRow=0;

 

 

//////////////////// РАМКА /////////////////////////////////