Согласие на обработку персональных данных.

16.10.2018
Новая статья Типизированные и нетипизированные указатели.

09.10.2018
Новые видео и статья Как изменить цвет текста в HTML.

02.10.2018
Новый выпуск журнала Автоматизация и программирование.

28.09.2018
Новые видео и статья Процедура Close.

26.09.2018
Новые видео и статья Как уменьшить размер программы в Lazarus.



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

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

Условие задачи 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;
}

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


Основы C++ Основы C++

C++ - это один из самых популярных языков программирования. Не важно, на каком языке программируете лично вы. Но, если вы хотя бы в общих чертах не знаете С++, то это большой пробел в вашем образовании, который надо восполнить как можно быстрее... Подробнее...
Инфо-МАСТЕР ®
Все права защищены ©
e-mail: mail@info-master.su

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