교묘하게 두 갈래 나무 원리로 집합의 멱집을 구하다
4502 단어 두 갈래 나무
멱집은 집합론에서 중요한 개념으로 집합은 다음과 같이 정의된다.
집합은 하나의 원 개념으로 연구 대상의 전체를 통상적으로 대문자로 집합을 나타낸다.집합 A, 집합 B.집합의 표시 방식은 두 가지가 있는데, 각각 예거법과 묘사법이다.
만약 1보다 작고 5보다 작은 정수로 구성된 집합이라면 예를 들면 다음과 같이 표시할 수 있다.
이 집합을 A로 설정하면 A={2,3,4}
설명은 다음과 같습니다.
이 집합을 A로 설정하면 A={x | 1
이제 우리는 마침내 멱집의 개념을 끌어낼 수 있게 되었다. 멱집은 하나의 집합의 모든 자집으로 구성된 집합이 이 집합의 멱집이 된다고 정의되었다.이를 통해 알 수 있듯이 멱집합은 집합의 집합이다.만약 집합 A={1,2,3}, 그러면 그의 멱집합은 P(A)={{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, n개의 원소가 있는 집합, 그의 멱집합은 2가 있다
n개의 원소, 이 원소들은 모두 이 집합의 서브집합이다.
위의 간단한 소개를 통해 알 수 있듯이 하나의 집합을 요구하는 멱집합은 이 집합에 포함된 원소가 비교적 적을 때 신속하게 알 수 있지만 집합 원소가 증가할 때 멱집합의 원소는 기하급수로 증가하여 집합의 멱집합을 구하는 것은 매우 어려워진다.
여기서 나는 집합의 멱집을 구하는 프로그램을 만들었는데 두 갈래 나무를 두루 돌아다니며 집합의 멱집을 구해냈다.프로그램의 원리는 멱집 원소를 구하는 과정을 먼저 n+1의 깊이가 있는 만 두 갈래 나무를 훑어보는 것으로 간주하고 뿌리 노드부터 왼쪽 아이를 방문하여 멱집 원소(집합의 서브집합)에 집합된 첫 번째 원소를 포함하지 않고 오른쪽 아이를 방문하면 멱집 원소에 집합된 첫 번째 원소를 포함한다. 이렇게 하면 두 갈래 나무의 두 번째 층에서 집합된 첫 번째 원소에 대한 취사를 완성하고 순서대로 유추한다.n+1층, 즉 두 갈래 나무의 잎 노드에 도달했을 때 모든 원소를 집합하는 취사를 완성했고 이때 취사 후의 멱집 원소를 출력한다.두 갈래 나무가 가득한 n+1층은 모두 2
n개의 잎 노드는 집합의 2를 대표한다
n개의 멱집 원소는 온전한 두 갈래 나무가 가득한 잎 노드를 두루 출력하면 우리가 요구하는 멱집을 얻을 수 있다.
프로그램은 다음과 같습니다.
1 /*
2 code by: EricYou
3 date: 2006.1.7
4 blog: http://www.cnblogs.com/yxin1322오
6 */
7
8 #include <stdio.h>
9 #include <string.h>
10
11 #define MAX_LENGTH 100 /* */
12
13 void PowerSet(char*, int, char*,int *);
14
15 int main()
16 {
17 char a[MAX_LENGTH]; /* */
18 char set[MAX_LENGTH]={"\0"}; /* */
19 int NumOfPowerSet=0; /* */
20
21 printf("Input the elements:");
22 scanf("%s",a);
23
24 printf("----------------------------
");
25 PowerSet(a,0,set,&NumOfPowerSet); /* */
26 printf("----------------------------
");
27
28 printf("Number of PowerSet: %d
",NumOfPowerSet);
29
30 return 1;
31 }
32
33 /*
34 ： char* a :
35 int i : i
36 char* set :
37 int* Num :
38 */
39 void PowerSet(char* a, int i, char* set, int * Num)
40 {
41 char TempSet[MAX_LENGTH];
42
43 strcpy(TempSet,set);
44 if(i>=strlen(a))
45 {
46 printf("{%s}
",set);
47 (*Num)++;
48 }
49 else
50 {
51 PowerSet(a,i+1,TempSet,Num);
52 strncat(TempSet,(a+i),1);
53 PowerSet(a,i+1,TempSet,Num);
54 }
55 }
：ABCD, {A,B,C,D}, ：Input the elements:ABCD
-------------------------
{}
{D}
{C}
{CD}
{B}
{BD}
{BC}
{BCD}
{A}
{AD}
{AC}
{ACD}
{AB}
{ABD}
{ABC}
{ABCD}
-------------------------
Number of PowerSet: 16이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
