List All Of The Subset In Another Method

Problem description:Please list all of the subsets of a known set including the empty set.

Thinking: the subset's sum of a super set is (n is the number of the super set element) while a n-bit binary space could express  numbers too.So our target is to generate all of the binary numbers in n bit space.Before solving the problem,please look at this point:

11111 01111
+                 1
-------------------
11111 10000

When the number add 1,the current bit will become to 0 and generate a carry if it was 1.Next,the previous bit 1 will become 0 with a carry,too.If its current bit is 0 ,it becomes 1 without a carry and stop the addition.Hence,the program process is clear.

 1 #include <stdio.h>
 2 #include <math.h>
 3 #define MAX 1000
 4 
 5 int n=4;// the number of the set elements
 6 int set[MAX]={1,2,3,4};
 7 int path[MAX]={0};
 8 int count=1;
 9 
10 //prototype
11 void print_set();
12 
13 int main()
14 {
15     int sum=(int)pow(2.0,n)-1;
16     int index,index_re;
17     printf("%d:{}\n",count);
18     for(index=0;index<sum;index++)
19     {
20         for(index_re=n-1;index_re>=0;index_re--) 
21         {
22             if(path[index_re]==1) 
23                 path[index_re]=0;
24             else
25             {
26                 path[index_re]=1;
27                 break;
28             }
29         }
30         count++;
31         printf("%d:{",count);
32         print_set();
33     }
34     return 0;
35 }
36 
37 void print_set()
38 {
39     int index;
40     for(index=0;index<n;index++)
41     {
42         if(path[index]!=0) 
43             printf("%d ",set[index]);
44     }
45     printf("}\n");
46 }

Reference material: C语言名题精选百则技巧篇 in Chinese.

List All Of The Subsets

Problem description:Please list all of the subsets of a known set including the empty set.

My idea: one thinking of the algorithm backtracking is to generate a tree of subset and the condition of an element in the super set for a subset is either on or off.Hence we can specialize the subset tree to a binary tree and we print once when we reach the bottom of the tree each time.It is also easy to write a program.

 1 #include <stdio.h>
 2  #define MAX 1000
 3  
 4  int n=3;  //the number of the set elements
 5  int set[MAX]={1,2,3};
 6  int count=0;//the number of the subset.
 7  
 8  void DFS(int level);
 9  void print_set();
10  
11  int main()
12  {
13      DFS(0);
14      return 0;
15  }
16  
17  void DFS(int level)
18  {
19      if(level==n)
20      {
21          print_set();
22          return ;
23      }
24      int save=set[level];
25      set[level]=0;
26      int index=0;
27      for(index=0;index<2;index++)
28      {
29          DFS(level+1);
30          set[level]=save;
31      }
32  
33  }
34  
35  void print_set()
36  {
37      int index;
38      count++;
39      printf("%d: {",count);
40      for(index=0;index<n;index++)
41      {
42          if(set[index]!=0) 
43              printf("%d ",set[index]);
44      }
45      printf("}\n");
46  }

Linear Sieve Method for Prime Numbers

Problem description:When we calculate for prime numbers with a sieve method,we delete so many numbers which is not necessary repeatly.For instance,there is a number which consists of 3x7x17x23,and we delete it when we delete the multiples of 3 as we delete the same number when we delete the multiples of 7,17,and 23.Please write a program that will not do these jobs more than once.
   
Thinking: There is a factorization theorem:every composite number could be decomposed into the multiplication of some primer numbers.Hence,the number can be decomposed in the form of  (both of p and q are prime numbers and p < q).Therefore,what we need to remove is:,,...and,i=1,2,3.....The value of p and q is the numbers which are not removed currently and in a sequence from small to large.It is easy to write the program.

 1 #include <stdio.h>
 2 #define MAX 1000
 3 #define null1 0
 4 #define NEXT(x)  x=next[x]
 5 #define REMOVE(x) {   previous[next[x]]=previous[x];   \
 6                       next[previous[x]]=next[x];       \
 7                   }
 8 
 9 #define INITIAL(n)  { unsigned long i;                    \
10                       for(i=2;i<=n;i++)                   \
11                           previous[i]=i-1,next[i]=i+1;    \
12                       previous[2]=next[n]=null1;           \
13                     }
14 
15 int main()
16 {
17     unsigned long previous[MAX+1]={0};
18     unsigned long next[MAX+1]={0};
19     unsigned long prime,fact,i,mult;
20     unsigned long n;
21     unsigned long count=0;
22     
23     scanf("%lu",&n);
24 
25     INITIAL(n); //initial the array
26 
27     for(prime=2;prime*prime<=n;NEXT(prime))
28     {
29         for(fact=prime;prime*fact<=n;NEXT(fact)) 
30         {
31             for(mult=prime*fact;mult<=n;mult*=prime) 
32                 REMOVE(mult);
33         }
34     }
35     for(i=2;i!=null1;NEXT(i))
36         printf("%lu ",i),count++;
37     printf("\nThe sum of the prime numbers is %lu\n",count);
38 }

Reference material: C语言名题精选百则技巧篇 in Chinese.

A Sieve Method for Prime Numbers

Problem description:Calculate the prime numbers with a sieve method.There is a magical sieve that can remove all the multiple of the number i.Please calculate the prime numbers at a range from 2 to N by this way.There is a requirement that you should not use multiplication and division.You can only use the addition and subtraction for the speed.

The problem and the solution come from the book named C语言名题精选百则技巧篇 in Chinese.I am ashamed that I have few idea about this kind of problems which need some math knowledge.I need do practice more in this aspect.

I made a summary about the thinking of that book and added some my own idea.

1. The multiples of 2 are not prime so we don't think about them. 2 is prime,so the set should be discussed is 2i+3,i=0,1,2,3,4........

2. We just need deal with the numbers up to the half the number to be tested. We base the MAX in the code,calculate the prime between 2 to 2*MAX+3 but we just stop i at the MAX with our program.

3. We can not use the multiplication and division but addition and subtraction,so we must do something in math aspect : 2i+3 is  odd numbers and we need to remove their multiples.In the 1st point,we have already removed the multiple of 2 so that we can ignore the even multiples of 2i+3.Now our goal is to deal with the odd multiples of 2i+3.Therefore,we want to delete the (2n+1)(2i+3),n=1,2,3,4......Of course we can not remove the 2i+3 itself.Then change the (2n+1)(2i+3) into the form 2N+3(I remembered that I often do it in my math proofs).The procedure is : (2n+1)(2i+3)=2n(2i+3)+2i+3=2[n(2i+3)+i]+3;This is a form of 2N+3(N is n(2i+3)+i).Because we use i as a index so what we pick the numbers located at N by the sieve method are the numbers located at n(2i+3)+i.Finally,we can write a program with the thinking above.

 1 #include <stdio.h>
 2 #define MAX 1000
 3 #define SAVE 0
 4 #define DELETE 1
 5 
 6 int sieve[1000]={0}; //all to SAVE
 7 
 8 int main()
 9 {
10     int i,k;
11     int prime;
12     int count=1;//The sum number of the prime numbers 
13     //2*i+3 is odd numbers
14     for(i=0;i<MAX;i++)
15     {
16         if(sieve[i]==SAVE) //it is a prime number 
17         {
18             //I have a problem here.Why are the front several numbers prime number after one or two sieve process such as 5 or 7 or 11? I just think they are prime nubmers without proving it.  
19             prime=i+i+3; 
20             count++;
21             for(k=prime+i;k<=MAX;k+=prime)
22                 sieve[k]=DELETE;
23         }
24     }
25     printf("%6d",2);
26 
27     for(i=0,k=2;i<MAX;i++)
28     {
29         if(sieve[i]==SAVE)
30         {
31             if(k>10) 
32             {
33                 printf("\n"); 
34                 k=1;
35             }
36             int temp=i+i+3;
37             printf("%6d",temp);
38             k++;
39         }
40     }
41     printf("\nThe sum number is %d \n",count);
42     return 0;
43 }

Summary:I am poor in the problems with math knowledge.I can hardly come up with a great idea to solve it.The root cause for this is that I don't have enough math knowlege and the lack of practice.From now on,I will practice more algorithm or data structure problems with math and program,even some projects.

Reference material: C语言名题精选百则技巧篇 in Chinese.