如何使用C中的递归生成4位二进制组合0,1？
对于这个数组，尝试这样的事情：
void rollover(int val,int count) { if(count==0) { return; } printf("%d ",val); count--; rollover(val,count); } int main() { int arr[]={0,1}; for(int i=0;i<=1;i++) { rollover(arr[i],4); } printf("\n"); return 0; } 使用递归方法的预期输出：
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
无法理解如何编写rec函数。 我花了几个小时来解决它。 有人可以协助编写该function吗？
我正在尝试做下面发布的G_G之类的事情。 我怎么能写这样的递归函数？ 我是否必须使用一个for循环来调用递归函数，或者使用两个for循环来递归，还是应该调用两次递归函数？ 例如：
void rollover(int val,int count) { if(count==0) { return; } printf("%d ",val); count--; rollover(val,count); //.. do something if necessary .. rollover(val,count); //.. do something if necessary .. }
最简单的解决方案：二进制转换，无递归
for(int i = 0; i < 16: ++i) { printf("%u%u%u%u", i/8%2, i/4%2, i/2%2, i%2); }
有关此循环的递归版本，请参阅MOHAMED的答案
以下解决方案使用的二进制递归
_ 000 _ 00 _/ / \_ 001 0 _ 010 \_ 01 _/ \_ 011 _ 100 _ 10 _/ / \_ 101 1 _ 110 \_ 11 _/ \_ 111
使用char* buffer的递归解决方案，没有二进制转换
void char_buffer_rec(char number[4], int n) { if(n > 0) { number[4-n] = '0'; char_buffer_rec(number, n - 1); number[4-n] = '1'; char_buffer_rec(number, n - 1); } else { printf("%s\n", number); } }
用法：
char number[5] = {0}; char_buffer_rec(number, 4);
仅使用int ，无缓冲区，无二进制转换的递归解决方案
void int_ten_rec(int number, int tenpower) { if(tenpower > 0) { int_ten_rec(number, tenpower/10); int_ten_rec(number + tenpower, tenpower/10); } else { printf("%04u\n", number); } }
用法：
int_ten_rec(0, 1000);
此解决方案的另一个版本替换tenpower宽度bitwidth ，使用可变填充替换printf width ，具体取决于长度变量。 length可以定义为新参数，程序常量等。
void int_rec(int number, int bitwidth) { static int length = bitwidth; int i, n; if(bitwidth > 0) { int_rec(number, bitwidth-1); /* n := 10^(bitwidth-2) */ for(i=0,n=1;i=10;++i,n/=10); /* print (length-i) zeros */ for(n=i; n
用法：
int_rec(0, 4);
Tree Solution，使用char* buffer递归递归，无二进制转换
struct Node { int val; struct Node *left, *right; }; void build_tree(struct Node* tree, int n) { if(n > 0) { tree->left = (Node*)malloc(sizeof(Node)); tree->right= (Node*)malloc(sizeof(Node)); tree->left->val = 0; build_tree(tree->left, n - 1); tree->right->val = 1; build_tree(tree->right, n - 1); } else { tree->left = tree->right = NULL; } } void print_tree(struct Node* tree, char* buffer, int index) { if(tree->left != NULL && tree->right != NULL) { sprintf(buffer+index, "%u", tree->val); print_tree(tree->left, buffer, index+1); sprintf(buffer+index, "%u", tree->val); print_tree(tree->right, buffer, index+1); } else { printf("%s%u\n", buffer, tree->val); } }
用法：
char buffer[5] = {0}; Node* tree = (Node*)malloc(sizeof(Node)); tree->val = 0; build_tree(tree, 4); print_tree(tree, buffer, 0);
但是这会在每行的开头打印一个额外的0 ，为了避免这种情况，构建两个较小的树：
Node* tree0 = (Node*)malloc(sizeof(Node)); Node* tree1 = (Node*)malloc(sizeof(Node)); tree0->val = 0; tree1->val = 1; build_tree(tree0, 3); build_tree(tree1, 3); print_tree(tree0, buffer, 0); print_tree(tree1, buffer, 0);
使用int *数组的递归解决方案
#define MAX_LENGTH 32 int number[MAX_LENGTH]; void int_buffer_rec(int n, int length) { if(n > 0) { number[4-n] = 0; int_buffer_rec(n - 1, length); number[4-n] = 1; int_buffer_rec(n - 1, length); } else { for(int i = 0; i < length; ++i) { printf("%u", number[i]); } printf("\n"); } }
用法：
int_buffer_rec(4, 4);
递归可以用+1完成
void f(unsigned int x) { printf("%u%u%u%u\n", (x>>3)&0x1, (x>>2)&0x1, (x>>1)&0x1, x&0x1); if(x==0xF) return; else f(x+1); } int main(void) { f(0); }
执行：
$ ./test 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
只需遍历DFS深度为4的二叉树，向左移动为0，向右移动为1。
tr(int dep, int val) { if(dep == 4) { printf("\n"); } else { printf("%d", val); tr(dep+1, 0); // going left tr(dep+1, 1); // going right } return; } int main() { tr(0,0); }
我试图将我的解决方案限制为使用相同的参数，但我肯定会添加一个额外的参数来知道count的初始值。
void rec(int val, int count) { if (count <= 1) { int i; int f = 0; for (i = sizeof(int) * 8; i >= 0; i--) { f |= (val >> i) & 1; if (f) { printf("%d", (val >> i) & 1); } } printf("\n"); } else { rec(val * 2, count - 1); rec(val * 2 + 1, count - 1); } }
输出：
1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111
为了添加前导0，我添加了一个参数：
#include void rec2(int val, int count, int b) { if (count <= 1) { int i; for (i = b - 1; i >= 0; i--) { printf("%d", (val >> i) & 1); } printf("\n"); } else { rec2(val * 2, count - 1, b); rec2(val * 2 + 1, count - 1, b); } } void rec(int val, int count) { rec2(val, count, count); } int main() { rec(0, 4); rec(1, 4); return 0; }
输出：
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
让我们从设计递归函数的原型开始。 希望它从那里开始有意义。 看一下这段代码的非递归版本，你需要相同的变量。 您不需要将它们中的任何一个作为参数传递，但我更愿意将它们全部传递，并使解决方案尽可能灵活和模块化。 考虑返回值。 这应该表明某种成功 ，以模仿与C标准库的一致性。
int count_r(char *destination, /* The storage for the function to store * * the 0s and 1s as we count. */ size_t length, /* The number of digits in the number. */ char *digit); /* The set of digits */
现在让我们专注于设计第一次迭代。 就像在小学一样，我们首先定义我们的count_r ，一次只迭代一位数。 一旦我们能够certificate它知道如何从0到9计数，我们将它引入两位数…但是现在，一次一步。
让我们假设在第一次调用之前， destination被初始化为包含digits[0] length字节。 这个初始化由调用者完成，调用者可能会在调用之前输出预先初始化的数组。 第一次迭代应该只修改一个字节：由length表示的那个，然后返回给调用者。
int count_r(char *destination, size_t length, char *digit) { /* The position of the right-most digit is before the '\0' in destination, * * so we need to decrement length */ length--; /* Find the digit at the very end of destination, within our "digit" parameter */ char *d = strchr(digit, destination[length]); /* d[1] points to the next digit (or '\0') */ destination[length] = d[1]; return 0; }
然后调用者可能会打印数组，并使用相同的缓冲区再次调用count_r来增加计数器。 这适用于不同的基础，通过反转digit字符串，我们可以减少而不是递增。 但是，正如我们很快就会看到的那样，它在达到可以计入的最高数字后失败：在下面的例子中为'F' 。
int main(void) { char num[] = "0"; do { puts(num); } while (count_r(num, strlen(num), "0123456789ABCDEF") == 0); }
当计数更高时，d [1]将为'\0'因为它将迭代超过数字集并进入字符串的空终止符。 让我们考虑添加代码来处理我们的第二次迭代。
需要一些代码将destination[length]设置回第一个digit并递归地向左移动到下一个数字。 当d[1] == '\0'时会发生这种情况，因此我们可以编写一个if (...) { ... }分支来处理它。
将length传入0时会出现问题，我们将在实现刚刚提到的更改后发现。 这里函数应返回1表示计数已完成，因为它已尽可能向左移动并达到可能的最高数量。
void count_r(char *destination, size_t length, char *digit) { /* The position of the right-most digit is before the '\0' in destination, * * so we need to decrement length */ if (length-- == 0) { return 1; } /* Find the digit at the very end of destination, within our "digit" parameter */ char *d = strchr(digit, destination[length]); /* d[1] points to the next digit (or '\0') */ if (d[1] == '\0') { /* Set destination[length] to the first digit */ destination[length] = digit[0]; /* Recurse onto the next digit. We've already decremented length */ return count_r(destination, length, digit); } destination[length] = d[1]; return 0; }
在添加一些assert离子（例如assert(strlen(digit) > 1); ）并编写一些测试用例之后，我们可能会确定此函数已准备好进行生产。 我希望我能够提供帮助。 🙂
递归是一种编程技术，允许程序员根据自己表达操作。 在C和C ++中，它采用调用自身的函数的forms 。
#include #include using namespace std; void rec(int val) { if(val<16) { printf("%u%u%u%u", val>>3, (val&4)>>2, (val&2)>>1, val&1); printf("\n"); rec(++val); //calling val+1 here } return; } int main() { rec(0); //calling recursion for 0 }
这为您提供了您想要的精确输出..！
如果你不想使用位移操作符..
#include #include using namespace std; void rec(int val) { if(val<16) { for(int b=val,a=8,i=0;i<4;b%=a,a/=2,i++) printf("%u",(b/a)); printf("\n"); rec(++val);// calling val+1 here } return; } int main() { rec(0);//calling recursion for 0 }
可以推广该问题以通过使用递归来获得任何长度的二进制组合。 例如，如果要获得length=4所有二进制组合，只需调用printBinaryCombination("????", 0) （即四个需要替换为0或1 ）。
相应的代码如下：
void printBinaryCombination(string str, int current) { int length = str.length(); if (length == 0) return; if (current == length) printf("%s\n", str.c_str()); else { if (str[current] == '?') { str[current] = '0'; printBinaryCombination(str, current+1); str[current] = '1'; printBinaryCombination(str, current+1); // change back for next time str[current] = '?'; } else printBinaryCombination(str, current+1); } }
编辑 ：实际上，上面的函数也很强大，可以处理包含随机数的所有二进制组合? s，每个可以是0或1 。 例如，如果你调用printBinaryCombination("1??0", 0) ，它将打印：
1000 1010 1100 1110
要生成n位组合，您要求（您要求n = 4）任何n的一般递归实现将是：
主function：
vector ve,ve1; int main(int argc, char const *argv[]) { /* code */ int n; cin>>n; generate("0",n,true); generate("1",n,false); for(int i=0;i
生成以递归方式生成二进制字符串的函数：
void generate(string s,int n,bool b){ if(n==1){ if(b==true){ ve.push_back(s); } else{ ve1.push_back(s); } return; }else{ generate(s+"0",n-1,b); generate(s+"1",n-1,b); } }
希望这可以帮助..
SOLN 1：更广泛的答案（在c90，c99下可编译）。 布尔值输出为int。 限制：
1）使用数学库。（它更重）。
#include #include #define MAXBITS 4 //#define MAXVALUES (((int)pow(2,maxb))-1) const int MAXVALUES = (((int)pow(2,maxb))-1) //if this gives warning then use #define version. void bin(int val,int total) { int i = 0; if(val <= MAXVALUES) //can write pow(2,total-1)-1 but anyways.. { for(i =0 ; i < total;i++) { printf("%d",!!(val&(int)pow(2,total-i-1))); } printf("\n"); } else return; bin(val+1,total); } int main() { setbuf(stdout,NULL); bin(0,MAXBITS);//4 bits return 0; }
Soln 2：这可以通过char打印来完成。 没有class次操作员。
限制：
1）它可以（正确地）打印最多15（十进制）或0x0F（hex）值。
2）共计
(5 * sizeof(char) * total) + (( total + 2) * (sizeof(int) + sizeof(int)))在堆栈上创建（如此浪费）。
#include #include #include #define MAXVALUES 15 #define MAXBITS 4 void bin(int val,int total) //@prototype void bin(int val);remove redundant total. { char *s = malloc(sizeof(char)*(total+1)); //cant declare variable array(atleast pre c99) int i = 0; if(val <= MAXVALUES ) { for(i =0 ; i < total;i++) { s[total - i-1] = !!(val&(int)pow(2,i)) + '0'; } s[total] = '\0'; printf("%s\n",s); } else return; bin(val+1,total); } int main() { bin(0,MAXBITS);//4 bits return 0; }
这个通用的c ++代码适用于任意数量的位。 只需将const int num更改为要生成二进制代码的任意位数…
const int num=3; string code=""; void GenerateBinaryCode(string str,unsigned int n){ if(n==0){ cout<
在介绍最终解决方案之前，我将展示两个可用于实现目标的function。
下一个函数的主要思想是将l1列表的元素添加到l2包含的每个列表中。 例如：
l1 = [0] l2 = [ [1,1] , [1,0] ] then f1(l1,l2) = [ [0,1,1] ,[0,1,0]] def f1(l1:List[Int],l2:List[List[Int]]): List[List[Int]] = l2.map{ r=> l1:::r}
第一个参数是一个列表，其中包含将添加到l2列表中包含的每个数字列表的整数列表。 例如：
l1 = [ [0] , [1]] l2 = [ [1,0], [1,1] ] f(l1,l2) = [ [0,1,0],[0,1,1], [1,1,0],[1,1,1] ] def f(l1:List[List[Int]],l2:List[List[Int]]): List[List[Int]] = l1.map{ r=> f1(r,l2)} flatten
现在，我们有了辅助方法，我们创建了解决需求的function
/** n : The max number of digits that the binary number can contain */ def binaryNumbers(n:Int):List[List[Int]] = n match { case 1 => List(List(0),List(1)) case _ => f( List(List(0),List(1)) , binaryNumbers(n-1) ) } Example: binaryNumbers(2) = List( List(0,0), List(0,1), List(1,0), List(1,1) )