给定一个正整数n，任务是在执行以下两个操作后，确定该数字是否达到1：-
null
- 如果n是偶数，那么n=n/2。
- 如果n是奇数，那么n=3*n+1。
- 重复以上步骤，直到变为1。
例如，对于n=12，我们得到序列12，6，3，10，5，16，8，4，2，1。 例如：
Input : n = 4Output : YesInput : n = 5Output : Yes
其思想是简单地遵循给定的规则，递归地调用具有缩减值的函数，直到它达到1。如果在递归过程中再次看到一个值，那么就有一个循环，我们不能达到1。在这种情况下，我们返回false。
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> |
输出：
Yes
上述程序效率低下。这个想法是使用 科拉兹猜想 它表示，如果n是正的，那么经过一定的时间，它会以某种方式达到1。所以，通过使用这个事实，它可以在O（1）中完成，也就是说，只需检查n是否为正整数。 请注意，对于负数，答案将为false。对于负数，上述操作将使数字保持为负数，并且永远不会达到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 ?> |
输出：
Yes
我们强烈建议将以下问题作为练习： 最大Collatz序列长度 本文由 萨希尔·查布拉（阿克库） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
