Раздел: Задачи / Простейшие /

Является ли число числом Фибоначчи

Основы программирования

Подпишись на новости, чтобы ничего не пропустить


Условие задачи 2.23

Задача 2.23
Дано натуральное число Х. Если оно является числом Фибоначчи, то присвоить переменной Т значение 1, иначе - значение 0. Вывести на экран значение Т.

На мой взгляд, задачка любопытная. Начинающим придётся подумать и включить воображение, что и требуется при изучении программирования.

О том, как получить последовательность чисел Фибоначчи с помощью рекурсии, я рассказывал здесь (если вы не знаете, что такое числа Фибоначчи, то узнаете там же).

Напомню, как выглядит исходный код рекуррентной функции для получения нужной нам последовательности чисел:

//**********************************************************
// Вычисляет число Фибоначчи
//**********************************************************
function Fibonachi(Num : integer) : integer;
begin
  //Если это 1-й или 2-й элемент
  if (Num = 1) or (Num = 2) then  
    Result := 1
  //Иначе функция вызывает сама себя (рекурсия)
  else              
    Result := Fibonachi(Num-1) + Fibonachi(Num-2);
end;

Один из способов решения данной задачи - это просто вызывать эту функцию и сравнивать результат с числом Х. Однако с рекурсией надо быть осторожным - при большом количестве чисел она может занять очень много времени на выполнение. Поэтому лучше обойтись без неё.

Для решения задачи сначала присвоим переменной Т значение 0. Затем в цикле будем создавать числа Фибоначчи, и сравнивать с числом Х. Если текущее число Фибоначчи будет равно числу Х, то мы прервём цикл и присвоим значение 1 переменной Т.

Ну а дальше останется только вывести на экран значение Т.

Для лучшей наглядности предоставим пользователю возможность ввести число Х, а также будем выводить ряд чисел Фибоначчи на экран в ходе выполнения программы.

Также ограничим аппетиты пользователя при вводе значения Х, например, числом 1 000 000 000. Иначе время работы программы может сильно затянуться (особенно если использовать рекурсию). Кроме того, введённое число не должно быть равно нулю - это тоже будем проверять. Также число не должно быть отрицательным.

А ещё пользователь может ввести вместо числа букву (или строку). В С++ это будет обработано как число и выдано сообщение. В Паскале же придётся делать дополнительную обработку. Но, чтобы не загромождать код, мы этого делать не будем.

Также обратите внимание на проверку условия в if (X == F2) - в С++ здесь многие новички совершают ошибку, которую долго не могут найти и не понимают, почему программа работает неправильно.

Решение задачи 2.23 на Паскале
 
program mytask;

//****************************************************************
// КОНСТАНТЫ
//****************************************************************
const
  MAX_VAL = 1000000000;

//****************************************************************
// ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
//****************************************************************
var
  X   : Integer;
  Y   : Integer;
  F1  : Integer = 1;
  F2  : Integer = 1;
  T   : WORD = 0;

//****************************************************************
// ОСНОВНАЯ ПРОГРАММА
//****************************************************************
begin
  Write('X = '); ReadLn(X);

  if X > MAX_VAL then
    begin
      WriteLn('The number is too big!');
      WriteLn('The number X should be no more than ', MAX_VAL);
      WriteLn('Press ENTER...');
      ReadLn;
      Exit;
    end;

  if X < 1 then
    begin
      WriteLn('The number is too small!');
      WriteLn('Number X should not be less than ', 1);
      WriteLn('Press ENTER...');
      ReadLn;
      Exit;
    end;

  Write(F1, ' ');
  while F2 <= X do
    begin
      Write(F2, ' ');
      if X = F2 then
        begin
          T := 1;
          Break;
        end;
      Y := F2;
      F2 := F2 + F1;
      F1 := Y;
    end;

  WriteLn(#10#13'T = ', T);
  WriteLn('The end. Press ENTER...');
  ReadLn;
end.     
Решение задачи 2.23 на С++
#include <cstdlib>
#include <iostream>

using namespace std;

//****************************************************************
// КОНСТАНТЫ
//****************************************************************
const signed int MAX_VAL = 1000000000;

//****************************************************************
// ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
//****************************************************************
signed int X;
signed int Y;
signed int F1 = 1;
signed int F2 = 1;
unsigned short int T = 0; 

//****************************************************************
// ОСНОВНАЯ ПРОГРАММА
//****************************************************************
int main(int argc, char *argv[])
{
  cout << "X = "; cin >> X; 
  
  if (X > MAX_VAL) 
    {
      cout << "The number is too big!" << endl;
      cout << "The number X should be no more than " << MAX_VAL << endl;
      system("PAUSE");
      return EXIT_FAILURE;
    }; 
  
  if (X < 1) 
    {
      cout << "The number is too small!" << endl;
      cout << "Number X should not be less than " << 1 << endl;
      system("PAUSE");
      return EXIT_FAILURE;
    };   
    
  cout << F1 << " ";
  while (F2 <= X)
    {
      cout << F2 << " ";
      if (X == F2)  //!!! ВНИМАНИЕ !!! Это НЕ Паскаль!
        {
          T = 1;
          break;
        };
      Y = F2;
      F2 = F2 + F1;
      F1 = Y;
    };

  cout << endl << "T = " << T << endl;        
  
  system("PAUSE");
  return EXIT_SUCCESS;
}

Является ли число числом Фибоначчи


Помощь в технических вопросах Помощь в технических вопросах

Помощь студентам. Курсовые, дипломы, чертежи (КОМПАС), задачи по программированию: Pascal/Delphi/Lazarus; С/С++; Ассемблер; языки программирования ПЛК; JavaScript; VBScript; Fortran; Python и др. Разработка (доработка) ПО ПЛК (предпочтение - ОВЕН, CoDeSys 2 и 3), а также программирование панелей оператора, программируемых реле и других приборов систем автоматизации. Подробнее...
Инфо-МАСТЕР ®
Все права защищены ©
e-mail: mail@info-master.su

Яндекс.Метрика