Never been to DZone Snippets before?

Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

About this user

Alexandru Scvortov

« Newer Snippets
Older Snippets »
Showing 1-4 of 4 total  RSS 

Gaussian Elimination in C

This is a simple implementation of the Gaussian Elimination algorithm for solving n linear equations with n unknowns.

Further explanation is given here.

   1  
   2  #include <stdio.h>
   3  
   4  int n;
   5  float a[10][11];
   6  
   7  void forwardSubstitution() {
   8  	int i, j, k, max;
   9  	float t;
  10  	for (i = 0; i < n; ++i) {
  11  		max = i;
  12  		for (j = i + 1; j < n; ++j)
  13  			if (a[j][i] > a[max][i])
  14  				max = j;
  15  		
  16  		for (j = 0; j < n + 1; ++j) {
  17  			t = a[max][j];
  18  			a[max][j] = a[i][j];
  19  			a[i][j] = t;
  20  		}
  21  		
  22  		for (j = n; j >= i; --j)
  23  			for (k = i + 1; k < n; ++k)
  24  				a[k][j] -= a[k][i]/a[i][i] * a[i][j];
  25  
  26  /*		for (k = 0; k < n; ++k) {
  27  			for (j = 0; j < n + 1; ++j)
  28  				printf("%.2f\t", a[k][j]);
  29  			printf("\n");
  30  		}*/
  31  	}
  32  }
  33  
  34  void reverseElimination() {
  35  	int i, j;
  36  	for (i = n - 1; i >= 0; --i) {
  37  		a[i][n] = a[i][n] / a[i][i];
  38  		a[i][i] = 1;
  39  		for (j = i - 1; j >= 0; --j) {
  40  			a[j][n] -= a[j][i] * a[i][n];
  41  			a[j][i] = 0;
  42  		}
  43  	}
  44  }
  45  
  46  void gauss() {
  47  	int i, j;
  48  
  49  	forwardSubstitution();
  50  	reverseElimination();
  51  	
  52  	for (i = 0; i < n; ++i) {
  53  		for (j = 0; j < n + 1; ++j)
  54  			printf("%.2f\t", a[i][j]);
  55  		printf("\n");
  56  	}
  57  }
  58  
  59  int main(int argc, char *argv[]) {
  60  	int i, j;
  61  
  62  	FILE *fin = fopen("gauss.in", "r");
  63  	fscanf(fin, "%d", &n);
  64  	for (i = 0; i < n; ++i)
  65  		for (j = 0; j < n + 1; ++j)
  66  			fscanf(fin, "%f", &a[i][j]);
  67  	fclose(fin);
  68  	
  69  	gauss();
  70  	
  71  	return 0;
  72  }
  73
to c algorithm linear equation gauss elimination solve solving equations by scvalex on Dec 11, 2007

Gaussian Elimination in C

This is a simple implementation of the Gaussian Elimination algorithm for solving n linear equations with n unknowns.

Further explanation is given here.

   1  
   2  #include <stdio.h>
   3  
   4  int n;
   5  float a[10][11];
   6  
   7  void forwardSubstitution() {
   8  	int i, j, k, max;
   9  	float t;
  10  	for (i = 0; i < n; ++i) {
  11  		max = i;
  12  		for (j = i + 1; j < n; ++j)
  13  			if (a[j][i] > a[max][i])
  14  				max = j;
  15  		
  16  		for (j = 0; j < n + 1; ++j) {
  17  			t = a[max][j];
  18  			a[max][j] = a[i][j];
  19  			a[i][j] = t;
  20  		}
  21  		
  22  		for (j = n; j >= i; --j)
  23  			for (k = i + 1; k < n; ++k)
  24  				a[k][j] -= a[k][i]/a[i][i] * a[i][j];
  25  
  26  /*		for (k = 0; k < n; ++k) {
  27  			for (j = 0; j < n + 1; ++j)
  28  				printf("%.2f\t", a[k][j]);
  29  			printf("\n");
  30  		}*/
  31  	}
  32  }
  33  
  34  void reverseElimination() {
  35  	int i, j;
  36  	for (i = n - 1; i >= 0; --i) {
  37  		a[i][n] = a[i][n] / a[i][i];
  38  		a[i][i] = 1;
  39  		for (j = i - 1; j >= 0; --j) {
  40  			a[j][n] -= a[j][i] * a[i][n];
  41  			a[j][i] = 0;
  42  		}
  43  	}
  44  }
  45  
  46  void gauss() {
  47  	int i, j;
  48  
  49  	forwardSubstitution();
  50  	reverseElimination();
  51  	
  52  	for (i = 0; i < n; ++i) {
  53  		for (j = 0; j < n + 1; ++j)
  54  			printf("%.2f\t", a[i][j]);
  55  		printf("\n");
  56  	}
  57  }
  58  
  59  int main(int argc, char *argv[]) {
  60  	int i, j;
  61  
  62  	FILE *fin = fopen("gauss.in", "r");
  63  	fscanf(fin, "%d", &n);
  64  	for (i = 0; i < n; ++i)
  65  		for (j = 0; j < n + 1; ++j)
  66  			fscanf(fin, "%f", &a[i][j]);
  67  	fclose(fin);
  68  	
  69  	gauss();
  70  	
  71  	return 0;
  72  }
  73
to linear equation gauss elimination by scvalex on Dec 11, 2007

Gaussian Elimination in C

This is a simple implementation of the Gaussian Elimination algorithm for solving n linear equations with n unknowns.

Further explanation is given here.

   1  
   2  #include <stdio.h>
   3  
   4  int n;
   5  float a[10][11];
   6  
   7  void forwardSubstitution() {
   8  	int i, j, k, max;
   9  	float t;
  10  	for (i = 0; i < n; ++i) {
  11  		max = i;
  12  		for (j = i + 1; j < n; ++j)
  13  			if (a[j][i] > a[max][i])
  14  				max = j;
  15  		
  16  		for (j = 0; j < n + 1; ++j) {
  17  			t = a[max][j];
  18  			a[max][j] = a[i][j];
  19  			a[i][j] = t;
  20  		}
  21  		
  22  		for (j = n; j >= i; --j)
  23  			for (k = i + 1; k < n; ++k)
  24  				a[k][j] -= a[k][i]/a[i][i] * a[i][j];
  25  
  26  /*		for (k = 0; k < n; ++k) {
  27  			for (j = 0; j < n + 1; ++j)
  28  				printf("%.2f\t", a[k][j]);
  29  			printf("\n");
  30  		}*/
  31  	}
  32  }
  33  
  34  void reverseElimination() {
  35  	int i, j;
  36  	for (i = n - 1; i >= 0; --i) {
  37  		a[i][n] = a[i][n] / a[i][i];
  38  		a[i][i] = 1;
  39  		for (j = i - 1; j >= 0; --j) {
  40  			a[j][n] -= a[j][i] * a[i][n];
  41  			a[j][i] = 0;
  42  		}
  43  	}
  44  }
  45  
  46  void gauss() {
  47  	int i, j;
  48  
  49  	forwardSubstitution();
  50  	reverseElimination();
  51  	
  52  	for (i = 0; i < n; ++i) {
  53  		for (j = 0; j < n + 1; ++j)
  54  			printf("%.2f\t", a[i][j]);
  55  		printf("\n");
  56  	}
  57  }
  58  
  59  int main(int argc, char *argv[]) {
  60  	int i, j;
  61  
  62  	FILE *fin = fopen("gauss.in", "r");
  63  	fscanf(fin, "%d", &n);
  64  	for (i = 0; i < n; ++i)
  65  		for (j = 0; j < n + 1; ++j)
  66  			fscanf(fin, "%f", &a[i][j]);
  67  	fclose(fin);
  68  	
  69  	gauss();
  70  	
  71  	return 0;
  72  }
  73
to linear equation gauss elimination by scvalex on Dec 11, 2007

Modular linear equation solver

Prints the roots of this equation:
ax = b (mod n)

Relies on Euclid's extended algorithm:
http://snippets.dzone.com/posts/show/4192

   1  
   2  def solveLinearModularEquation(a, b, n):
   3    d, xx, yy = euclidExtended(a, n)
   4    if (b % d == 0):
   5      x0 = (xx * (b / d)) % n
   6      for i in xrange(0, d):
   7        print (x0 + i * (n / d)) % n,
   8    else:
   9      print "No solution"
  10    print
to python euclid linear equation modular by scvalex on Jun 22, 2007
« Newer Snippets
Older Snippets »
Showing 1-4 of 4 total  RSS