Dado un entero positivo n, la tarea es encontrar si este número llega a 1 después de realizar las siguientes dos operaciones:
- Si n es par, entonces n = n/2.
- Si n es impar, entonces n = 3*n + 1.
- 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