Объектно-ориентированное программирование на С#. Андрианова А.А - 47 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

47
Пример 2. Вычислить n-ое число Фибоначчи. Известно, что F
1
=1,
F
2
=1, F
i
=F
i-1
+ F
i-2
, т.е. каждый член последовательности чисел Фибоначчи,
начиная с третьего, равен сумме двух предыдущих.
class Program
{
// определение метода вычисления n-го числа Фибоначчи
static uint Fibonachi(uint n)
{
// условие выхода из рекурсии
if (n == 2 || n == 1)
return 1;
else
// рекурсивный вызов функции
return Fibonachi(n - 2) + Fibonachi(n - 1);
}
static void Main(string[] args)
{
uint n;
Console.WriteLine("Введите n:");
while(true)
{
try
{
n=uint.Parse(Console.ReadLine());
break;
}
catch (Exception ex)
{
Console.WriteLine("Введите корректное
число.\n");
}
}
uint k=Fibonachi(n); // первый вызов функции
Console.WriteLine("F({0})={1}",n,k);}
}
}
Это пример задачи, в которой рекурсивный алгоритм очевиден, но его
использование приводит к большим вычислительным расходам и излишним
затратам памяти. В теле метода Fibonachi() несколько раз
осуществляется рекурсивный вызов. Каждый вызов требует выделения
памяти. Например, для вычисления F
10
необходимо вызвать метод
Fibonachi для вычисления F
9
и F
8
. В свою очередь, для вычисления F
9
снова понадобится вызвать метод Fibonachi() для вычисления F
8
и т.д.
согласно приведенной ниже схеме.
Из схемы видно, что для некоторых аргументов приходится 
      Пример 2. Вычислить n-ое число Фибоначчи. Известно, что F1=1,
F2=1, Fi=Fi-1 + Fi-2, т.е. каждый член последовательности чисел Фибоначчи,
начиная с третьего, равен сумме двух предыдущих.
   class Program
   {
      // определение метода вычисления n-го числа Фибоначчи
      static uint Fibonachi(uint n)
      {
         // условие выхода из рекурсии
         if (n == 2 || n == 1)
            return 1;
         else
            // рекурсивный вызов функции
            return Fibonachi(n - 2) + Fibonachi(n - 1);
      }

       static void Main(string[] args)
       {
          uint n;
          Console.WriteLine("Введите n:");
          while(true)
          {
             try
             {
                 n=uint.Parse(Console.ReadLine());
                 break;
             }
             catch (Exception ex)
             {
                 Console.WriteLine("Введите корректное
                                                   число.\n");
             }
          }
          uint k=Fibonachi(n);      // первый вызов функции
          Console.WriteLine("F({0})={1}",n,k);}
       }
   }

      Это пример задачи, в которой рекурсивный алгоритм очевиден, но его
использование приводит к большим вычислительным расходам и излишним
затратам памяти. В теле метода Fibonachi()               несколько раз
осуществляется рекурсивный вызов. Каждый вызов требует выделения
памяти. Например, для вычисления F10 необходимо вызвать метод
Fibonachi для вычисления F9 и F8. В свою очередь, для вычисления F9
снова понадобится вызвать метод Fibonachi() для вычисления F8 и т.д.
согласно приведенной ниже схеме.
      Из схемы видно, что для некоторых аргументов приходится
                                                                        47

Страницы