首页 > 代码库 > 第一章 基本概念_假设有n个布尔变量x1, ..., xn,输出其所有可能的真值集合

第一章 基本概念_假设有n个布尔变量x1, ..., xn,输出其所有可能的真值集合

例如,如果n=2, 有四种可能:<true, true>, <true, false>,<false, true>和<false, false>。编写C语言函数实现之。

分析:对于任意一个正整数n,所有可能的情况为2^n种,即n个2相乘。对于每一个元素,有两种可能:true或者false,我们可以将其中一种结果设定为一个长度为n的序列,在每一位上,它的值只能是true或false。可以用下面给出的简单算法来产生其所有可能的序列,即长度为n的序列由下列序列组成:(True,(n-1)序列所有结果),(False,(n-1)序列所有结果)。由此我们自然想到使用递归,这表明,如果能够解决n-1个元素的序列,就可以解决n个元素的序列。


#include <stdio.h>  
#include <stdlib.h>
#define Max_size 100 /*最多可以使得n=100 */  
 
void value(char *, int i, int n);  
 
void main(void)  
{  
int n, k;  
char list[Max_size]; /*用字符数组存储字符,‘T’代表true, ‘F’代表false*/  
printf("input the number of Booleans: \n");  
scanf("%d", &n);  
if (n<1 || n>Max_size)  
{  
   printf("\nImproper number n!\n");  
   exit(1);  
}  
for(k=0; k<n; k++)  
{  
   list[k] = ‘T‘;  
}  
value(list, 0, n-1);  
}  
 
void value (char *list, int i, int n)  
{  
int j;  
if (i==n+1) /*已经递归完毕, 输出序列*/  
{  
   for (j=0; j<=n; j++)  
   {  
    printf("%c", list[j]);  
   }  
   printf("     ");  
}  
else {  
   list[i] = ‘T‘;  
   value(list, i+1, n);  
   list[i] = ‘F‘;  
   value(list, i+1, n);  
}  
}

第一章 基本概念_假设有n个布尔变量x1, ..., xn,输出其所有可能的真值集合