Рубрики

Последовательность Recaman

Математика, Рекурсия, Хеш

Дано целое число n. Выведите первые n элементов последовательности Рекамана .

Примеры:

Input : n = 6
Output : 0, 1, 3, 6, 2, 7

Input  : n = 17
Output : 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 
         11, 22, 10, 23, 9, 24, 8

В основном это функция с доменом и содоменом в виде натуральных чисел и 0. Она рекурсивно определяется следующим образом:
В частности, пусть a (n) обозначает (n + 1) -й член. (0 уже там).
Правило гласит:

a(0) = 0,
if n > 0 and the number is not 
   already included in the sequence,
     a(n) = a(n - 1) - n 
else 
     a(n) = a(n-1) + n.

Ниже приведена простая реализация, где мы храним все n порядковых номеров Recaman в массиве. Мы вычисляем следующее число, используя упомянутую выше рекурсивную формулу.

C ++

// C ++ программа для печати n-го числа в Recaman's
// последовательность
#include <bits/stdc++.h>

using namespace std;

  
// Печатает первые n членов последовательности Рекамана

int recaman(int n)

{

    // Создать массив для хранения терминов

    int arr[n];

  

    // Первый член последовательности всегда равен 0

    arr[0] = 0;

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

  

    // Заполняем оставшиеся термины рекурсивным

    // формула

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

    {

        int curr = arr[i-1] - i;

        int j;

        for (j = 0; j < i; j++)

        {

            // Если arr [i-1] - i отрицателен или

            // уже существует.

            if ((arr[j] == curr) || curr < 0)

            {

                curr = arr[i-1] + i;

                break;

            }

        }

  

        arr[i] = curr;

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

    }

}

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

int main()

{

    int n = 17;

    recaman(n);

    return 0;

}

Джава

// Java-программа для печати n-го числа в Recaman's
// последовательность

import java.io.*;

  

class GFG {

      

    // Печатает первые n членов последовательности Рекамана

    static void recaman(int n)

    {

        // Создать массив для хранения терминов

        int arr[] = new int[n];

      

        // Первый член последовательности всегда равен 0

        arr[0] = 0;

        System.out.print(arr[0]+" ,");

      

        // Заполняем оставшиеся термины рекурсивным

        // формула

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

        {

            int curr = arr[i - 1] - i;

            int j;

            for (j = 0; j < i; j++)

            {

                // Если arr [i-1] - i отрицателен или

                // уже существует.

                if ((arr[j] == curr) || curr < 0)

                {

                    curr = arr[i - 1] + i;

                    break;

                }

            }

      

            arr[i] = curr;

            System.out.print(arr[i]+", ");

              

        }

    }

      

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

    public static void main (String[] args) 

    {

        int n = 17;

        recaman(n);

  

    }

}

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

Python 3

# Python 3 программа для печати n-го
# номер в последовательности Recaman

  
# Печатает первые n терминов Recaman
# последовательность

def recaman(n):

  

    # Создать массив для хранения терминов

    arr = [0] * n

  

    # Первый член последовательности

    # всегда 0

    arr[0] = 0

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

  

    # Заполните оставшиеся условия, используя

    # рекурсивная формула.

    for i in range(1, n):

      

        curr = arr[i-1] - i

        for j in range(0, i):

          

            # Если обр [я-1] - я

            # отрицательный или уже

            # существуют.

            if ((arr[j] == curr) or curr < 0):

                curr = arr[i-1] + i

                break

              

        arr[i] = curr

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

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

n = 17

  
recaman(n)

  
# Этот код предоставлен Смитой.

C #

// C # программа для печати n-го числа в Recaman's
// последовательность

using System;

  

class GFG {

      

    // Печатает первые n членов последовательности Рекамана

    static void recaman(int n)

    {

        // Создать массив для хранения терминов

        int []arr = new int[n];

      

        // Первый член последовательности всегда равен 0

        arr[0] = 0;

        Console.Write(arr[0]+" ,");

      

        // Заполняем оставшиеся термины рекурсивным

        // формула

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

        {

            int curr = arr[i - 1] - i;

            int j;

            for (j = 0; j < i; j++)

            {

                // Если arr [i-1] - i отрицателен или

                // уже существует.

                if ((arr[j] == curr) || curr < 0)

                {

                    curr = arr[i - 1] + i;

                    break;

                }

            }

      

            arr[i] = curr;

        Console.Write(arr[i]+", ");

              

        }

    }

      

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

    public static void Main () 

    {

        int n = 17;

        recaman(n);

  

    }

}

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

PHP

<?php
// PHP-программа для печати n-го
// номер в последовательности Recaman

  
// Печатает первые n членов
// Рекамановской последовательности

function recaman($n)

{

      

    // Первый член

    // последовательность всегда 0

    $arr[0] = 0;

    echo $arr[0], ", ";

  

    // Заполнить оставшиеся условия

    // используя рекурсивную формулу.

    for ($i = 1; $i < $n; $i++)

    {

            $curr = $arr[$i - 1] - $i;

            $j;

        for ($j = 0; $j < $i; $j++)

        {

              

            // Если arr [i-1] - i

            // отрицательно или

            // уже существует.

            if (($arr[$j] == $curr) || $curr < 0)

            {

                $curr = $arr[$i-1] + $i;

                break;

            }

        }

  

        $arr[$i] = $curr;

        echo $arr[$i], ", ";

    }

}

  

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

    $n = 17;

    recaman($n);

      
// Этот код предоставлен Ajit
?>


Выход:

0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8,

Сложность времени: O (n 2 )
Вспомогательное пространство: O (n)

Оптимизации:
Мы можем использовать хеширование для хранения ранее вычисленных значений и заставить эту программу работать за O (n) времени.

C ++

// C ++ программа для печати n-го числа в Recaman's
// последовательность
#include <bits/stdc++.h>

using namespace std;

  
// Печатает первые n членов последовательности Рекамана

void recaman(int n)

{

    if (n <= 0)

      return;

  

    // Распечатать первый член и сохранить его в хеше

    printf("%d, ", 0);

    unordered_set<int> s;

    s.insert(0);

  

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

    // формула

    int prev = 0;

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

    {

        int curr = prev - i;

  

        // Если arr [i-1] - i отрицателен или

        // уже существует.

        if (curr < 0 || s.find(curr) != s.end())

           curr = prev + i;

  

        s.insert(curr);

  

        printf("%d, ", curr);

        prev = curr;

    }

}

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

int main()

{

    int n = 17;

    recaman(n);

    return 0;

}

Джава

// Java-программа для печати n-го числа
// в последовательности Recaman

import java.util.*;

  

class GFG

{

  
// Печатает первые n членов последовательности Рекамана

static void recaman(int n)

{

    if (n <= 0)

    return;

  

    // Распечатать первый член и сохранить его в хеше

    System.out.printf("%d, ", 0);

    HashSet<Integer> s = new HashSet<Integer>();

    s.add(0);

  

    // Распечатать остальные термины используя

    // рекурсивная формула.

    int prev = 0;

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

    {

        int curr = prev - i;

  

        // Если arr [i-1] - i отрицателен или

        // уже существует.

        if (curr < 0 || s.contains(curr))

            curr = prev + i;

  

        s.add(curr);

  

        System.out.printf("%d, ", curr);

        prev = curr;

    }

}

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

public static void main(String[] args)

{

    int n = 17;

    recaman(n);

}
}

  
// Этот код предоставлен Rajput-Ji

python3

# Программа Python3 для печати n-го числа в
# Recaman's sequence

  
# Печатает первые n членов последовательности Рекамана

def recaman(n):

  

    if(n <= 0):

        return

  

    # Напечатайте первый член и сохраните его в хеше

    print(0, ",", end='')

    s = set([])

    s.add(0)

  

    # Распечатать оставшиеся термины, используя рекурсив

    # формула.

    prev = 0

    for i in range(1, n):

  

        curr = prev - i

  

        # Если arr [i-1] - я отрицательный или

        # уже существует.

        if(curr < 0 or curr in s):

            curr = prev + i

  

        s.add(curr)

  

        print(curr, ",", end='')

        prev = curr

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

if __name__=='__main__':

    n = 17

    recaman(n)

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

C #

// C # программа для печати n-го числа
// в последовательности Recaman

using System;

using System.Collections.Generic;

  

class GFG

{

  
// Печатает первые n членов последовательности Рекамана

static void recaman(int n)

{

    if (n <= 0)

    return;

  

    // Распечатать первый член и сохранить его в хеше

    Console.Write("{0}, ", 0);

    HashSet<int> s = new HashSet<int>();

    s.Add(0);

  

    // Распечатать остальные термины используя

    // рекурсивная формула.

    int prev = 0;

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

    {

        int curr = prev - i;

  

        // Если arr [i-1] - i отрицателен или

        // уже существует.

        if (curr < 0 || s.Contains(curr))

            curr = prev + i;

  

        s.Add(curr);

  

        Console.Write("{0}, ", curr);

        prev = curr;

    }

}

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

public static void Main(String[] args)

{

    int n = 17;

    recaman(n);

}
}

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

PHP

<?php
// PHP-программа для печати n-го числа в
// последовательность Recaman

  
// Печатает первые n членов последовательности Рекамана

function recaman($n) 

{

    if($n <= 0) 

        return;

  

    // Распечатать первый термин и сохранить

    // это в хэше

    print("0, "); 

    $s = array(); 

    array_push($s, 0); 

  

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

    // формула

    $prev = 0;

    for ($i = 1; $i < $n; $i++)

    { 

        $curr = $prev - $i; 

  

        // Если arr [i-1] - i отрицателен или

        // уже существует.

        if($curr < 0 or in_array($curr, $s)) 

            $curr = $prev + $i; 

  

        array_push($s, $curr); 

  

        print($curr.", "); 

        $prev = $curr;

    }

          
}

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

$n = 17;

recaman($n); 

  
// Этот код предоставлен chandan_jnu
?>


Выход:

0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8,

Сложность времени: O (n)
Вспомогательное пространство: O (n)

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

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

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

Последовательность Recaman

0.00 (0%) 0 votes