Algorithm's
- Tower of Hannoi
- Gaussian Elimination
- Matrix Multiplication
- Jhon trotter(permutation)
- Lexographic (permutation)
ALGORITHM TOWER OF HANOI as TOH (n,A,B,C)
{
//if only one disk has to moved
If(n=1) then
{
Write(“The peg moved from A to C”)
Return
}
else
{
//move top (n-1) disk from A to B using C
TOH(n-1,A,B,C)
// move remaining disk from B to C using A
TOH(n-1,B,C,A)
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace algorithms
{
class algo
{
int count;
public void towerofhannoi(int n,char w,char y,char z)
{
count++;
if (n == 1)
{
Console.WriteLine("disc moved from {0} to {1} using {2}", w,y,z);
}
else
{
towerofhannoi(n - 1, w,y,z);
towerofhannoi(1, w, z,y);
towerofhannoi(n - 1, y ,z, w );
}
}
}
class Program
{
static void Main(string[] args)
{
algo hanoi = new algo();
hanoi.towerofhannoi(3,'A', 'B' ,'C');
}
}
}
Gauss jordan row elimination algorithm:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace new_algo
{
class algo
{
int[,] a;
int tnum;
public algo(int no)
{
tnum = no;
a = new int[tnum, tnum + 1];
}
public void show()
{
Console.WriteLine("enter the value");
for (int i = 0; i < tnum; i++)
{
for (int j = 0; j < tnum + 1; j++)
{
Console.Write("M[{0},{1}]=", i, j);
a[i, j] = Convert.ToInt32(Console.ReadLine());
}
//a[i, a.GetLength(0)] = b[i];
}
Console.WriteLine("Displaying the values in Matrix");
for (int i = 0; i < tnum; i++)
{
for (int j = 0; j < tnum + 1; j++)
{
Console.Write("{0:F2}\t",a[ i, j]);
}
Console.WriteLine();//a[i, a.GetLength(0)] = b[i];
}
for (int i = 0; i < tnum; i++) // i representing no of rows
{
int temp = a[i, i];
for (int j = 0; j < tnum + 1; j++) // j representing no of columns
{
a[i, j] = a[i, j] / temp; // To Store Multipliers
}
for (int k = 0; k < tnum; k++) // k representing Rows on which operation is
{ // being performed. To create zeros below &
temp = a[k, i]; // above the main diagonal.
if (i != k)
{
for (int j = 0; j < tnum + 1; j++) // j represents no of colums on which operation is being performed
{
a[k, j] = a[k, j] - (temp * a[i, j]);
}
}
}
}
Console.WriteLine("solved matrix");
for (int i = 0; i < tnum; i++)
{
for (int j = 0; j < tnum + 1; j++)
{
Console.Write("{0:F2}\t", a[i, j]);
}
Console.WriteLine();//a[i, a.GetLength(0)] = b[i];
}
}
}
class Program
{
static void Main(string[] args)
{
algo a = new algo(2);
a.show();
}
}
}
MATRIX MULTIPLICATION ALGORITHM ON N*N ARRAYS
ALGORITHM MATRIX MULTIPLICATION (A[0…n-1], B[0…n-1])
//Multiplying two n*n matrices by the definition base algorithm
//Input: Two n*n matrices A and B
//Output: matrix C=A*B
For i<----0 to n-1 do
For j<----0 to n-1 do
C[i,j] <----0
For k<----0 to n-1 do
C[i,j] <---- C[i,j]+A[i,k]*B[k,j]
return C
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace algorithms
{
class Program
{
static void Main(string[] args)
{
int[,] a = new int[,]{{1,3,4},{6,2,4}};
int[,] b = new int[,]{{5,4,8},{3,2,7}};
int[,] c = new int[, ] {{5,4,8},{3,2,7}};
for (int i = 0; i < c.GetLength(0); i++)
{
for (int j = 0; j < c.GetLength(1); j++)
{
c[i, j] = 0;
for (int k = 0; k < b.GetLength(0); k++) // OR k<b.GetLength(0)
c[i, j] = c[i, j] + a[i, k] * b[k, j];
}
}
for (int row = 0; row < c.GetLength(0); row++)
{
for (int col = 0; col < c.GetLength(1); col++)
{
Console.WriteLine("{0}",c[row, col]);
Console.WriteLine();
}
}
}
}
}
Jhon trotter algorithm()
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace algo
{
public class JT
{
public void perm(int N)
{
int[] p = new int[N]; // permutation
int[] pi = new int[N]; // inverse permutation
int[] dir = new int[N]; // direction = +1 or -1
for (int i = 0; i < N; i++)
{
dir[i] = -1;
p[i] = i;
pi[i] = i;
}
perm(0, p, pi, dir);
Console.Write(" (0 1)\n");
}
public void perm(int n, int[] p, int[] pi, int[] dir)
{
if (n >= p.Length)
{
for (int i = 0; i < p.Length; i++)
Console.Write(p[i]);
return;
}
perm(n + 1, p, pi, dir);
for (int i = 0; i <= n - 1; i++)
{
// swap
Console.Write(" {0} {1}\n", pi[n], pi[n] + dir[n]);
int z = p[pi[n] + dir[n]];
p[pi[n]] = z;
p[pi[n] + dir[n]] = n;
pi[z] = pi[n];
pi[n] = pi[n] + dir[n];
perm(n + 1, p, pi, dir);
}
dir[n] = -dir[n];
}
class Program
{
static void Main(string[] args)
{
JT a = new JT();
Console.Write("Enter value:");
int x = Convert.ToInt32(Console.ReadLine());
a.perm(x);
}
}
}
}
Lexicographic algorithm ()
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace algo
{
public class PermutationsLex
{
public void show(int[] a)
{
for (int i = 0; i < a.Length; i++)
Console.Write("{0}", a[i]);
Console.WriteLine("\n");
}
public void swap(int[] a, int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public bool hasNext(int[] a)
{
int N = a.Length;
// find rightmost element a[k] that is smaller than element to its right
int k;
for (k = N - 2; k >= 0; k--)
if (a[k] < a[k + 1]) break;
if (k == -1) return false;
// find rightmost element a[j] that is larger than a[k]
int j = N - 1;
while (a[k] > a[j])
j--;
swap(a, j, k);
for (int r = N - 1, s = k + 1; r > s; r--, s++)
swap(a, r, s);
return true;
}
public void perm(int N)
{
// initialize permutation
int[] a = new int[N];
for (int i = 0; i < N; i++)
a[i] = i;
// print permutations
show(a);
while (hasNext(a))
show(a);
}
class Program
{
static void Main(string[] args)
{
PermutationsLex a = new PermutationsLex();
Console.Write("Enter value:");
int x = Convert.ToInt32(Console.ReadLine());
a.perm(x);
}
}
}
}
For the Gauss-Jordan program (using new algo(3)), If you enter the matrix:
ReplyDelete1 2 3 0
4 5 6 0
7 8 9 0
The program breaks because it divides by zero. Is there anyway to solve this? The solution should be:
1 0 -1 0
0 1 2 0
0 0 0 0
made it long time ago.. it will take time to understand it again..
Deletebut if program is breaking some where because of zero put some exception handling.. algo can not solve your data untill it is valid.