[C,C++] Gauss, Gauss-Jodan

이산수학시간에 배운 가우스와 가우스조단 소거법을 이용하여 연립방정식의 해를 구하고, 역행렬을 구하는 방식을
C++로 구현해야 했다.
사실, 가우스와 가우스 조던 소거법은 네이버 지식인에 검색하면 똑같은 것으로,
그것도 최적화된 것으로 간단하고 정말 멋진 코드들이 많다. (근데 막상보면 다 같은 내용을 돌려먹는 느낌....)
소스보기 : http://kin.search.naver.com/search.naver?where=kin&sm=tab_jum&query=%uAC00%uC6B0%uC2A4%20c

그냥 쓰고 싶었지만... 역시나 많은 이들이 그대로 사용할 것같아 직접 노가다로 작성하였다.
구현도중 특히 어려운 점은 없었으나, 역시 알고리즘 짜는 부분에서 많은 시간을 보냈다.
특히 가우스 조단까지 가는데 i,j,k,h 4개의 변수로 와리가리 하는데....
정말 멍하니 모니터를 바라보면서 한 4시간은 생각을 해본 것 같다. 뭐 그래도 짱구를 굴리다보니 결국 돌아가긴 돌아가더라^^
아... 정말이지 알고리즘은 싫다.. 전 알고리즘 시간에도 느낀 것이었지만.... 이미 정해진것 배우는건 괜찮은데 새로 짜려니 머리가 잘 안돌아간다... 아아~ㅠ.ㅜ;

아무튼 가우스를 짜면 조던소거법도 무난히 해결되고 덩달아 역행렬도 간단한 조작으로 구하는 것이 가능해졌다.

[요구사항]
hw1_in1, hw_in2의 파일로부터 정보를 읽어들여 가우스(Gauss)와  가우스 조던(Gauss-Jodan)을 사용하고 hw1_out1, hw1_out2에 결과값을 출력하시오.
hw1_in1의 내용은 다음과 같다. (예일뿐임, 형식에 맞춘 모든수가 가능해야함. 10개이상의 변수도 처리가능해야함)

3           
x - y + 2z = 0
2x + y - z = 2
x + y + z = -1

첫번째 숫자는 총 구하려고 하는 변수의 수.
그 다음부터는 방정식이 나온다. 변수의 수만큼 식은 존재한다.(그래야 해를 구할 수 있으므로.)

hw1_in2의 내용은 다음과 같다.(예일 뿐임, 형식에 맞춘 모든 수가 가능해야함.)

3
1 2 7
2 5 3
6 3 7

처음 하나의 숫자는 정방행렬의 행(또는 열)의 갯수이다. 3일 경우 3x3 행렬을 말한다. 단 이 숫자는 3이하로 제한한다.

hw1_in1의 방정식들은 가우스와 가우스 조던방법을 이용하여 각 변수의 해를 구한다. 그후 hw1_out1에 출력한다.
hw1_in2의 행렬을 이용하여 행렬식을 구하고 역행렬의 존재 유무와 역행렬을 구한다. 그후 hw1_out2에 출력한다.

[구현내용]
전체적으로 보기쉽게(?) 하기 위해 함수화하여 필요한 기능이 바로 수행되는 것을 확인할 수 있도록 하여
main부분을 최소화 시켰다. 오히려 지나치게 많은 함수의 선언이 더 복잡해져 보일 수도 있지만, 이해하고 설명하기에는 더 편한 것 같다.
일부의 배열은 크기가 정해져있고(역행렬때 쓰이는 배열), 그외는 동적으로 할당하여 사용하게 된다.
모두 main밖에서 선언하여 어느 함수에서든 접근가능하게 하여 함수 매개변수의 수를 줄였다.
가우스나 가우스 조던은 함수로 모듈화되어 있으니,
그 과정을 직접 설명하는 것보다 궁금한사람(?)은 직접 따져가며 생각해보는게 훨씬 이해가 잘 갈 것 같다.
파일의 입출력 부분에서는 억지로 gets로 스트링을 받은후 스트링 쪼개기를 사용했는데, 사실 처음 링크했던 네이버 지식인에 등록된 부분에서는 getc를 이용하여 정말 효율적으로 받아들일 수 있다. (난 좀 다르게 할려다가 캐고생.)

다항싱을 입력받은 후 Parsing하는 부분에서도 짱구를 꽤나 굴려야 했었다.
다항식을 배열에 배치하여야 하기 때문에 다양한 방법이 존재함에도 불구하고 꽤나 복잡했다.
특히 0일경우 1일경우 두자리일 경우 한자리이고 마이너스일 경우등등등 이외로 예외상황이 많기에 더 복잡해진 느낌이다.

가우스 알고리즘을 억지로 만들어내느라 정말 머리 터지는줄 알았다.
(최적이 있으면서도 다시 지어내야한다는 슬픈 현실-.ㅜ;, 한번만들면 정말 두번 떠올리고 싶지 않다고나 할까 ㅠ.ㅜ;)
for문이 많이 나오면 어지러운건 역시 처음이나 지금이나 마찬가지인듯 하다.

아무튼 가우스를 이용한 다항식의 결과값과, 매트릭스의 역행렬은 무난히 구해진다.
아쉬운점은 역행렬을 구할때 3x3까지만 구해지도록 프로그램밍을 해놓았다는 것이다.(시간이 부족해서 -.-;;)
무한대로 구하는 것도 재귀함수를 쓰면 쉬워질텐데 라고 생각은 했지만.... Pass

가우스 소거법을 모른다면, 알아보자.(아래사이트에서 ^^)
http://ko.wikipedia.org/wiki/%EA%B0%80%EC%9A%B0%EC%8A%A4_%EC%86%8C%EA%B1%B0%EB%B2%95

[작성환경 : Linux Fedora  작성툴 : Vi editor   컴파일러 : g++]

#include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> using namespace std; float **ary; float ary_in2[3][3]; float ary_temp22[2][2]; //for determinate float **inverseAry; void doInverseMatrix(int num); void doGaussForInverse(int num); void doGaussJodanForInverse(int num); void doGaussJodan(int num); void doGauss(int num); int readAndParsing(); int readAndParsing2(); void printGJResult(FILE* fp,int num); void printAry(FILE* fp,int num); void printAry_in2(FILE* fp,int num); void printAry_Inverse(FILE* fp,int num); void printAry_InverseResult(FILE* fp,int num); int determinantAry_temp22(); int getDeterminant(int num); void resultwrite_out1(int num); void resultwrite_out2(int num); int main() { int num,num2; // variable Number num=readAndParsing(); resultwrite_out1(num); num2=readAndParsing2(); resultwrite_out2(num2); printf("=======================================\n"); printf("File Read and Write and Operate Success\n"); printf("=======================================\n"); return 0; } void resultwrite_out2(int num) { FILE *fp; if((fp=fopen("hw1_out2","w"))==0) { perror("write file open Error\n"); exit(0); } fprintf(fp,"[Input hw1_in2]\n"); fprintf(fp,"\n============================\n After Parsing\n============================\n"); printAry_in2(fp,num); int x=getDeterminant(num); fprintf(fp,"============================\n After determinate Operation\n============================\n"); fprintf(fp,"|A| is %d\n",x); fprintf(fp,"============================\n Before GaussJodan\n============================\n"); doInverseMatrix(num); printAry_Inverse(fp,num); doGaussForInverse(num); doGaussJodanForInverse(num); fprintf(fp,"============================\n After GaussJodan\n============================\n"); printAry_Inverse(fp,num); fprintf(fp,"============================\n Result Inverse Matrix\n============================\n"); printAry_InverseResult(fp,num); } void resultwrite_out1(int num) { FILE *fp; if((fp=fopen("hw1_out1","w"))==0) { perror("write file open Error\n"); exit(0); } fprintf(fp,"[Input hw1_in1]\n"); fprintf(fp,"\n============================\n After Parsing\n============================\n"); printAry(fp,num); fprintf(fp,"\n============================\n After Gauss\n============================\n"); doGauss(num); printAry(fp,num); fprintf(fp,"\n============================\n After GaussJodan\n============================\n"); doGaussJodan(num); printAry(fp,num); printGJResult(fp,num); } void doInverseMatrix(int num) { int i,j; inverseAry=new float *[num]; for(i=0;i<num;i++){ inverseAry[i]=new float[num*2]; } for(i=0;i<num;i++){ //init inverseAry for(j=0;j<num*2;j++){ if(j<num){ inverseAry[i][j]=ary_in2[i][j]; } else{ if(((j-i)==num)||(i==j)){ inverseAry[i][j]=1; } else{ inverseAry[i][j]=0; } } } } }; int getDeterminant(int num) { int i,j; if(num==2){ for(i=0;i<2;i++){ for(j=0;j<2;j++){ ary_temp22[i][j]=ary_in2[i][j]; } } return determinantAry_temp22(); } else if(num==3) { for(i=0;i<num-1;i++){ for(j=0;j<num-1;j++) ary_temp22[i][j]=ary_in2[i+1][j+1]; } int v1=determinantAry_temp22(); for(i=0;i<num-1;i++){ for(j=0;j<num-1;j++) ary_temp22[i][j]=ary_in2[i+1][j*2]; } int v2=determinantAry_temp22(); for(i=0;i<num-1;i++){ for(j=0;j<num-1;j++) ary_temp22[i][j]=ary_in2[i+1][j]; } int v3=determinantAry_temp22(); return (int)((ary_in2[0][0]*v1)+(-1)*(ary_in2[0][1]*v2)+(ary_in2[0][2]*v3)); } return 0; }; void doGaussJodan(int num) { int i,j,k,h; for(h=num-1;h>=0;h--) { float temp=ary[h][h]; for(j=h-1;j>=0;j--) { temp=-(ary[j][h]/ary[h][h]); //calculator for(i=0;i<num+1;i++) { ary[j][i]=temp*ary[h][i]+ary[j][i]; } } } } void doGaussJodanForInverse(int num) { int i,j,k,h; for(h=num-1;h>=0;h--) { float temp=inverseAry[h][h]; for(j=h-1;j>=0;j--) { temp=-(inverseAry[j][h]/inverseAry[h][h]); //calculator for(i=0;i<num*2;i++) { inverseAry[j][i]=temp*inverseAry[h][i]+inverseAry[j][i]; } } } } void doGaussForInverse(int num) { int i,j,k,h; for(h=0;h<num;h++) { float temp=inverseAry[h][h]; for(k=0;k<num*2;k++) //Setting by 1 { if(inverseAry[h][k]==0)continue; inverseAry[h][k]=inverseAry[h][k]/temp; } for(j=h+1;j<num;j++) { temp=-(inverseAry[j][h]/inverseAry[h][h]); //calculator for(i=0;i<num*2;i++) { inverseAry[j][i]=temp*inverseAry[h][i]+inverseAry[j][i]; } } } }; void doGauss(int num) { int i,j,k,h; for(h=0;h<num;h++) { float temp=ary[h][h]; for(k=0;k<num+1;k++) //Setting by 1 { //if(ary[h][k]==0)continue; ary[h][k]=ary[h][k]/temp; } for(j=h+1;j<num;j++) { temp=-(ary[j][h]/ary[h][h]); //calculator for(i=0;i<num+1;i++) { ary[j][i]=temp*ary[h][i]+ary[j][i]; } } } float *temp=new float[num]; temp[num]=ary[num-1][num]; cout<<temp[num]; }; int readAndParsing2() { FILE* fp; char buf[10]; char temp[10]; int num,i,j=0; char *token; //strset(buf,0); //strset(temp,0); if((fp=fopen("hw1_in2","r"))==NULL){ perror("Fail open file [hw1_in2]\n"); } fgets(buf,10,fp); num=atoi(buf); while(fgets(buf,10,fp)!=NULL) { token=strtok(buf," "); strcpy(temp,token); ary_in2[j][0]=atoi(temp); for(i=1;i<num;i++) { token=strtok(NULL," "); strcpy(temp,token); ary_in2[j][i]=atoi(temp); } j++; } return num; } int readAndParsing() //return is "counted variable Num" { FILE* fp; char buf[50]; int num,i,j; if((fp=fopen("hw1_in1","r"))==NULL){ perror("Fail open file [hw1_in1]\n"); } fgets(buf,100,fp); num=atoi(buf); ary=new float *[num]; for(i=0;i<num;i++){ ary[i]=new float[num+1]; } int row=0,column=0; while(fgets(buf,100,fp)!=NULL) { // strlwr(buf); int len=strlen(buf); char temp[10]; //strset(temp,0); int i=0,j=0,k=0; while(k<len+1){ if(buf[i]==' '){i++;} //ignore 'Space' if(buf[i]=='='){i++;j=0;} //ignore '=' else if((buf[i]>='a'&&buf[i]<='z')||(buf[i]=='\n'||buf[i]==0)){ temp[j]=buf[i]; //처리부분 if(temp[0]==0)break; // End of String int sign=1; float value; if((temp[0]=='-')&&(temp[1]>='a' &&temp[1]<='z')){sign=-1;} if(((value=atof(temp))==0)&&((temp[1]>='a'&& temp[1]<='z')||(temp[0]>='a'&& temp[0]<='z'))){value=1;} ary[row][column]=sign*value; column++; //strset(temp,0); i++,j=0; } else{ temp[j]=buf[i]; i++,j++; } k++; } row++; column=0; //cout<<buf; //for check } return num; }; void printGJResult(FILE* fp,int num) { int i; fprintf(fp,"\n"); for(i=0;i<num;i++) { fprintf(fp,"[%d] Value is %.2f\n",i+1,ary[i][num]); } }; void printAry_Inverse(FILE* fp,int num) { int i,j; for(i=0;i<num ;i++){ for(j=0;j<num*2;j++){ if(j==num) { fprintf(fp," | "); } fprintf(fp,"%.2lf ",inverseAry[i][j]); } fprintf(fp,"\n"); } }; void printAry_InverseResult(FILE* fp,int num) { int i,j; for(i=0;i<num ;i++){ for(j=num;j<num*2;j++){ fprintf(fp,"%.2lf ",inverseAry[i][j]); } fprintf(fp,"\n"); } }; void printAry_in2(FILE* fp,int num) { int i,j; for(i=0;i<num ;i++){ for(j=0;j<num;j++){ fprintf(fp,"%.2lf ",ary_in2[i][j]); } fprintf(fp,"\n"); } }; int determinantAry_temp22() { return (int)(ary_temp22[0][0]*ary_temp22[1][1]-ary_temp22[0][1]*ary_temp22[1][0]); }; void printAry(FILE* fp,int num) //View Static Array { int i,j; for(i=0;i<num ;i++){ for(j=0;j<num+1;j++){ if(j==num) { fprintf(fp," | "); } fprintf(fp,"%.2lf ",ary[i][j]); } fprintf(fp,"\n"); } };

<실행시 나오는 화면, 파일에 출력하기 때문에 성공여부만 화면에 출력함>

<결과물인 hw1_out1을 출력해본 모습, 다음과 같은 결과값이 저장되어 있다.>

<결과물인 hw1_out2를 출력한 모습, 역행렬이 구해진다.>