Algoritma görselleştirme üzerine yapılmış çok güzel bir çalışmayı aşağıdaki linkte bulabilirsiniz. Birçok algoritmayı kapsıyor, nerdeyse birkaç dönemlik ders literatürünü bir pojede toplamışlar.
http://www.cs.usfca.edu/~galles/visualization/download.html
Horspool’s stringMatch algoritmasını c# ile implemente etmeye çalıştım. Algoritma basit anlamda indexof gibi çalışıyor. Indexof kullanmak daha performanslı sonuç verebilir. Bildiğiniz üzere Boyer Moore’un ilkel hali diyebiliriz algoritma için.
Kaynak için wiki
private static Hashtable ShiftTable;
static void Main(string[] args)
{
Console.WriteLine("{0}. index'te bulundu",HorspoolMatching("lah", "abdullah"));
Console.ReadLine();
}
private static int HorspoolMatching(string pattern, string text)
{
ShiftMyTable(pattern, text);
int i = pattern.Length - 1;
while (i < = text.Length - 1)
{
int k = 0;
while (k <= pattern.Length - 1 && pattern[pattern.Length - 1 - k] == text[i - k])
{
k++;
}
if (k == pattern.Length)
return i - pattern.Length + 1;
else
i=i+Convert.ToInt32(ShiftTable[text[i]].ToString());
}
return -1;
}
private static void ShiftMyTable(string pattern, string text)
{
ShiftTable = new Hashtable();
for (int i = 0; i < text.Length; i++)
{
if (!ShiftTable.ContainsKey(text[i]))
{
if (!pattern.Contains(text[i].ToString()))
ShiftTable.Add(text[i], pattern.Length);
else
{
for(int j=pattern.Length-1;j>=0;j--)
{
if (pattern[j] == text[i])
{
ShiftTable.Add(text[i], pattern.Length - j-1);
break;
}
}
}
}
}
}
Noktalar dizisi içinde en yakın iki noktayı bulmak için kullanılabilecek yöntemlerden birisi brute force’dur. Brute force olarak bir noktayı alıp tüm diğer noktalar ile karşılaştırıp en yakın noktaların hangi ikisi olduğuna karar vermeye çalışırsınız. İlgili kodu aşağıda paylaşıyorum, birde grafik arayüzü ile uzayda boşlukta duran noktalar arasındaki mesafenin nasıl hesaplanabileceğini geometrik olarak göstermeye çalıştım. Görselin ve noktaların tabi 2D uzayda var olduğunu düşünerek algoritmayı yazdım. x,y ve birde z ekseni işin içine girmiş olsaydı çözüm çok daha farklı olurdu tabiki.
private static void ClosestPair()
{
double d = 10000000, dmin = 1000000; // min bulmak için sorun olmaması açısından büyük rakamlar atadım
int x = 0, y = 0; //(xi-xj)^2 ve (yi-yj)^2 değerlerini tutmak için değişkenler.
int index1 = 0, index2 = 0;
// input değerleri ayarlanıyor
int[,] p = new int[5, 5];
p[0, 0] = 1;
p[0, 1] = 1;
p[1, 0] = 3;
p[1, 1] = 3;
p[2, 0] = 3;
p[2, 1] = 3;
p[3, 0] = 4;
p[3, 1] = 4;
p[4, 0] = 5;
p[4, 1] = 5;
//input değerleri bitiş
for (int i = 0; i < 5; i++)
for (int j = i + 1; j < 5; j++)
{
x = (p[i, 0] - p[j, 0]) * (p[i, 0] - p[j, 0]);
y = (p[i, 1] - p[j, 1]) * (p[i, 1] - p[j, 1]);
d = Math.Sqrt(x + y);
if (d < dmin)
{
dmin = d;
index1 = i;
index2 = j;
}
}
Console.WriteLine("index1 {0}, index2 {1}", index1, index2);
Console.ReadLine();
}
Bir önceki yazımda bahsettiğim kodun daha performanslı hale getirilmiş olanı;
private static void PolynomialEvaluation()
{
int p = 0;
Console.WriteLine("sayıyı giriniz:");
string sayi = Console.ReadLine();
Console.WriteLine("tabanı giriniz");
int taban = Convert.ToInt32(Console.ReadLine());
int power = 1;
for (int i = sayi.Length - 1; i >= 0; i--)
{
int x = Convert.ToInt32(sayi[i].ToString());
p += x * power;
power = power * taban;
}
Console.WriteLine("{0} sayısının 10 luk tabanda karşılığı {1}'dir.", sayi, p);
Console.ReadLine();
}
Taban dönüşüm işleminin polinom çözümünün implementasyonu için aşağıdaki kodu kullanabilirsiniz , kod kısaca belirtilen tabandaki sayıyı 10′luk tabana polinom çözümü ile dönüştürüyor. Kodu çok kontrollü yazmadım, input’lara dikkat etmek gerek. Bir sonraki yazımda kodun iyileştirilmiş olanını paylaşacağım.
Polinom çözüm= An*x^n + An-1*x^n-1+ … +A1*x^1+A0
private static void BruteForcePolynomialEvaluation()
{
int p = 0;
Console.WriteLine("sayıyı giriniz:");
string sayi = Console.ReadLine();
Console.WriteLine("tabanı giriniz");
int taban = Convert.ToInt32(Console.ReadLine());
int counter = 0;
for (int i = sayi.Length - 1; i >= 0; i--)
{
int power = 1;
for (int j = 0; j < i; j++)
{
power = power * taban;
}
int x = Convert.ToInt32(sayi[counter].ToString());
p += x * power;
counter++;
}
Console.WriteLine("{0} sayısının 10 luk tabanda karşılığı {1}'dir.", sayi, p);
Console.ReadLine();
}
Büyük integer’ların çarpımını formülü biraz ilerleterek hızlandırmak mümkün, bir önceki formülde major multiplication sayımız 4 iken burda 3′e düşüreceğiz;
A=2150 olsun, A1=21*10^2 ,A2=50
B=7890 olsun , B1=78*10^2, B2=90 Olur.
Olayı formüle edecek olursak;
A*B=A1*B1*10^n+((A1+A2)*(B1+B2)-A1*B1-A2*B2)*10^n/2 +A2*B2
Kod örneği aşağıdaki gibidir;
//divide and conquer
private static void FastLargeIntegerMultiplaction()
{
string Num1 = "2135", Num2 = "4014";
int n = Num1.Length;
int Num1L = Convert.ToInt32(Num1.Substring(0, (n / 2)));
int Num1H = Convert.ToInt32(Num1.Substring((n / 2), n / 2));
int Num2L = Convert.ToInt32(Num2.Substring(0, (n / 2)));
int Num2H = Convert.ToInt32(Num2.Substring((n / 2), n / 2));
string Nzero = "", N2zero = "";
for (int i = 0; i < n; i++)
{
Nzero += "0";
if (i + 1 <= n / 2)
N2zero += "0";
}
int Multp1, Multp2;
Multp1 = Num1L * Num2L;
Multp2 = Num1H * Num2H;
Console.WriteLine(Convert.ToInt32(Multp1.ToString() + Nzero) + Convert.ToInt32(((Num1L+Num1H)*(Num2L+Num2H)-Multp1-Multp2).ToString() + N2zero) + Multp2);
Console.ReadLine();
}
Bazen büyük sayıların çarpımında dilin bize tanıdığı değer aralığını aşarız. Bu tür durumlarda iki sayının çarpımını çokta basit olmayarak formüle etmek mümkün.
A=2150 olsun, A1=21*10^2 ,A2=50
B=7890 olsun , B1=78*10^2, B2=90 Olur.
Olayı formüle edecek olursak;
A*B=A1*B1*10^n+(A1*B2+A2*B1)*10^n/2 +A2*B2
Kod örneği aşağıdaki gibidir;
//divide and conquer
private static void LargeIntegerMultiplaction()
{
string Num1 = "2135", Num2 = "4014";
int n = Num1.Length;
int Num1L = Convert.ToInt32(Num1.Substring(0, (n / 2)));
int Num1H = Convert.ToInt32(Num1.Substring((n / 2), n / 2));
int Num2L = Convert.ToInt32(Num2.Substring(0, (n / 2)));
int Num2H = Convert.ToInt32(Num2.Substring((n / 2), n / 2));
string Nzero = "", N2zero = "";
for (int i = 0; i < n; i++)
{
Nzero += "0";
if (i + 1 <= n / 2)
N2zero += "0";
}
int Multp1, Multp2, Multp3, Multp4;
Multp1 = Num1L * Num2L;
Multp2 = Num1H * Num2H;
Multp3 = Num1L * Num2H;
Multp4 = Num1H * Num2L;
Console.WriteLine(Convert.ToInt32(Multp1.ToString() + Nzero) + Convert.ToInt32((Multp3 + Multp4).ToString() + N2zero) + Multp2);
Console.ReadLine();
}
Brute force string eşleştirme algoritması ile bir string dizisi içinde ondan daha küçük ya da eşit olan birbaşka dizinin geçip geçmediği kontrol edilebilir. Aşağıda ilgili kodu paylaşıyorum;
static void Main(string[] args)
{
System.Console.WriteLine(BruteForceStringmatch("abdullah kuzhan", "kuzhan"));
Console.ReadLine();
}
private static bool BruteForceStringmatch(string Source, string LookingFor)
{
for (int i = 0; i < = Source.Length - LookingFor.Length; i++)
{
int j = 0;
while (j < LookingFor.Length)
{
if (LookingFor[j] == Source[i + j])
j++;
else
break;
}
if (j == LookingFor.Length)
return true;
}
return false;
}
Sıralı diziler içinde arama yapmak için oldukça etkili bir yöntem olan Binary search kullanılabilir. Aşağıdaki kod aynı zamanda bir divide and conquer örneği teşkil ediyor.
static void Main(string[] args)
{
int iterationCount = 0;
int[] MyList = new int[100];
for (int i = 1; i < 100; i++)
MyList[i - 1] = i;
Console.WriteLine(BinarySearch(MyList, 50, ref iterationCount));
Console.WriteLine("iterasyon sayısı:{0}", iterationCount);
System.Console.ReadLine();
}
private static bool BinarySearch(int[] MyList, int LookingFor, ref int iterationCount)
{
int l = 0, r=MyList.Length-1,m=0;
while(l<=r)
{
iterationCount++;
m = (l + r) / 2;
if (LookingFor == MyList[m])
return true;
else if (LookingFor < MyList[m])
r = m - 1;
else
l = m + 1;
}
return false;
}
C# ile 100 elemanlık bir dizinin selection sort ile sıralanması algoritmasını aşağıda bulabilirsiniz;
static void Main(string[] args)
{
int[] MyList = new int[100];
Random r = new Random();
for (int i = 0; i < 100; i++)
MyList[i] = r.Next(150);
selectionSort(MyList);
foreach (int a in MyList)
System.Console.WriteLine(a);
System.Console.ReadLine();
}
static void selectionSort(int[] a)
{
for(int j=0; j < a.Length;j++)
{
int minElementIndex =j;
int minElementValue = j;
for(int i=j+1; i
follow: RSS