Определение того, является ли число числом Фибоначчи

Вместо передачи индекса n напишите функцию, которая принимает ограничение и заставляет ее генерировать числа Фибоначчи до этого ограничения включительно. Получите, чтобы он возвращал логическое значение в зависимости от того, достигает ли он или пропускает предел, и вы можете использовать это, чтобы проверить, входит ли это значение в последовательность.

Поскольку это домашнее задание, такой толчок, вероятно, все, что мы должны вам дать ...

В порядке. Поскольку люди утверждали, что я просто говорю «факты» против «предположений») без каких-либо данных, подтверждающих это, я написал собственный тест.

Не java, а код C # ниже.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SO
{
    class Program
    {
        static void Main(string[] args)
        {
            AssertIsFibSqrt(100000000);

            MeasureSequential(1);
            MeasureSqrt(1);

            MeasureSequential(10);
            MeasureSqrt(10);

            MeasureSequential(50);
            MeasureSqrt(50);

            MeasureSequential(100);
            MeasureSqrt(100);


            MeasureSequential(100000);
            MeasureSqrt(100000);

            MeasureSequential(100000000);
            MeasureSqrt(100000000);

        }

        static void MeasureSequential(long n)
        {
            int count = 1000000;
            DateTime start = DateTime.Now;
            for (int i = 0; i < count; i++)
            {
                IsFibSequential(n);
            }
            DateTime end = DateTime.Now;

            TimeSpan duration = end - start;

            Console.WriteLine("Sequential for input = " + n + 
                              " : " + duration.Ticks);
        }

        static void MeasureSqrt(long n)
        {
            int count = 1000000;

            DateTime start = DateTime.Now;
            for (int i = 0; i < count; i++)
            {
                IsFibSqrt(n);
            }
            DateTime end = DateTime.Now;

            TimeSpan duration = end - start;

            Console.WriteLine("Sqrt for input =  " + n + 
                              " : " + duration.Ticks);
        }

        static void AssertIsFibSqrt(long x)
        {

            Dictionary<long, bool> fibs = new Dictionary<long, bool>();
            long a = 0;
            long b = 1;
            long f = 1;

            while (b < x)
            {
                f = a + b;
                a = b;
                b = f;

                fibs[a] = true;
                fibs[b] = true;
            }

            for (long i = 1; i <= x; i++)
            {
                bool isFib = fibs.ContainsKey(i);

                if (isFib && IsFibSqrt(i))
                {
                    continue;
                }

                if (!isFib && !IsFibSqrt(i))
                {
                    continue;
                }

                Console.WriteLine("Sqrt Fib test failed for: " + i);
            }
        }
        static bool IsFibSequential(long x)
        {
            long a = 0;
            long b = 1;
            long f = 1;

            while (b < x)
            {
                f = a + b;
                a = b;
                b = f;
            }
            return x == f;
        }

        static bool IsFibSqrt(long x)
        {
            long y = 5 * x * x + 4;

            double doubleS = Math.Sqrt(y);

            long s = (long)doubleS;

            long sqr = s*s;

            return (sqr == y || sqr == (y-8));
        }
    }
}

А вот и вывод

Sequential for input = 1 : 110011
Sqrt for input =  1 : 670067

Sequential for input = 10 : 560056
Sqrt for input =  10 : 540054

Sequential for input = 50 : 610061
Sqrt for input =  50 : 540054

Sequential for input = 100 : 730073
Sqrt for input =  100 : 540054

Sequential for input = 100000 : 1490149
Sqrt for input =  100000 : 540054

Sequential for input = 100000000 : 2180218
Sqrt for input =  100000000 : 540054

Метод sqrt превосходит наивный метод, когда сам n = 50, возможно, из-за наличия аппаратной поддержки на моей машине. Даже если бы оно было 10 ^ 8 (как в тесте Питера), под этим пороговым значением находится не более 40 чисел Фибоначчи, которые можно было бы легко поместить в таблицу поиска и при этом превзойти наивную версию для меньших значений.

Также у Питера плохая реализация SqrtVersion. На самом деле ему не нужно вычислять два квадратных корня или вычислять степени с помощью Math.Pow. Он мог бы хотя бы попытаться сделать это лучше, прежде чем опубликовать результаты своих тестов.

В любом случае, я позволю этим фактам говорить сами за себя, а не так называемым «догадкам».

Положительное целое число x является числом Фибоначчи тогда и только тогда, когда одно из 5x ^ 2 + 4 и 5x ^ 2-4 является полным квадратом.

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

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

1. Сгенерируйте число Фибоначчи
2. Если оно меньше целевого числа, сгенерируйте следующие фибоначчи и повторите
3. Если это целевое число, то успех
4. Если оно больше целевого числа, то неудача.

Я бы, вероятно, использовал рекурсивный метод, передав текущее n-значение (т.е. чтобы вычислить n-е число Фибоначчи) и целевое число.

Если моя Ява не слишком ржавая ...

static bool isFib(int x) {
    int a=0;
    int b=1;
    int f=1;
    while (b < x){
        f = a + b;
        a = b;
        b = f;
    }
    return x == f;
}

Пытаясь использовать уже написанный вами код, я бы сначала предложил следующее, так как это простейшее решение (но не самое эффективное):

private static void main(string[] args)
{
    //This will determnine which numbers between 1 & 100 are in the fibonacci series
    //you can swop in code to read from console rather than 'i' being used from the for loop
    for (int i = 0; i < 100; i++)
    {
        bool result = isFib(1);

        if (result)
            System.out.println(i + " is in the Fib series.");

        System.out.println(result);
    }

}

private static bool isFib(int num)
{
    int counter = 0;

    while (true)
    {
        if (fib(counter) < num)
        {
            counter++;
            continue;
        }

        if (fib(counter) == num)
        {
            return true;
        }

        if (fib(counter) > num)
        {
            return false;
        }
    }
}

Я бы предложил более элегантное решение при генерации чисел Фибоначчи, которое использует рекурсию следующим образом:

public static long fib(int n) 
{
   if (n <= 1) 
      return n;
   else 
      return fib(n-1) + fib(n-2);
}

Для получения дополнительной информации читайте: http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers

Вы увидите, что есть несколько более эффективных способов проверить, принадлежит ли число к серии Фибоначчи, а именно: (5z ^ 2 + 4 или 5z ^ 2-4) = полный квадрат.

//(5z^2 + 4 or 5z^2 − 4) = a perfect square 
//perfect square = an integer that is the square of an integer
private static bool isFib(int num)
{
    double first = 5 * Math.pow((num), 2) + 4;
    double second = 5 * Math.pow((num), 2) - 4;

    return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}

private static bool isWholeNumber(double num)
{
    return num - Math.round(num) == 0;    
}

Я не знаю, существует ли фактическая формула, которую вы можете применить к пользовательскому вводу, однако вы можете сгенерировать последовательность Фибоначчи и сравнить ее с пользовательским вводом, пока она не станет меньше, чем последнее сгенерированное число.

int userInput = n;
int a = 1, b = 1;

while (a < n) {
  if (a == n)
    return true;

  int next = a + b;
  b = a;
  a = next;
}

return false;

Вы можете сделать это двумя способами: рекурсивным и математическим. рекурсивный способ начать генерировать последовательность Фибоначчи, пока вы не нажмете число или не передадите его математическим способом, красиво описанным здесь ... http://www.physicsforums.com/showthread.php?t=252798

удачи.

Рассмотрим последовательность чисел Фибоначчи 1,1,2,3,5,8,13,21 и т. Д. Желательно построить 3 стека каждая емкостью 10, содержащих числа из приведенных выше последовательностей, следующим образом:

Стек 1: первые 10 чисел последовательности. Стек 2: первые 10 простых чисел из последовательности. Стек 3: первые 10 непростых чисел последовательности.

(i) Дайте алгоритм блок-схемы (ii) Напишите программу (на BASIC, C ++ или Java) для реализации этого.

Вывод: По мере того, как выполняются операции со стеком, вы должны отображать в любой удобной форме 3 стека вместе со значениями, хранящимися в них.

Определение числа по шкале Фибоначчи по формуле:

public static boolean isNumberFromFibonacciSequence(int num){

    if (num == 0 || num == 1){
        return true;
    }

    else {
        //5n^2 - 4 OR 5n^2 + 4 should be perfect squares
        return isPerfectSquare( 5*num*num - 4) || isPerfectSquare(5*num*num - 4);
    }
}

private static boolean isPerfectSquare(int num){
        double sqrt = Math.sqrt(num);
        return sqrt * sqrt == num;
}

Думал, что это просто, пока мне не пришлось ломать голову над этим несколько минут. Это сильно отличается от генерации последовательности Фибоначчи. Эта функция возвращает 1, если это значение Фибоначи, или 0, если нет.

public static int isFibonacci (int n){
  int isFib = 0;
  int a = 0, b = 0, c = a + b; // set up the initial values
  do 
   {
    a = b;
    b = c;
    c = a + b;
    if (c == n)
    isFib = 1;
    } while (c<=n && isFin == 0)
  return isFib;
}

public static void main(String [] args){
  System.out.println(isFibonacci(89));
}