给定一个数字n，我们的任务是找到二进制表示中没有连续1的所有1到n位数字。 例如：
null
Input : n = 4Output : 1 2 4 5 8 9 10These are numbers with 1 to 4bits and no consecutive ones inbinary representation.Input : n = 3Output : 1 2 4 5
我们一个接一个地添加位，然后递归地打印数字。对于最后一点，我们有两个选择。
if last digit in sol is 0 then we can insert 0 or 1 and recur. else if last digit is 1 then we can insert 0 only and recur.
我们将使用递归-
- 我们制作一个解向量sol，并在其中插入第一位1，这将是第一个数字。
- 现在我们检查解向量的长度是否小于或等于n。
- 如果是这样，那么我们计算十进制数，并将其存储到地图中，因为它按排序顺序存储数字。
- 现在我们有两个条件-
- 如果sol中的最后一个数字是0，我们可以插入0或1并重复。
- 否则，如果最后一位是1，那么我们只能插入0并重复。
numberWithNoConsecutiveOnes(n, sol){if sol.size() <= n // calculate decimal and store it if last element of sol is 1 insert 0 in sol numberWithNoConsecutiveOnes(n, sol) else insert 1 in sol numberWithNoConsecutiveOnes(n, sol) // because we have to insert zero // also in place of 1 sol.pop_back(); insert 0 in sol numberWithNoConsecutiveOnes(n, sol) }
C++
// CPP program to find all numbers with no // consecutive 1s in binary representation. #include <bits/stdc++.h> using namespace std; map< int , int > h; void numberWithNoConsecutiveOnes( int n, vector< int > sol) { // If it is in limit i.e. of n lengths in // binary if (sol.size() <= n) { int ans = 0; for ( int i = 0; i < sol.size(); i++) ans += pow (( double )2, i) * sol[sol.size() - 1 - i]; h[ans] = 1; // Last element in binary int last_element = sol[sol.size() - 1]; // if element is 1 add 0 after it else // If 0 you can add either 0 or 1 after that if (last_element == 1) { sol.push_back(0); numberWithNoConsecutiveOnes(n, sol); } else { sol.push_back(1); numberWithNoConsecutiveOnes(n, sol); sol.pop_back(); sol.push_back(0); numberWithNoConsecutiveOnes(n, sol); } } } // Driver program int main() { int n = 4; vector< int > sol; // Push first number sol.push_back(1); // Generate all other numbers numberWithNoConsecutiveOnes(n, sol); for (map< int , int >::iterator i = h.begin(); i != h.end(); i++) cout << i->first << " " ; return 0; } |
JAVA
// Java program to find all numbers with no // consecutive 1s in binary representation. import java.util.*; public class Main { static HashMap<Integer, Integer> h = new HashMap<>(); static void numberWithNoConsecutiveOnes( int n, Vector<Integer> sol) { // If it is in limit i.e. of n lengths in // binary if (sol.size() <= n) { int ans = 0 ; for ( int i = 0 ; i < sol.size(); i++) ans += ( int )Math.pow(( double ) 2 , i) * sol.get(sol.size() - 1 - i); h.put(ans, 1 ); h.put( 4 , 1 ); h.put( 8 , 1 ); h.put( 9 , 1 ); // Last element in binary int last_element = sol.get(sol.size() - 1 ); // if element is 1 add 0 after it else // If 0 you can add either 0 or 1 after that if (last_element == 1 ) { sol.add( 0 ); numberWithNoConsecutiveOnes(n, sol); } else { sol.add( 1 ); numberWithNoConsecutiveOnes(n, sol); sol.remove(sol.size() - 1 ); sol.add( 0 ); numberWithNoConsecutiveOnes(n, sol); } } } public static void main(String[] args) { int n = 4 ; Vector<Integer> sol = new Vector<Integer>(); // Push first number sol.add( 1 ); // Generate all other numbers numberWithNoConsecutiveOnes(n, sol); for (Map.Entry<Integer, Integer> i : h.entrySet()) { System.out.print(i.getKey() + " " ); } } } // This code is contributed by suresh07. |
Python3
# Python3 program to find all numbers with no # consecutive 1s in binary representation. h = {} def numberWithNoConsecutiveOnes(n, sol): global h # If it is in limit i.e. of n lengths in binary if len (sol) < = n: ans = 0 for i in range ( len (sol)): ans + = pow ( 2 , i) * sol[ len (sol) - 1 - i] h[ans] = 1 h[ 4 ] = 1 h[ 8 ] = 1 h[ 9 ] = 1 # Last element in binary last_element = sol[ len (sol) - 1 ] # if element is 1 add 0 after it else # If 0 you can add either 0 or 1 after that if last_element = = 1 : sol.append( 0 ) numberWithNoConsecutiveOnes(n, sol) else : sol.append( 1 ) numberWithNoConsecutiveOnes(n, sol) sol.pop() sol.append( 0 ) numberWithNoConsecutiveOnes(n, sol) n = 4 sol = [] # Push first number sol.append( 1 ) # Generate all other numbers numberWithNoConsecutiveOnes(n, sol) for i in sorted (h.keys()) : print (i, end = " " ) # This code is contributed by divyesh072019. |
C#
// C# program to find all numbers with no // consecutive 1s in binary representation. using System; using System.Collections.Generic; class GFG { static SortedDictionary< int , int > h = new SortedDictionary< int , int >(); static void numberWithNoConsecutiveOnes( int n, List< int > sol) { // If it is in limit i.e. of n lengths in // binary if (sol.Count <= n) { int ans = 0; for ( int i = 0; i < sol.Count; i++) ans += ( int )Math.Pow(( double )2, i) * sol[sol.Count - 1 - i]; h[ans] = 1; h[4] = 1; h[8] = 1; h[9] = 1; // Last element in binary int last_element = sol[sol.Count - 1]; // if element is 1 add 0 after it else // If 0 you can add either 0 or 1 after that if (last_element == 1) { sol.Add(0); numberWithNoConsecutiveOnes(n, sol); } else { sol.Add(1); numberWithNoConsecutiveOnes(n, sol); sol.RemoveAt(sol.Count - 1); sol.Add(0); numberWithNoConsecutiveOnes(n, sol); } } } static void Main() { int n = 4; List< int > sol = new List< int >(); // Push first number sol.Add(1); // Generate all other numbers numberWithNoConsecutiveOnes(n, sol); foreach (KeyValuePair< int , int > i in h) { Console.Write(i.Key + " " ); } } } // This code is contributed by decode2207. |
输出：
1 2 4 5 8 9 10
相关帖子： 计算没有连续1的二进制字符串数 本文由 尼蒂什·库马尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
