Рубрики

N-е XOR число Фибоначчи

Конкурентное программирование, Математика, Немного магии

Даны три целых числа a , b и N, где a и b — первые два члена ряда XOR Фибоначчи, и задача состоит в том, чтобы найти N- й член.
N-й член ряда XOR Фибоначчи определяется как F (N) = F (N — 1) ^ F (N — 2), где ^ — побитовое XOR.

Примеры:

Input: a = 1, b = 2, N = 5
Output: 3
F(0) = 1
F(1) = 2
F(2) = 1 ^ 2 = 3
F(3) = 2 ^ 3 = 1
F(4) = 1 ^ 3 = 2
F(5) = 1 ^ 2 = 3

Input: a = 5, b = 11, N = 1000001
Output: 14

Подход: так как, a ^ a = 0, и дано, что

F(0) = a and F(1) = b
Now, F(2) = F(0) ^ F(1) = a ^ b
And, F(3) = F(1) ^ F(2) = b ^ (a ^ b) = a
F(4) = a ^ b ^ a = b
F(5) = a ^ b
F(6) = a
F(7) = b
F(8) = a ^ b
…

Можно заметить, что ответ повторяется после каждых 3 цифр. Таким образом, ответ F (N% 3), где F (0) = a, F (1) = b и F (2) = a ^ b .

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата n-го числа XOR по Фибоначчи

int nthXorFib(int n, int a, int b)

{

    if (n == 0)

        return a;

    if (n == 1)

        return b;

    if (n == 2)

        return (a ^ b);

  

    return nthXorFib(n % 3, a, b);

}

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

int main()

{

    int a = 1, b = 2, n = 10;

  

    cout << nthXorFib(n, a, b);

  

    return 0;

}

Джава

// Java реализация вышеуказанного подхода

class GFG

{

          

    // Функция для возврата

    // n-е число XOR по Фибоначчи

    static int nthXorFib(int n, int a, int b) 

    { 

        if (n == 0) 

            return a; 

        if (n == 1) 

            return b; 

        if (n == 2) 

            return (a ^ b); 

      

        return nthXorFib(n % 3, a, b); 

    } 

      

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

    public static void main (String[] args) 

    { 

        int a = 1, b = 2, n = 10; 

      

        System.out.println(nthXorFib(n, a, b)); 

    } 

}

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

python3

# Python3 реализация подхода

  
# Функция для возврата
# -е XOR число Фибоначчи

def nthXorFib(n, a, b):

    if n == 0 : 

        return a 

    if n == 1 : 

        return b 

    if n == 2 : 

        return a ^ b 

  

    return nthXorFib(n % 3, a, b) 

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

a = 1

b = 2

n = 10

print(nthXorFib(n, a, b)) 

  
# Этот код предоставлен divyamohan123

C #

// C # реализация вышеуказанного подхода

using System;

      

class GFG

{

          

    // Функция для возврата

    // n-е число XOR по Фибоначчи

    static int nthXorFib(int n, int a, int b) 

    { 

        if (n == 0) 

            return a; 

        if (n == 1) 

            return b; 

        if (n == 2) 

            return (a ^ b); 

      

        return nthXorFib(n % 3, a, b); 

    } 

      

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

    public static void Main (String[] args) 

    { 

        int a = 1, b = 2, n = 10; 

      

        Console.WriteLine(nthXorFib(n, a, b)); 

    } 

}

  
// Этот код предоставлен Принчи Сингхом

Выход:

2

Сложность времени: O (1)

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

N-е XOR число Фибоначчи

0.00 (0%) 0 votes