가우스 소원 법 (Gauss Elimination) 분석 & 문제 풀이 & 템 플 릿
31588 단어 Mina
가우스 소원 법 은 선형 대수 중의 한 알고리즘 으로 선형 방정식 조 를 풀 수 있 고 행렬 의 질 서 를 구 할 수 있 으 며 역 방진 의 역 행렬 을 구 할 수 있다.가우스 소원 법의 원 리 는 초등 행 변환 으로 확대 행렬 을 만 들 면 AX = B 와 CX = D 는 동 해 방정식 이다.그래서 우 리 는 초등 행 변환 으로 확대 행렬 을 행 계단 진 으로 바 꾼 다음 에 다시 방정식 의 해 를 구 할 수 있다.
이상 은 선형 대수 과목 의 회고 이 고 다음은 고 스 소원 법 이 프로 그래 밍 에서 의 응용 을 말한다.
먼저, 프로그램 에서 고 스 소원 법의 절 차 를 소개 한다. (우 리 는 방정식 그룹 에서 방정식 의 개 수 는 equ 이 고 변 원 의 개 수 는 var 이다. 주의: 일반적인 상황 에서 n 개의 방정식, n 개의 변 원 이지 만 일부 문 제 는 고의로 방정식 수 와 변 원 수 를 다 르 게 한다)
1. 방정식 그룹 을 증폭 행렬 로 전환한다.
2. 초등 행 변환 을 이용 하여 확장 행렬 을 행 계단 진 으로 전환한다.매 거 k 는 0 에서 equ – 1 까지 현재 처 리 된 열 은 col (초기 0) 이 고 매번 k 줄 아래 (k 줄 포함) 를 찾 을 때마다 col 열 에서 요소 의 절대 값 이 가장 큰 열 은 k 줄 과 교환 합 니 다.col 열 에 있 는 요소 가 모두 0 이면 col + 1 열 을 처리 하고 k 는 변 하지 않 습 니 다.
3. 행 계단 진 으로 전환 하여 상황 을 판단 한다.
① 무 해 당 방정식 에 나타 나 는 (0, 0,..., 0, a) 형식 과 a! =0 시 에는 설명 이 풀 리 지 않 는 다.
② 유일한 해결 조건 은 k = equ 로 계단 진 이 엄격 한 상 삼각 진 을 형성 했다.회 대 를 이용 하여 하나하나 해 집 을 구하 다.
③ 무한 해.조건 은 k < equ, 즉 엄격 한 상 삼각형 을 형성 할 수 없고 자유 변 원 의 개 수 는 equ – k 이지 만 어떤 변 원 이 부족 하지 않 은 지 판단 해 야 한다. 여기 서 이러한 해법 을 따로 소개 합 니 다. 우선, 자유 변 원 은 var - k 개가 있 습 니 다. 즉, 불확실 한 변 원 은 적어도 var - k 개가 있 습 니 다.우 리 는 먼저 모든 변 원 을 불확실 하 게 여 긴 다.각 방정식 에서 변 원 의 개 수 를 확정 하지 못 하고 1 개 이상 이면 이 방정식 은 풀 수 없다.만약 1 개의 변 원 만 있다 면, 이 변 원 은 바로 변 원 을 확정 하기 위해 구 할 수 있다.이상 에서 소개 한 것 은 정수 선형 방정식 조 의 구법 이 고 복잡 도 는 O (n3) 이다.부동 소수점 선형 방정식 그룹의 구법 은 유사 하지만 0 여 부 를 판단 할 때 EPS 를 넣 어 정밀도 문 제 를 없 애 야 한다.
다음은 OJ 상의 고 스 소원 법 으로 선형 방정식 조 의 문 제 를 설명 한다.
POJ 1222 EXTENDED LIGHTS OUT http://acm.pku.edu.cn/JudgeOnline/problem?id=1222 POJ 1681 Painter 's Problem http://acm.pku.edu.cn/JudgeOnline/problem?id=1681 POJ 1753 플 립 게임 http://acm.pku.edu.cn/JudgeOnline/problem?id=1753 POJ 1830 스위치 문제 http://acm.pku.edu.cn/JudgeOnline/problem?id=1830
POJ 3185 The Water Bowls
http://acm.pku.edu.cn/JudgeOnline/problem?id=3185 창문 을 닫 고 불 을 끄 는 문 제 는 전형 적 인 선형 방정식 팀 의 문 제 를 해결 하 는 것 이다.방정식 수 와 변 수 는 모두 줄 수 * 열 수 이 고 템 플 릿 을 직접 만들어 서 풀 면 됩 니 다.그러나 무한 해 가 발생 했 을 때 매 거 해 야 하 는 상황 은 어떤 해 가 문제 의 요구 가 가장 좋 은 지 판단 할 수 없 기 때문이다.POJ 2947 Widget Factory http://acm.pku.edu.cn/JudgeOnline/problem?id=2947 는 동 여 방정식 그룹 문 제 를 풀 었 다.일반적인 구 해선 성 방정식 그룹의 문제 와 유사 하 므 로 구 해 과정 에서 나머지 를 넣 으 면 된다.주의: 방정식 팀 이 유일 하 게 풀 때 구 해 과정 에서 [3, 9] 사이 에 풀 도록 해 야 합 니 다.POJ 1166 The Clocks http://acm.pku.edu.cn/JudgeOnline/problem?id=1166 고전 BFS 문 제 는 여러 가지 해법 이 있 고 역 행렬 로 행렬 을 곱 할 수도 있다.그러나 이 문 제 는 고 스 소원 법 으로 해결 하 는 데 문제 가 있 는 것 같 습 니 다.그럼 마지막 에 구 한 답 이 맞다 고 장담 할 수 는 없 지...........................................................................
POJ 2065 SETI http://acm.pku.edu.cn/JudgeOnline/problem?id=2065 역시 동 여 방정식 그룹 문 제 를 구 하 는 것 이다. 문제 중의 p 는 소수 이기 때문에 직접 구 해 할 때 나머지 를 취하 고 템 플 릿 으로 구 해 하면 된다.(AC 는 사람 이 적 지만 물 을 비교 하 는 문제 입 니 다.)
POJ 1487 Single - Player Games http://acm.pku.edu.cn/JudgeOnline/problem?id=1487 번 거 로 운 문제....................................................................나 는 창고 + 재 귀적 인 방법 으로 분해 했다.먼저 창고 의 사상 으로 이 결산 점 의 아이 수 를 구 한 다음 에 돌아 와 서 각 아이들 을 구해낸다.이 문제 풀이 방정식 팀 도 남 다 릅 니 다. 먼저 부동 소수점 방정식 팀 을 푸 는 것 입 니 다. 정밀도 문 제 를 주의 한 다음 에 불확실 한 변 원 을 묻 고 앞에서 말 한 방법 으로 풀 어야 합 니 다.한 번 고생 한 후에 이 문 제 는 6000 + B 라 고 썼 다. 게다가 어 려 운 것 은 자 이언 트 C + WA, G + AC 였 다. 아마도 정밀도 의 문 제 였 을 것 이다. 이 문 제 를 보면 이 코드 를 보면 고 칠 욕망 이 없 었 다. hdu OJ 2449 http://acm.hdu.edu.cn/showproblem.php?pid=2449 하 얼 빈 라 이브 경기 의 순 고 스 문 제 였 다. 그 당시 학 우 는 1 시간 넘 게 두 드 렸 다. 주로 점수 류 를 쓰 고 높 은 템 플 릿 을 만 들 었 다.해결 ~ ~ 0 과 음수 의 출력 을 주의 하 시 면 됩 니 다.
fze OJ 1704 http://acm.fzu.edu.cn/problem.php?pid=1704 복대 월 경기 의 한 문 제 는 전형 적 인 스위치 문제 이지 만 방정식 수 와 변 원 수 는 다르다 (템 플 릿 을 시험 할 때 ~). 마지막 으로 확대 진의 단 계 를 요구 하고 높 은 정밀도 로 사용 해 야 한다 ~ ~
Sgu 275 To xor or not to xor http://acm.sgu.ru/problem.php?contest=0&problem=275 문제 풀이: http://hi.baidu.com/czyuan%5Facm/blog/item/be3403d32549633d970a16ee.html 여기 서 자신 이 쓴 만 족 스 러 운 정수 선형 방정식 그룹의 템 플 릿 을 제공 합 니 다 (부동 소수점 이 유사 하면 제공 하지 않 습 니 다) ~
1 /* . */
2 #include <iostream>
3 #include <string>
4 #include <cmath>
5 using namespace std;
6 const int maxn = 105;
7 int equ, var; // equ ，var 。 equ, 0 equ - 1， var + 1， 0 var.
8 int a[maxn][maxn];
9 int x[maxn]; // .
10 bool free_x[maxn]; // .
11 int free_num;
12 void Debug(void)
13 {
14 int i, j;
15 for (i = 0; i < equ; i++)
16 {
17 for (j = 0; j < var + 1; j++)
18 {
19 cout << a[i][j] << " ";
20 }
21 cout << endl;
22 }
23 cout << endl;
24 }
25 inline int gcd(int a, int b)
26 {
27 int t;
28 while (b != 0)
29 {
30 t = b;
31 b = a % b;
32 a = t;
33 }
34 return a;
35 }
36 inline int lcm(int a, int b)
37 {
38 return a * b / gcd(a, b);
39 }
40 // (Gauss-Jordan elimination).(-2 ， ，-1 ，0 ， 0 ， )
41 int Gauss(void)
42 {
43 int i, j, k;
44 int max_r; // .
45 int col; // .
46 int ta, tb;
47 int LCM;
48 int temp;
49 int free_x_num;
50 int free_index;
51 // .
52 col = 0; // .
53 for (k = 0; k < equ && col < var; k++, col++)
54 { // .
55 // col k .( )
56 max_r = k;
57 for (i = k + 1; i < equ; i++)
58 {
59 if (abs(a[i][col]) > abs(a[max_r][col])) max_r = i;
60 }
61 if (max_r != k)
62 { // k .
63 for (j = k; j < var + 1; j++) swap(a[k][j], a[max_r][j]);
64 }
65 if (a[k][col] == 0)
66 { // col k 0 ， .
67 k--; continue;
68 }
69 for (i = k + 1; i < equ; i++)
70 { // .
71 if (a[i][col] != 0)
72 {
73 LCM = lcm(abs(a[i][col]), abs(a[k][col]));
74 ta = LCM / abs(a[i][col]), tb = LCM / abs(a[k][col]);
75 if (a[i][col] * a[k][col] < 0) tb = -tb; // .
76 for (j = col; j < var + 1; j++)
77 {
78 a[i][j] = a[i][j] * ta - a[k][j] * tb;
79 }
80 }
81 }
82 }
83 Debug();
84 // 1. : (0, 0, ..., a) (a != 0).
85 for (i = k; i < equ; i++)
86 { // ， ， ， .
87 if (a[i][col] != 0) return -1;
88 }
89 // 2. : var * (var + 1) (0, 0, ..., 0) ， .
90 // .
91 if (k < var)
92 {
93 // ， var - k ， var - k .
94 for (i = k - 1; i >= 0; i--)
95 {
96 // i (0, 0, ..., 0) ， k equ .
97 // ， i (0, 0, ..., a), a != 0 ， .
98 free_x_num = 0; // ， 1 ， ， .
99 for (j = 0; j < var; j++)
100 {
101 if (a[i][j] != 0 && free_x[j]) free_x_num++, free_index = j;
102 }
103 if (free_x_num > 1) continue; // .
104 // free_index， ， .
105 temp = a[i][var];
106 for (j = 0; j < var; j++)
107 {
108 if (a[i][j] != 0 && j != free_index) temp -= a[i][j] * x[j];
109 }
110 x[free_index] = temp / a[i][free_index]; // .
111 free_x[free_index] = 0; // .
112 }
113 return var - k; // var - k .
114 }
115 // 3. : var * (var + 1) .
116 // Xn-1, Xn-2 ... X0.
117 for (i = var - 1; i >= 0; i--)
118 {
119 temp = a[i][var];
120 for (j = i + 1; j < var; j++)
121 {
122 if (a[i][j] != 0) temp -= a[i][j] * x[j];
123 }
124 if (temp % a[i][i] != 0) return -2; // ， .
125 x[i] = temp / a[i][i];
126 }
127 return 0;
128 }
129 int main(void)
130 {
131 freopen("Input.txt", "r", stdin);
132 int i, j;
133 while (scanf("%d %d", &equ, &var) != EOF)
134 {
135 memset(a, 0, sizeof(a));
136 memset(x, 0, sizeof(x));
137 memset(free_x, 1, sizeof(free_x)); // .
138 for (i = 0; i < equ; i++)
139 {
140 for (j = 0; j < var + 1; j++)
141 {
142 scanf("%d", &a[i][j]);
143 }
144 }
145 // Debug();
146 free_num = Gauss();
147 if (free_num == -1) printf(" !
");
148 else if (free_num == -2) printf(" ， !
");
149 else if (free_num > 0)
150 {
151 printf(" ! %d
", free_num);
152 for (i = 0; i < var; i++)
153 {
154 if (free_x[i]) printf("x%d
", i + 1);
155 else printf("x%d: %d
", i + 1, x[i]);
156 }
157 }
158 else
159 {
160 for (i = 0; i < var; i++)
161 {
162 printf("x%d: %d
", i + 1, x[i]);
163 }
164 }
165 printf("
");
166 }
167 return 0;
168 }/ * czyuan 오리지널, 전재 출처 를 밝 혀 주세요. * /
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
미나, Netty, Twisted와 함께 배우기(1): 간단한 TCP 서버 구현위의 간단한 소개에서 이들의 공통된 특징인 이벤트-driven과 asynchronous를 발견할 수 있다.그것들은 모두 이벤트 구동, 비동기적인 네트워크 프로그래밍 프레임워크이다.이를 통해 알 수 있듯이 그들 사이의...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
