Programa para implementar la Conjetura de Collatz

Dado un entero positivo n, la tarea es encontrar si este número llega a 1 después de realizar las siguientes dos operaciones: 
 

  1. Si n es par, entonces n = n/2.
  2. Si n es impar, entonces n = 3*n + 1.
  3. Repita los pasos anteriores, hasta que se convierta en 1.

Por ejemplo, para n = 12, obtenemos la secuencia 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.
Ejemplos: 
 

Input : n = 4
Output : Yes

Input : n = 5
Output : Yes

La idea es simplemente seguir las reglas dadas y llamar recursivamente a la función con valores reducidos hasta que llegue a 1. Si se vuelve a ver un valor durante la recursión, entonces hay un ciclo y no podemos llegar a 1. En este caso, devolvemos falso. 
 

C++

// C++ program to implement Collatz Conjecture
#include<bits/stdc++.h>
using namespace std;
 
// Function to find if n reaches to 1 or not.
bool isToOneRec(int n, unordered_set<int> &s)
{
    if (n == 1)
        return true;
 
    // If there is a cycle formed, we can't r
    // reach 1.
    if (s.find(n) != s.end())
        return false;
     s.insert(n);//inserting elements to the s
 
    // If n is odd then pass n = 3n+1 else n = n/2
    return (n % 2)? isToOneRec(3*n + 1, s) :
                    isToOneRec(n/2, s);
}
 
// Wrapper over isToOneRec()
bool isToOne(int n)
{
   // To store numbers visited using recursive calls.
   unordered_set<int> s;
 
   return isToOneRec(n, s);
}
 
// Drivers code
int main()
{
    int n = 5;
    isToOne(n) ? cout << "Yes" : cout <<"No";
    return 0;
}

Java

// Java program to implement Collatz Conjecture
import java.util.*;
 
class GFG
{
 
    // Function to find if n reaches to 1 or not.
    static boolean isToOneRec(int n, HashSet<Integer> s)
    {
        if (n == 1)
        {
            return true;
        }
 
        // If there is a cycle formed, we can't r
        // reach 1.
        if (s.contains(n))
        {
            return false;
        }
 
        // If n is odd then pass n = 3n+1 else n = n/2
        return (n % 2 == 1) ? isToOneRec(3 * n + 1, s)
                : isToOneRec(n / 2, s);
    }
 
    // Wrapper over isToOneRec()
    static boolean isToOne(int n)
    {
        // To store numbers visited using recursive calls.
        HashSet<Integer> s = new HashSet<Integer>();
 
        return isToOneRec(n, s);
    }
 
    // Drivers code
    public static void main(String[] args)
    {
        int n = 5;
        if (isToOne(n))
        {
            System.out.print("Yes");
        }
        else
        {
            System.out.print("No");
        }
    }
}
 
/* This code contributed by PrinciRaj1992 */

Python3

# Python3 program to implement Collatz Conjecture
 
# Function to find if n reaches to 1 or not.
def isToOneRec(n: int, s: set) -> bool:
    if n == 1:
        return True
 
    # If there is a cycle formed,
    # we can't reach 1.
    if n in s:
        return False
 
    # If n is odd then pass n = 3n+1 else n = n/2
    if n % 2:
        return isToOneRec(3 * n + 1, s)
    else:
        return isToOneRec(n // 2, s)
 
# Wrapper over isToOneRec()
def isToOne(n: int) -> bool:
 
    # To store numbers visited
    # using recursive calls.
    s = set()
 
    return isToOneRec(n, s)
 
# Driver Code
if __name__ == "__main__":
    n = 5
    if isToOne(n):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by
# sanjeev2552

C#

// C# program to implement
// Collatz Conjecture
using System;
using System.Collections.Generic;
     
class GFG
{
 
    // Function to find if n reaches to 1 or not.
    static Boolean isToOneRec(int n, HashSet<int> s)
    {
        if (n == 1)
        {
            return true;
        }
 
        // If there is a cycle formed,
        // we can't reach 1.
        if (s.Contains(n))
        {
            return false;
        }
 
        // If n is odd then pass n = 3n+1 else n = n/2
        return (n % 2 == 1) ? isToOneRec(3 * n + 1, s)
                            : isToOneRec(n / 2, s);
    }
 
    // Wrapper over isToOneRec()
    static Boolean isToOne(int n)
    {
        // To store numbers visited using
        // recursive calls.
        HashSet<int> s = new HashSet<int>();
 
        return isToOneRec(n, s);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int n = 5;
        if (isToOne(n))
        {
            Console.Write("Yes");
        }
        else
        {
            Console.Write("No");
        }
    }
}
 
// This code contributed by Rajput-Ji

Javascript

<script>
    // Javascript program to implement Collatz Conjecture
     
    // Function to find if n reaches to 1 or not.
    function isToOneRec(n, s)
    {
        if (n == 1)
        {
            return true;
        }
   
        // If there is a cycle formed,
        // we can't reach 1.
        if (s.has(n))
        {
            return false;
        }
   
        // If n is odd then pass n = 3n+1 else n = n/2
        return (n % 2 == 1) ? isToOneRec(3 * n + 1, s)
                            : isToOneRec(n / 2, s);
    }
   
    // Wrapper over isToOneRec()
    function isToOne(n)
    {
        // To store numbers visited using
        // recursive calls.
        let s = new Set();
   
        return isToOneRec(n, s);
    }
     
    let n = 5;
    if (isToOne(n))
    {
      document.write("Yes");
    }
    else
    {
      document.write("No");
    }
     
    // This code is contributed by divyeshrabadiya07.
</script>

Producción: 
 

Yes

El programa anterior es ineficiente. La idea es usar la Conjetura de Collatz . Establece que si n es positivo, de alguna manera llegará a 1 después de una cierta cantidad de tiempo. Entonces, al usar este hecho, se puede hacer en O (1), es decir, simplemente verifique si n es un número entero positivo o no. 
Tenga en cuenta que la respuesta sería falsa para números negativos. Para números negativos, las operaciones anteriores mantendrían el número negativo y nunca llegaría a 1.
 

C++

// C++ program to implement Collatz Conjecture
#include<bits/stdc++.h>
using namespace std;
 
// Function to find if n reaches to 1 or not.
bool isToOne(int n)
{
    // Return true if n is positive
    return (n > 0);
}
 
// Drivers code
int main()
{
    int n = 5;
    isToOne(n) ? cout << "Yes" : cout <<"No";
    return 0;
}

Java

// Java program to implement Collatz
// Conjecture
class GFG {
     
    // Function to find if n reaches
    // to 1 or not.
    static boolean isToOne(int n)
    {
         
        // Return true if n is positive
        return (n > 0);
    }
     
    // Drivers code
    public static void main(String[] args)
    {
        int n = 5;
         
        if(isToOne(n) == true)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by Smitha.

Python 3

# Python 3 program to implement
# Collatz Conjecture
 
# Function to find if n
# reaches to 1 or not.
def isToOne(n):
 
    # Return true if n
    # is positive
    return (n > 0)
 
# Drivers code
n = 5
 
if isToOne(n) == True:
    print("Yes")
else:
    print("No")
     
# This code is contributed
# by Smitha.

C#

// C# program to implement
// Collatz Conjecture
using System;
 
class GFG {
     
    // Function to find if n
    // reaches to 1 or not.
    static bool isToOne(int n)
    {
         
        // Return true if n
        // is positive
        return (n > 0);
    }
     
    // Drivers code
    public static void Main()
    {
        int n = 5;
         
        if(isToOne(n) == true)
            Console.Write("Yes") ;
        else
            Console.Write("No");
    }
}
 
// This code is contributed
// by Smitha.

Javascript

<script>
    // Javascript program to implement Collatz Conjecture
     
    // Function to find if n
    // reaches to 1 or not.
    function isToOne(n)
    {
          
        // Return true if n
        // is positive
        return (n > 0);
    }
     
    let n = 5;
          
    if(isToOne(n) == true)
      document.write("Yes") ;
    else
      document.write("No");
     
    // This code is contributed by mukesh07.
</script>

PHP

<?php
// PHP program to implement Collatz Conjecture
 
// Function to find if n reaches
// to 1 or not.
function isToOne($n)
{
    // Return true if n is positive
    if($n > 0)
        return true;
    return false;
}
 
// Driver code
$n = 5;
isToOne($n)? print("Yes") : print("No");
 
// This code is contributed by princiraj1992
?>

Producción: 
 

Yes

Recomendamos enfáticamente referirse al siguiente problema como un ejercicio: 
Longitud máxima de la secuencia de Collatz
Este artículo es una contribución de Sahil Chhabra (akku) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *