Рубрики

Наибольшее подмножество, все элементы которого являются числами Фибоначчи

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

Спросил в Facebook

Примеры :

Input : arr[] = {1, 4, 3, 9, 10, 13, 7};
Output : subset[] = {1, 3, 13}
The output three numbers are Fibonacci
numbers.

Input  : arr[] = {0, 2, 8, 5, 2, 1, 4, 
                  13, 23};
Output : subset[] = {0, 2, 8, 5, 2, 1, 
                    13, 23}

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

Ниже приведено эффективное решение, основанное на хешировании.

  1. Найти максимум в массиве
  2. Сгенерируйте числа Фибоначчи до максимума и сохраните их в хэш-таблице.
  3. Снова просмотрите массив, если число присутствует в хеш-таблице, затем добавьте его к результату.

C ++

// C ++ программа для поиска наибольшего подмножества Фибоначчи
#include<bits/stdc++.h>

using namespace std;

  
// Печатает наибольшее подмножество массива которого
// все элементы являются числами Фибоначчи

void findFibSubset(int arr[], int n)

{

    // Найти максимальный элемент в arr []

    int max = *std::max_element(arr, arr+n);

  

    // Генерируем все числа Фибоначчи до

    // max и сохраняем их в хеше.

    int a = 0, b = 1;

    unordered_set<int> hash;

    hash.insert(a);

    hash.insert(b);

    while (b < max)

    {

        int c = a + b;

        a = b;

        b = c;

        hash.insert(b);

    }

  

    // Npw перебрать все числа и

    // быстро проверяем Фибоначчи, используя

    // хеш

    for (int i=0; i<n; i++)

        if (hash.find(arr[i]) != hash.end())

            printf("%d ", arr[i]);

}

  
// Код драйвера

int main()

{

    int arr[] = {4, 2, 8, 5, 20, 1, 40, 13, 23};

    int n = sizeof(arr)/sizeof(arr[0]);

    findFibSubset(arr, n);

    return 0;

}

Джава

// Java-программа для поиска
// наибольшее подмножество Фибоначчи

import java.util.*;

  

class GFG

{

    // Печатает наибольшее подмножество массива которого

    // все элементы являются числами Фибоначчи

    public static void findFibSubset(Integer[] x)

    {

        Integer max = Collections.max(Arrays.asList(x));

        List<Integer> fib = new ArrayList<Integer>(); 

        List<Integer> result = new ArrayList<Integer>();

          

        // Генерируем все числа Фибоначчи

        // до максимума и сохраняем их

        Integer a = 0;

        Integer b = 1;

        while (b < max){

            Integer c = a + b;

            a=b;

            b=c;

            fib.add(c);

        }

      

        // Теперь перебираем все числа и

        // быстро проверяем Фибоначчи

        for (Integer i = 0; i < x.length; i++){

        if(fib.contains(x[i])){

            result.add(x[i]); 

        }     

        }

        System.out.println(result);

    }

  

    // Код драйвера

    public static void main(String args[])

    {

        Integer[] a = {4, 2, 8, 5, 20, 1, 40, 13, 23};

        findFibSubset(a);

    }

}

  
// Этот код предоставлен prag93

python3

# python3 программа для поиска наибольшего подмножества Фибоначчи

   
# Печатает наибольшее подмножество массива которого
# все элементы являются числами Фибоначчи

def findFibSubset(arr, n):

  

    # Найти максимальный элемент в arr []

    m= max(arr)

   

    # Генерация всех чисел Фибоначчи до

    # max и храните их в хеше.

    a = 0

    b = 1

    hash = []

    hash.append(a)

    hash.append(b)

    while (b < m):

      

        c = a + b

        a = b

        b = c

        hash.append(b)

      

   

    # Npw перебрать все числа и

    # быстро проверить Фибоначчи, используя

    # хеш

    for i in range (n):

        if arr[i] in hash :

            print( arr[i],end=" ")

   
# Код драйвера

if __name__ == "__main__":

  

    arr = [4, 2, 8, 5, 20, 1, 40, 13, 23]

    n = len(arr)

    findFibSubset(arr, n)

C #

// C # программа для поиска
// наибольшее подмножество Фибоначчи

using System;

using System.Linq;

using System.Collections.Generic; 

      

class GFG

{

    // Печатает наибольшее подмножество массива которого

    // все элементы являются числами Фибоначчи

    public static void findFibSubset(int[] x)

    {

        int max = x.Max();

        List<int> fib = new List<int>(); 

        List<int> result = new List<int>();

          

        // Генерируем все числа Фибоначчи

        // до максимума и сохраняем их

        int a = 0;

        int b = 1;

        while (b < max)

        {

            int c = a + b;

            a = b;

            b = c;

            fib.Add(c);

        }

      

        // Теперь перебираем все числа и

        // быстро проверяем Фибоначчи

        for (int i = 0; i < x.Length; i++)

        {

            if(fib.Contains(x[i]))

            {

                result.Add(x[i]); 

            }     

        }

        foreach(int i in result)

            Console.Write(i + " ");

    }

  

    // Код драйвера

    public static void Main(String []args)

    {

        int[] a = {4, 2, 8, 5, 20, 1, 40, 13, 23};

        findFibSubset(a);

    }

}

  
// Этот код предоставлен PrinciRaj1992


Выход:

2 8 5 1 13 

Ссылка :
https://www.careercup.com/question?id=5154130839470080

Эта статья предоставлена DANISH_RAZA . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Наибольшее подмножество, все элементы которого являются числами Фибоначчи

0.00 (0%) 0 votes