La secuencia de Newman-Conway es la que genera la siguiente secuencia entera.
1 1 2 2 3 4 4 4 5 6 7 7…
En términos matemáticos, la secuencia P(n) de los números de Newman-Conway se define por la relación de recurrencia
P(n) = P(P(n - 1)) + P(n - P(n - 1))
con valores semilla P(1) = 1 y P(2) = 1
Dado un número n, imprima el n-ésimo número en la secuencia de Newman-Conway.
Ejemplos:
Input : n = 2 Output : 1 Input : n = 10 Output : 6
Método 1 (usar recursividad):
Un enfoque simple es la implementación recursiva directa de la relación de recurrencia anterior.
C++
// C++ program for n-th
// element of Newman-Conway Sequence
#include <bits/stdc++.h>
using namespace std;
// Recursive Function to find the n-th element
int sequence(int n)
{
if (n == 1 || n == 2)
return 1;
else
return sequence(sequence(n - 1))
+ sequence(n - sequence(n - 1));
}
// Driver Program
int main()
{
int n = 10;
cout << sequence(n);
return 0;
}
Java
// Java program to find nth
// element of Newman-Conway Sequence
import java.io.*;
class GFG {
// Recursion to find
// n-th element
static int sequence(int n)
{
if (n == 1 || n == 2)
return 1;
else
return sequence(sequence(n - 1))
+ sequence(n - sequence(n - 1));
}
// Driver Program
public static void main(String args[])
{
int n = 10;
System.out.println(sequence(n));
}
}
/*This code is contributed by Nikita Tiwari.*/
Python
# Recursive function to find the n-th # element of sequence def sequence(n): if n == 1 or n == 2: return 1 else: return sequence(sequence(n-1)) + sequence(n-sequence(n-1)); # Driver code def main(): n = 10 print sequence(n) if __name__ == '__main__': main()
C#
// C# program to find nth element
// of Newman-Conway Sequence
using System;
class GFG {
// Recursion to find
// n-th element
static int sequence(int n)
{
if (n == 1 || n == 2)
return 1;
else
return sequence(sequence(n - 1)) + sequence
(n - sequence(n - 1));
}
// Driver code
public static void Main()
{
int n = 10;
Console.Write(sequence(n));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program for n-th element
// of Newman-Conway Sequence
// Recursive Function to
// find the n-th element
function sequence($n)
{
if ($n == 1 || $n == 2)
return 1;
else
return sequence(sequence($n - 1))+
sequence($n - sequence($n - 1));
}
// Driver Code
$n = 10;
echo(sequence($n));
// This code is contributed by Ajit.
?>
Javascript
<script>
// JavaScript program to find nth
// element of Newman-Conway Sequence
// Recursion to find
// n-th element
function sequence(n)
{
if (n == 1 || n == 2)
return 1;
else
return sequence(sequence(n - 1)) +
sequence(n - sequence(n - 1));
}
// Driver code
let n = 10;
document.write(sequence(n));
// This code is contributed by souravghosh0416
</script>
Producción :
6
Método 2 (usar programación dinámica):
podemos evitar el trabajo repetido realizado en el método 1 almacenando los valores en la secuencia en una array.
C++
// C++ program to find the n-th element of
// Newman-Conway Sequence
#include <bits/stdc++.h>
using namespace std;
// Function to find the n-th element
int sequence(int n)
{
// Declare array to store sequence
int f[n + 1];
int i;
f[0] = 0;
f[1] = 1;
f[2] = 1;
for (i = 3; i <= n; i++)
f[i] = f[f[i - 1]] + f[i - f[i - 1]];
return f[n];
}
// Driver Program
int main()
{
int n = 10;
cout << sequence(n);
return 0;
}
Java
// JAVA Code for Newman-Conway Sequence
import java.util.*;
class GFG {
// Function to find the n-th element
static int sequence(int n)
{
// Declare array to store sequence
int f[] = new int[n + 1];
f[0] = 0;
f[1] = 1;
f[2] = 1;
int i;
for (i = 3; i <= n; i++)
f[i] = f[f[i - 1]] +
f[i - f[i - 1]];
return f[n];
}
/* Driver program to test above function */
public static void main(String[] args)
{
int n = 10;
System.out.println(sequence(n));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python
''' Python program to find the n-th element of
Newman-Conway Sequence'''
# To declare array import module array
import array
def sequence(n):
f = array.array('i', [0, 1, 1])
# To store values of sequence in array
for i in range(3, n + 1):
r = f[f[i-1]]+f[i-f[i-1]]
f.append(r);
return r
# Driver code
def main():
n = 10
print sequence(n)
if __name__ == '__main__':
main()
C#
// C# Code for Newman-Conway Sequence
using System;
class GFG {
// Function to find the n-th element
static int sequence(int n)
{
// Declare array to store sequence
int []f = new int[n + 1];
f[0] = 0;
f[1] = 1;
f[2] = 1;
int i;
for (i = 3; i <= n; i++)
f[i] = f[f[i - 1]] +
f[i - f[i - 1]];
return f[n];
}
// Driver Code
public static void Main()
{
int n = 10;
Console.Write(sequence(n));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to find the n-th element
// of Newman-Conway Sequence
// Function to find
// the n-th element
function sequence($n)
{
// Declare array to
// store sequence
$i;
$f[0] = 0;
$f[1] = 1;
$f[2] = 1;
for ($i = 3; $i <= $n; $i++)
$f[$i] = $f[$f[$i - 1]] +
$f[$i - $f[$i - 1]];
return $f[$n];
}
// Driver Code
$n = 10;
echo(sequence($n));
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript program to find the n-th element
// of Newman-Conway Sequence
// Function to find
// the n-th element
function sequence(n)
{
// Declare array to
// store sequence
let i;
let f = [];
f[0] = 0;
f[1] = 1;
f[2] = 1;
for (let i = 3; i <= n; i++)
f[i] = f[f[i - 1]] +
f[i - f[i - 1]];
return f[n];
}
// Driver Code
let n = 10;
document.write(sequence(n));
// This code is contributed by gfgking.
</script>
Producción :
6
Complejidad temporal : O(n)
Espacio auxiliar : O(n)
Referencias: https://archive.lib.msu.edu/crcmath/math/math/n/n078.htm
Publicación traducida automáticamente
Artículo escrito por NishuAggarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA