雷卡曼序列-yiteyi-C++库

给定一个整数n.打印雷卡曼序列 . 例如：

null

Input : n = 6Output : 0, 1, 3, 6, 2, 7Input  : n = 17Output : 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++ program to print n-th number in Recaman's                       
                         // sequence                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Prints first n terms of Recaman sequence                       
                         int                                     recaman(                                     int                                     n)                       
                         {                       
                                                 // Create an array to store terms                       
                                                 int                                     arr[n];                       
           
                                                 // First term of the sequence is always 0                       
                                                 arr[0] = 0;                       
                                                 printf                                     (                                     "%d, "                                     , arr[0]);                       
           
                                                 // Fill remaining terms using recursive                       
                                                 // formula.                       
                                                 for                                     (                                     int                                     i=1; i< n; i++)                       
                                                 {                       
                                                 int                                     curr = arr[i-1] - i;                       
                                                 int                                     j;                       
                                                 for                                     (j = 0; j < i; j++)                       
                                                 {                       
                                                 // If arr[i-1] - i is negative or                       
                                                 // already exists.                       
                                                 if                                     ((arr[j] == curr) || curr < 0)                       
                                                 {                       
                                                 curr = arr[i-1] + i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 arr[i] = curr;                       
                                                 printf                                     (                                     "%d, "                                     , arr[i]);                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 17;                       
                                                 recaman(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print n-th number in Recaman's                       
                         // sequence                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                                   
                                                 // Prints first n terms of Recaman sequence                       
                                                 static                                     void                                     recaman(                                     int                                     n)                       
                                                 {                       
                                                 // Create an array to store terms                       
                                                 int                                     arr[] =                                     new                                     int                                     [n];                       
                                   
                                                 // First term of the sequence is always 0                       
                                                 arr[                                     0                                     ] =                                     0                                     ;                       
                                                 System.out.print(arr[                                     0                                     ]+                                     " ,"                                     );                       
                                   
                                                 // Fill remaining terms using recursive                       
                                                 // formula.                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; i++)                       
                                                 {                       
                                                 int                                     curr = arr[i -                                     1                                     ] - i;                       
                                                 int                                     j;                       
                                                 for                                     (j =                                     0                                     ; j < i; j++)                       
                                                 {                       
                                                 // If arr[i-1] - i is negative or                       
                                                 // already exists.                       
                                                 if                                     ((arr[j] == curr) || curr <                                     0                                     )                       
                                                 {                       
                                                 curr = arr[i -                                     1                                     ] + i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 arr[i] = curr;                       
                                                 System.out.print(arr[i]+                                     ", "                                     );                       
                                   
                                                 }                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     n =                                     17                                     ;                       
                                                 recaman(n);                       
           
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m                       

Python 3

                         # Python 3 program to print n-th                       
                         # number in Recaman's sequence                       
           
                         # Prints first n terms of Recaman                       
                         # sequence                       
                         def                                     recaman(n):                       
           
                                                 # Create an array to store terms                       
                                                 arr                                     =                                     [                                     0                                     ]                                     *                                     n                       
           
                                                 # First term of the sequence                       
                                                 # is always 0                       
                                                 arr[                                     0                                     ]                                     =                                     0                       
                                                 print                                     (arr[                                     0                                     ], end                                     =                                     ", "                                     )                       
           
                                                 # Fill remaining terms using                       
                                                 # recursive formula.                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
                                   
                                                 curr                                     =                                     arr[i                                     -                                     1                                     ]                                     -                                     i                       
                                                 for                                     j                                     in                                     range                                     (                                     0                                     , i):                       
                                   
                                                 # If arr[i-1] - i is                       
                                                 # negative or already                       
                                                 # exists.                       
                                                 if                                     ((arr[j]                                     =                                     =                                     curr)                                     or                                     curr <                                     0                                     ):                       
                                                 curr                                     =                                     arr[i                                     -                                     1                                     ]                                     +                                     i                       
                                                 break                       
                                   
                                                 arr[i]                                     =                                     curr                       
                                                 print                                     (arr[i], end                                     =                                     ", "                                     )                       
           
                         # Driver code                       
                         n                                     =                                     17                       
           
                         recaman(n)                       
           
                         # This code is contributed by Smitha.                       

C#

                         // C# program to print n-th number in Recaman's                       
                         // sequence                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Prints first n terms of Recaman sequence                       
                                                 static                                     void                                     recaman(                                     int                                     n)                       
                                                 {                       
                                                 // Create an array to store terms                       
                                                 int                                     []arr =                                     new                                     int                                     [n];                       
                                   
                                                 // First term of the sequence is always 0                       
                                                 arr[0] = 0;                       
                                                 Console.Write(arr[0]+                                     " ,"                                     );                       
                                   
                                                 // Fill remaining terms using recursive                       
                                                 // formula.                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 {                       
                                                 int                                     curr = arr[i - 1] - i;                       
                                                 int                                     j;                       
                                                 for                                     (j = 0; j < i; j++)                       
                                                 {                       
                                                 // If arr[i-1] - i is negative or                       
                                                 // already exists.                       
                                                 if                                     ((arr[j] == curr) || curr < 0)                       
                                                 {                       
                                                 curr = arr[i - 1] + i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 arr[i] = curr;                       
                                                 Console.Write(arr[i]+                                     ", "                                     );                       
                                   
                                                 }                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     n = 17;                       
                                                 recaman(n);                       
           
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to print n-th                       
                         // number in Recaman's sequence                       
           
                         // Prints first n terms                       
                         // of Recaman sequence                       
                         function                                     recaman(                                     $n                                     )                       
                         {                       
                                   
                                                 // First term of the                       
                                                 // sequence is always 0                       
                                                 $arr                                     [0] = 0;                       
                                                 echo                                     $arr                                     [0],                                     ", "                                     ;                       
           
                                                 // Fill remaining terms                       
                                                 // using recursive formula.                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 $curr                                     =                                     $arr                                     [                                     $i                                     - 1] -                                     $i                                     ;                       
                                                 $j                                     ;                       
                                                 for                                     (                                     $j                                     = 0;                                     $j                                     <                                     $i                                     ;                                     $j                                     ++)                       
                                                 {                       
                                   
                                                 // If arr[i-1] - i                       
                                                 // is negative or                       
                                                 // already exists.                       
                                                 if                                     ((                                     $arr                                     [                                     $j                                     ] ==                                     $curr                                     ) ||                                     $curr                                     < 0)                       
                                                 {                       
                                                 $curr                                     =                                     $arr                                     [                                     $i                                     -1] +                                     $i                                     ;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 $arr                                     [                                     $i                                     ] =                                     $curr                                     ;                       
                                                 echo                                     $arr                                     [                                     $i                                     ],                                     ", "                                     ;                       
                                                 }                       
                         }                       
           
                                                 // Driver Code                       
                                                 $n                                     = 17;                       
                                                 recaman(                                     $n                                     );                       
                                   
                         // This code is contributed by Ajit                       
                         ?>                       

Javascript

                         <script>                       
           
                                                 // Javascript program to print                       
                                                 // n-th number in Recaman's sequence                       
                                   
                                                 // Prints first n terms of Recaman sequence                       
                                                 function                                     recaman(n)                       
                                                 {                       
                                                 // Create an array to store terms                       
                                                 let arr =                                     new                                     Array(n);                       
                                   
                                                 // First term of the sequence is always 0                       
                                                 arr[0] = 0;                       
                                                 document.write(arr[0]+                                     " ,"                                     );                       
                                   
                                                 // Fill remaining terms using recursive                       
                                                 // formula.                       
                                                 for                                     (let i = 1; i < n; i++)                       
                                                 {                       
                                                 let curr = arr[i - 1] - i;                       
                                                 let j;                       
                                                 for                                     (j = 0; j < i; j++)                       
                                                 {                       
                                                 // If arr[i-1] - i is negative or                       
                                                 // already exists.                       
                                                 if                                     ((arr[j] == curr) || curr < 0)                       
                                                 {                       
                                                 curr = arr[i - 1] + i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 arr[i] = curr;                       
                                                 document.write(arr[i]+                                     ", "                                     );                       
                                   
                                                 }                       
                                                 }                       
                                   
                                                 let n = 17;                       
                                                 recaman(n);                       
                                   
                         </script>                       

输出：

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++ program to print n-th number in Recaman's                       
                         // sequence                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Prints first n terms of Recaman sequence                       
                         void                                     recaman(                                     int                                     n)                       
                         {                       
                                                 if                                     (n <= 0)                       
                                                 return                                     ;                       
           
                                                 // Print first term and store it in a hash                       
                                                 printf                                     (                                     "%d, "                                     , 0);                       
                                                 unordered_set<                                     int                                     > s;                       
                                                 s.insert(0);                       
           
                                                 // Print remaining terms using recursive                       
                                                 // formula.                       
                                                 int                                     prev = 0;                       
                                                 for                                     (                                     int                                     i=1; i< n; i++)                       
                                                 {                       
                                                 int                                     curr = prev - i;                       
           
                                                 // If arr[i-1] - i is negative or                       
                                                 // already exists.                       
                                                 if                                     (curr < 0 || s.find(curr) != s.end())                       
                                                 curr = prev + i;                       
           
                                                 s.insert(curr);                       
           
                                                 printf                                     (                                     "%d, "                                     , curr);                       
                                                 prev = curr;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 17;                       
                                                 recaman(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print n-th number                       
                         // in Recaman's sequence                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Prints first n terms of Recaman sequence                       
                         static                                     void                                     recaman(                                     int                                     n)                       
                         {                       
                                                 if                                     (n <=                                     0                                     )                       
                                                 return                                     ;                       
           
                                                 // Print first term and store it in a hash                       
                                                 System.out.printf(                                     "%d, "                                     ,                                     0                                     );                       
                                                 HashSet<Integer> s =                                     new                                     HashSet<Integer>();                       
                                                 s.add(                                     0                                     );                       
           
                                                 // Print remaining terms using                       
                                                 // recursive formula.                       
                                                 int                                     prev =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i< n; i++)                       
                                                 {                       
                                                 int                                     curr = prev - i;                       
           
                                                 // If arr[i-1] - i is negative or                       
                                                 // already exists.                       
                                                 if                                     (curr <                                     0                                     || s.contains(curr))                       
                                                 curr = prev + i;                       
           
                                                 s.add(curr);                       
           
                                                 System.out.printf(                                     "%d, "                                     , curr);                       
                                                 prev = curr;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     n =                                     17                                     ;                       
                                                 recaman(n);                       
                         }                       
                         }                       
           
                         // This code is contributed by Rajput-Ji                       

Python3

                         # Python3 program to print n-th number in                       
                         # Recaman's sequence                       
           
                         # Prints first n terms of Recaman sequence                       
                         def                                     recaman(n):                       
           
                                                 if                                     (n <                                     =                                     0                                     ):                       
                                                 return                       
           
                                                 # Print first term and store it in a hash                       
                                                 print                                     (                                     0                                     ,                                     ","                                     , end                                     =                                     '')                       
                                                 s                                     =                                     set                                     ([])                       
                                                 s.add(                                     0                                     )                       
           
                                                 # Print remaining terms using recursive                       
                                                 # formula.                       
                                                 prev                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
           
                                                 curr                                     =                                     prev                                     -                                     i                       
           
                                                 # If arr[i-1] - i is negative or                       
                                                 # already exists.                       
                                                 if                                     (curr <                                     0                                     or                                     curr                                     in                                     s):                       
                                                 curr                                     =                                     prev                                     +                                     i                       
           
                                                 s.add(curr)                       
           
                                                 print                                     (curr,                                     ","                                     , end                                     =                                     '')                       
                                                 prev                                     =                                     curr                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 n                                     =                                     17                       
                                                 recaman(n)                       
           
                         # This code is contributed by                       
                         # Sanjit_Prasad                       

C#

                         // C# program to print n-th number                       
                         // in Recaman's sequence                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Prints first n terms of Recaman sequence                       
                         static                                     void                                     recaman(                                     int                                     n)                       
                         {                       
                                                 if                                     (n <= 0)                       
                                                 return                                     ;                       
           
                                                 // Print first term and store it in a hash                       
                                                 Console.Write(                                     "{0}, "                                     , 0);                       
                                                 HashSet<                                     int                                     > s =                                     new                                     HashSet<                                     int                                     >();                       
                                                 s.Add(0);                       
           
                                                 // Print remaining terms using                       
                                                 // recursive formula.                       
                                                 int                                     prev = 0;                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 {                       
                                                 int                                     curr = prev - i;                       
           
                                                 // If arr[i-1] - i is negative or                       
                                                 // already exists.                       
                                                 if                                     (curr < 0 || s.Contains(curr))                       
                                                 curr = prev + i;                       
           
                                                 s.Add(curr);                       
           
                                                 Console.Write(                                     "{0}, "                                     , curr);                       
                                                 prev = curr;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 int                                     n = 17;                       
                                                 recaman(n);                       
                         }                       
                         }                       
           
                         // This code is contributed by Princi Singh                       

PHP

                         <?php                       
                         // PHP program to print n-th number in                       
                         // Recaman's sequence                       
           
                         // Prints first n terms of Recaman sequence                       
                         function                                     recaman(                                     $n                                     )                       
                         {                       
                                                 if                                     (                                     $n                                     <= 0)                       
                                                 return                                     ;                       
           
                                                 // Print first term and store                       
                                                 // it in a hash                       
                                                 print                                     (                                     "0, "                                     );                       
                                                 $s                                     =                                     array                                     ();                       
                                                 array_push                                     (                                     $s                                     , 0);                       
           
                                                 // Print remaining terms using recursive                       
                                                 // formula.                       
                                                 $prev                                     = 0;                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 $curr                                     =                                     $prev                                     -                                     $i                                     ;                       
           
                                                 // If arr[i-1] - i is negative or                       
                                                 // already exists.                       
                                                 if                                     (                                     $curr                                     < 0                                     or                                     in_array(                                     $curr                                     ,                                     $s                                     ))                       
                                                 $curr                                     =                                     $prev                                     +                                     $i                                     ;                       
           
                                                 array_push                                     (                                     $s                                     ,                                     $curr                                     );                       
           
                                                 print                                     (                                     $curr                                     .                                     ", "                                     );                       
                                                 $prev                                     =                                     $curr                                     ;                       
                                                 }                       
                                   
                         }                       
           
                         // Driver code                       
                         $n                                     = 17;                       
                         recaman(                                     $n                                     );                       
           
                         // This code is contributed by chandan_jnu                       
                         ?>                       

Javascript

                         <script>                       
           
                         //  Javascript program to print n-th number                       
                         // in Recaman's sequence                       
           
                         // Prints first n terms of Recaman sequence                       
                         function                                     recaman(n)                       
                         {                       
                                                 if                                     (n <= 0)                       
                                                 return                                     ;                       
                                   
                                                 // Print first term and store it in a hash                       
                                                 document.write(0 +                                     ", "                                     );                       
                                                 let s =                                     new                                     Set();                       
                                                 s.add(0);                       
                                   
                                                 // Print remaining terms using                       
                                                 // recursive formula.                       
                                                 let prev = 0;                       
                                                 for                                     (let i = 1; i< n; i++)                       
                                                 {                       
                                                 let curr = prev - i;                       
                                   
                                                 // If arr[i-1] - i is negative or                       
                                                 // already exists.                       
                                                 if                                     (curr < 0 || s.has(curr))                       
                                                 curr = prev + i;                       
                                   
                                                 s.add(curr);                       
                                   
                                                 document.write(curr +                                     ", "                                     );                       
                                                 prev = curr;                       
                                                 }                       
                         }                       
                                   
                                                 // Driver code                       
                                   
                                                 let n = 17;                       
                                                 recaman(n);                       
                                   
                         </script>                       

输出：

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

时间复杂性： O（n） 辅助空间： O（n）本文由 基什莱·维尔马 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章