现在的位置: 首页 > 综合 > 正文

列出所有子集—–字典顺序 2013年1月14日

2013年12月03日 ⁄ 综合 ⁄ 共 876字 ⁄ 字号 评论关闭

         问题描述:写一个程序,用字典顺序把一个集合的所有子集找出来。

         此题的思路来自《C语言名题精选百则技巧篇》:字典顺序,也就是字符串比较时的顺序规则。可以采取这样的思路(以下是我根据书上的思路进行归纳再加上我自己的理解得来的步骤):

         先定义n是集合的个数并且集合是已经从小到大排好顺序的{1,2,3....n}的集合。集合从{1}开始(此时下标index=0),

         1.当state[i]<n时,就向右进行扩展,将state[2]=2;接着将state[3]=3;

         2.当state[index]==n时,就不能向右边进行扩展了,此时就需要向左边处理了。此时的集合是{1,2,3,....,n-2,n-1,n},那么,要找比这个集合刚好大一点的,就是{1,2,3,....n-2,n},所以就可以归纳出规则为:将index减1并且将state[index]加1。

         3.如果state[0]==n,那么循环就结束,反之则重复第1,2步,直到state[0]==n。

         代码如下:

复制代码
 1 #include <stdio.h>
 2 #define MAX  1000
 3 
 4 int main()
 5 {
 6     int n=3;
 7     int set[MAX]={1};
 8     int index=0;
 9     int count=2;
10     printf("1:{}\n2:{1}\n");
11     while(set[0]!=n)
12     {
13         if(set[index]<n)  
14         {   
15             set[index+1]=set[index]+1;
16             index++;
17         }
18         else
19         {
20             index--; 
21             set[index]++;
22         }
23         int a_index;
24         count++;
25         printf("%d:{",count);
26         for(a_index=0;a_index<=index;a_index++)
27             printf("%d ",set[a_index]);
28         printf("}\n");
29     }
30     return 0;
31 }
复制代码

         参考资料:《C语言名题精选百则技巧篇》

抱歉!评论已关闭.