原文:
给定一个正整数 n，打印所有 n 位二进制数，对于该数的任何前缀，该数的 1 大于 0。
示例:
input : n = 2
output : 11 10
input : n = 4
output : 1111 1110 1101 1100 1011 1010
一个简单但不有效的pg电子试玩链接的解决方案是生成所有的 n 位二进制数，并打印那些满足条件的数。这个解的时间复杂度是指数级的。
一个有效的pg电子试玩链接的解决方案是只生成那些满足给定条件的 n 位数字。我们使用递归。在递归中的每一点，我们将 0 和 1 附加到部分形成的数字上，并用少一个数字重复。
c
// c program to print all n-bit binary
#include
using namespace std;
/* function to generate n digit numbers*/
void printrec(string number, int extraones,
int remainingplaces)
{
/* if number generated */
if (0 == remainingplaces) {
cout << number << " ";
return;
}
/* append 1 at the current number and reduce
the remaining places by one */
printrec(number "1", extraones 1,
remainingplaces - 1);
/* if more ones than zeros, append 0 to the
current number and reduce the remaining
places by one*/
if (0 < extraones)
printrec(number "0", extraones - 1,
remainingplaces - 1);
}
void printnums(int n)
{
string str = "";
printrec(str, 0, n);
}
// driver code
int main()
{
int n = 4;
// function call
printnums(n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print all n-bit binary
import java.io.*;
class gfg {
// function to generate n digit numbers
static void printrec(string number,
int extraones,
int remainingplaces)
{
// if number generated
if (0 == remainingplaces) {
system.out.print(number " ");
return;
}
// append 1 at the current number and
// reduce the remaining places by one
printrec(number "1", extraones 1,
remainingplaces - 1);
// if more ones than zeros, append 0 to the
// current number and reduce the remaining
// places by one
if (0 < extraones)
printrec(number "0", extraones - 1,
remainingplaces - 1);
}
static void printnums(int n)
{
string str = "";
printrec(str, 0, n);
}
// driver code
public static void main(string[] args)
{
int n = 4;
// function call
printnums(n);
}
}
// this code is contributed by vt_m
python 3
# python 3 program to print all n-bit binary
# function to generate n digit numbers
def printrec(number, extraones, remainingplaces):
# if number generated
if (0 == remainingplaces):
print(number, end=" ")
return
# append 1 at the current number and
# reduce the remaining places by one
printrec(number "1", extraones 1,
remainingplaces - 1)
# if more ones than zeros, append 0 to
# the current number and reduce the
# remaining places by one
if (0 < extraones):
printrec(number "0", extraones - 1,
remainingplaces - 1)
def printnums(n):
str = ""
printrec(str, 0, n)
# driver code
if __name__ == '__main__':
n = 4
# function call
printnums(n)
# this code is contributed by
# surendra_gangwar
c
// c# program to print all n-bit binary
using system;
class gfg {
// function to generate n digit numbers
static void printrec(string number,
int extraones,
int remainingplaces)
{
// if number generated
if (0 == remainingplaces)
{
console.write(number " ");
return;
}
// append 1 at the current number and
// reduce the remaining places by one
printrec(number "1", extraones 1,
remainingplaces - 1);
// if more ones than zeros, append
// 0 to the current number and
// reduce the remaining places
// by one
if (0 < extraones)
printrec(number "0", extraones - 1,
remainingplaces - 1);
}
static void printnums(int n)
{
string str = "";
printrec(str, 0, n);
}
// driver code
public static void main()
{
int n = 4;
// function call
printnums(n);
}
}
// this code is contributed by nitin mittal.
服务器端编程语言（professional hypertext preprocessor 的缩写）
java 描述语言
output
1111 1110 1101 1100 1011 1010
也存在非递归pg电子试玩链接的解决方案，其思想是直接生成 2^n 到 2^(n-1 范围内的数字)，然后只需要满足以下条件的数字:
c
// c program to print all n-bit binary
#include
#include
using namespace std;
// function to get the binary representation
// of the number n
string getbinaryrep(int n, int num_of_bits)
{
string r = "";
num_of_bits--;
// loop for each bit
while (num_of_bits >= 0)
{
if (n & (1 << num_of_bits))
r.append("1");
else
r.append("0");
num_of_bits--;
}
return r;
}
vector nbitbinary(int n)
{
vector r;
int first = 1 << (n - 1);
int last = first * 2;
// generate numbers in the range of (2^n)-1 to 2^(n-1)
// inclusive
for (int i = last - 1; i >= first; --i)
{
int zero_cnt = 0;
int one_cnt = 0;
int t = i;
int num_of_bits = 0;
// longest prefix check
while (t)
{
if (t & 1)
one_cnt ;
else
zero_cnt ;
num_of_bits ;
t = t >> 1;
}
// if counts of 1 is greater than
// counts of zero
if (one_cnt >= zero_cnt)
{
// do sub-prefixes check
bool all_prefix_match = true;
int msk = (1 << num_of_bits) - 2;
int prefix_shift = 1;
while (msk)
{
int prefix = (msk & i) >> prefix_shift;
int prefix_one_cnt = 0;
int prefix_zero_cnt = 0;
while (prefix)
{
if (prefix & 1)
prefix_one_cnt ;
else
prefix_zero_cnt ;
prefix = prefix >> 1;
}
if (prefix_zero_cnt > prefix_one_cnt)
{
all_prefix_match = false;
break;
}
prefix_shift ;
msk = msk & (msk << 1);
}
if (all_prefix_match)
{
r.push_back(getbinaryrep(i, num_of_bits));
}
}
}
return r;
}
// driver code
int main()
{
int n = 4;
// function call
vector results = nbitbinary(n);
for (int i = 0; i < results.size(); i)
cout << results[i] << " ";
cout << endl;
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print all n-bit binary
import java.io.*;
import java.util.*;
class gfg
{
// function to get the binary representation
// of the number n
static string getbinaryrep(int n, int num_of_bits)
{
string r = "";
num_of_bits--;
// loop for each bit
while (num_of_bits >= 0)
{
if ((n & (1 << num_of_bits))!=0)
r = "1";
else
r = "0";
num_of_bits--;
}
return r;
}
static arraylist nbitbinary(int n)
{
arraylist r = new arraylist();
int first = 1 << (n - 1);
int last = first * 2;
// generate numbers in the range of (2^n)-1 to 2^(n-1)
// inclusive
for (int i = last - 1; i >= first; --i)
{
int zero_cnt = 0;
int one_cnt = 0;
int t = i;
int num_of_bits = 0;
// longest prefix check
while (t > 0)
{
if ((t & 1) != 0)
one_cnt ;
else
zero_cnt ;
num_of_bits ;
t = t >> 1;
}
// if counts of 1 is greater than
// counts of zero
if (one_cnt >= zero_cnt)
{
// do sub-prefixes check
boolean all_prefix_match = true;
int msk = (1 << num_of_bits) - 2;
int prefix_shift = 1;
while (msk > 0)
{
int prefix = (msk & i) >> prefix_shift;
int prefix_one_cnt = 0;
int prefix_zero_cnt = 0;
while (prefix > 0)
{
if ((prefix & 1)!=0)
prefix_one_cnt ;
else
prefix_zero_cnt ;
prefix = prefix >> 1;
}
if (prefix_zero_cnt > prefix_one_cnt)
{
all_prefix_match = false;
break;
}
prefix_shift ;
msk = msk & (msk << 1);
}
if (all_prefix_match)
{
r.add(getbinaryrep(i, num_of_bits));
}
}
}
return r;
}
// driver code
public static void main (string[] args)
{
int n = 4;
// function call
arraylist results = nbitbinary(n);
for (int i = 0; i < results.size(); i)
system.out.print(results.get(i) " ");
system.out.println();
}
}
// this code is contributed by avanitrachhadiya2155
python 3
# python3 program to print
# all n-bit binary
# function to get the binary
# representation of the number n
def getbinaryrep(n, num_of_bits):
r = "";
num_of_bits -= 1
# loop for each bit
while (num_of_bits >= 0):
if (n & (1 << num_of_bits)):
r = ("1");
else:
r = ("0");
num_of_bits -= 1
return r;
def nbitbinary(n):
r = []
first = 1 << (n - 1);
last = first * 2;
# generate numbers in the range
# of (2^n)-1 to 2^(n-1) inclusive
for i in range (last - 1,
first - 1, -1):
zero_cnt = 0;
one_cnt = 0;
t = i;
num_of_bits = 0;
# longest prefix check
while (t):
if (t & 1):
one_cnt = 1
else:
zero_cnt = 1
num_of_bits = 1
t = t >> 1;
# if counts of 1 is greater
# than counts of zero
if (one_cnt >= zero_cnt):
# do sub-prefixes check
all_prefix_match = true;
msk = (1 << num_of_bits) - 2;
prefix_shift = 1;
while (msk):
prefix = ((msk & i) >>
prefix_shift);
prefix_one_cnt = 0;
prefix_zero_cnt = 0;
while (prefix):
if (prefix & 1):
prefix_one_cnt = 1
else:
prefix_zero_cnt = 1
prefix = prefix >> 1;
if (prefix_zero_cnt >
prefix_one_cnt):
all_prefix_match = false;
break;
prefix_shift = 1
msk = msk & (msk << 1);
if (all_prefix_match):
r.append(getbinaryrep(i,
num_of_bits));
return r
# driver code
if __name__ == "__main__":
n = 4;
# function call
results = nbitbinary(n);
for i in range (len(results)):
print (results[i],
end = " ")
print ()
# this code is contributed by chitranayal
c
// c# program to print all n-bit binary
using system;
using system.collections.generic;
class gfg{
// function to get the binary representation
// of the number n
static string getbinaryrep(int n, int num_of_bits)
{
string r = "";
num_of_bits--;
// loop for each bit
while (num_of_bits >= 0)
{
if ((n & (1 << num_of_bits)) != 0)
r = "1";
else
r = "0";
num_of_bits--;
}
return r;
}
static list nbitbinary(int n)
{
list r = new list();
int first = 1 << (n - 1);
int last = first * 2;
// generate numbers in the range of (2^n)-1 to 2^(n-1)
// inclusive
for(int i = last - 1; i >= first; --i)
{
int zero_cnt = 0;
int one_cnt = 0;
int t = i;
int num_of_bits = 0;
// longest prefix check
while (t > 0)
{
if ((t & 1) != 0)
one_cnt ;
else
zero_cnt ;
num_of_bits ;
t = t >> 1;
}
// if counts of 1 is greater than
// counts of zero
if (one_cnt >= zero_cnt)
{
// do sub-prefixes check
bool all_prefix_match = true;
int msk = (1 << num_of_bits) - 2;
int prefix_shift = 1;
while (msk > 0)
{
int prefix = (msk & i) >> prefix_shift;
int prefix_one_cnt = 0;
int prefix_zero_cnt = 0;
while (prefix > 0)
{
if ((prefix & 1)!=0)
prefix_one_cnt ;
else
prefix_zero_cnt ;
prefix = prefix >> 1;
}
if (prefix_zero_cnt > prefix_one_cnt)
{
all_prefix_match = false;
break;
}
prefix_shift ;
msk = msk & (msk << 1);
}
if (all_prefix_match)
{
r.add(getbinaryrep(i, num_of_bits));
}
}
}
return r;
}
// driver code
static public void main()
{
int n = 4;
// function call
list results = nbitbinary(n);
for (int i = 0; i < results.count; i)
console.write(results[i] " ");
console.writeline();
}
}
// this code is contributed by rag2127
java 描述语言
output
1111 1110 1101 1100 1011 1010
本文由普拉纳夫供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。
如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
