几种常用算法

常用的算法（经典以及排序）

1二分查找

* 二分法查找
* 查找线性表必须是有序列表
*
* @param e
* @param key
* @return
*/
public int binarySearch(int[] e, int key) {
int low = 0, high = e.length - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (key == e[mid]) {
return mid;
} else if (key < e[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}



发表于 2009-10-24 10:25
一猫抓老鼠


猫和老鼠在10*10的方格中运动，例如：
*...*.....
......*...
...*...*..
..........
...*.C....
*.....*...
...*......
..M......*
...*.*....
.*.*......
C=猫（CAT）
M=老鼠（MOUSE）
*=障碍物
.=空地
猫和老鼠每秒中走一格，如果在某一秒末他们在同一格中，我们称他们“相遇”。
注意，“对穿”是不算相遇的。猫和老鼠的移动方式相同：平时沿直线走，下一步如果会走到障碍物上去或者出界，
就用1秒的时间做一个右转90度。一开始他们都面向北方。
编程计算多少秒以后他们相遇。

Input
第一行为一整数N，表示有N组测试数据。
每组测试数据为10行，格式如题目描述。

Output
相遇时间T。如果无解，输出-1。

Sample Input
1
*...*.....
......*...
...*...*..
..........
...*.C....
*.....*...
...*......
..M......*
...*.*....
.*.*......

Sample Output
49


解法如下：
类似迷宫算法问题

using System;
class MainClass
{
public struct Pos //position
{
public int x;
public int y;
}
public struct direction
{
public int x;
public int y;
}
private static int CatAndMice(string[] path)
{
int width = path[0].Length + 2;
int height = path.Length + 2;
int time = 0;
string[] fulPath = new string[height];
Pos micePos = new Pos(); //current position
Pos catPos = new Pos();
Pos miceInitPos=new Pos(); //first postion
Pos catInitPos=new Pos();
direction[] dir = new direction[4]; //4 direction
dir[0].x = -1; //up
dir[0

].y = 0;
dir[1].x = 0; //right
dir[1].y = 1;
dir[2].x = 1; //down
dir[2].y = 0;
dir[3].x = 0; //left
dir[3].y = -1;
for (int i = 0; i < height; ++i) //add '*' around the path matrix
{
string curLine = String.Empty;
if (i == 0 || i == height - 1)
{
while (curLine.Length < width)
{
curLine += "*";
}
}
else
{
curLine = "*" + path[i - 1] + "*";
}
fulPath = curLine;
if (fulPath.IndexOf("C") > 0)
{
catPos.y = fulPath.IndexOf("C");
catPos.x = i;
}
if (fulPath.IndexOf("M") > 0)
{
micePos.y = fulPath.IndexOf("M");
micePos.x = i;
}
}
miceInitPos.x=micePos.x;
miceInitPos.y=micePos.y;
catInitPos.x=catPos.x;
catInitPos.y=catPos.y;
int initCatDir = 0; //start direction of cat: 0 for up
int initMiceDir = 0;
while (true)
{
if (fulPath[catPos.x + dir[initCatDir].x][catPos.y + dir[initCatDir].y] == '*')
{
initCatDir++; //turn right
if (initCatDir == 4)
{
initCatDir = 0;
}
}
else
{
catPos.x += dir[initCatDir].x; //move to next point
catPos.y += dir[initCatDir].y;
}
if (fulPath[micePos.x + dir[initMiceDir].x][micePos.y + dir[initMiceDir].y] == '*')
{
initMiceDir++;

if (initMiceDir == 4)
{
initMiceDir = 0;
}
}
else
{
micePos.x += dir[initMiceDir].x;
micePos.y += dir[initMiceDir].y;
}
time++;
if (micePos.x == catPos.x && micePos.y == catPos.y)
{
return time;
}
if (time > 0 && initCatDir == initMiceDir && catInitPos.x == catPos.x && catInitPos.y == catPos.y && miceInitPos.x == micePos.x && miceInitPos.y == micePos.y)
{
return -1;
}
}
}
public static void Main()
{
string[] path = new string[]{
"*...*.....",
"......*...",
"...*...*..",
"..........",
"...*.C....",
"*.....*...",
"...*......",
"..M......*",
"...*.*....",
".*.*......"};
Console.WriteLine(CatAndMice(path));
Console.ReadLine();
}
}



发表于 2009-10-24 10:25
二:八皇后问题

八个皇后在排列时不能同在一行、一列或一条斜线上。

在8!=40320种排列中共有92种解决方案


using System;
using System.Collections.Generic;
using System.Text;

namespace ExQueen
{
class Queen
{
public void QueenArithmetic(int size)
{
int[] Queen = new int[size];//每行皇后的位置
int y, x, i, j, d, t = 0;
y = 0;
Queen[0] = -1;
while (true)
{
for (x = Queen[y] + 1; x < size; x++)
{
for (i = 0; i < y; i++)
{
j = Queen;
d = y - i;
//检查新皇后是否能与以前的皇后相互攻击
if ((j == x) || (j == x - d) || (j == x + d))
break;
}
if (i >= y)
break;//不攻击
}
if (x == size) //没有合适的位置
{
if (0 == y)
{
//回朔到了第一行
Console.WriteLine("Over");
break; //结束
}
//回朔

Queen[y] = -1;
y--;
}
else
{
Queen[y] = x;//确定皇后的位置
y++;//下一个皇后
if (y < size)
Queen[y] = -1;
else
{
//所有的皇后都排完了，输出
Console.WriteLine("\n" + ++t + ':');
for (i = 0; i < size; i++)
{
for (j = 0; j < size; j++)
Console.Write(Queen == j ? 'Q' : '*');
Console.WriteLine();
}
y = size - 1;//回朔
}
}
}
}
public static void Main()
{
int size = 8;//皇后数
Queen q = new Queen();
q.QueenArithmetic(size);
}
}
}


发表于 2009-10-24 10:25
三:打靶问题



一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？



用C#编写的完整代码如下：

using System ;



public class M

{
//public static int[] store;

//相当于设置了全局变量

//这个全局变量sum是包含在M类中的

public static int sum;

public M()

{
int sum =0;

// int[] store = {1,2,3,4,5,6,7,8,9,0};
}



//打印函数

//符合要求的则把它打印出来

public static void Output(int[] store2)

{
for(int i = 9; i>=0; --i)

{
Console.Write(" {0}",store2);
}

Console.WriteLine();
sum++;
}

//计算总数，返回sum值

public static int sum2()
{
return sum;
}


public static void Cumput(int score, int num, int[] store2 )
{
//如果总的成绩超过了90环（也就是score<0），或者如果剩下要打靶

//的成绩大于10环乘以剩下要打的次数，也就是说即便后面的都打10环

//也无法打够次数，则退出递归

if(score < 0 || score > (num+1)*10 ) //次数num为0～9
{
return;
}

//如果满足条件且达到最后一层
if(num == 0)
{
store2[num] = score;
Output( store2);
return;
}



for(int i = 0; i <= 10; ++i)
{
store2[num] = i;
Cumput(score - i, num - 1,store2);
}
//Console.Write(" {0}",store2[5]);
}
}



public class myApp
{
public static void Main( )
{
int[] store;
store = new int[10];
int sum = 0;
//int a=90;
//int b=9;
//Output();
M.C

umput(90,9,store);
sum = M.sum2();
//M.Cumput2(a,b,store);
//Console.Write(" {0}",store[3]);
//cout<<"总数:"<Console.Write(" 总数: {0}",sum);
}
}


#5
使用道具
发表于 2009-10-24 10:25
四 选择排序

using System;
public class SelectionSorter
{
// public enum comp {COMP_LESS,COMP_EQUAL,COMP_GRTR};
private int min;
// private int m=0;
public void Sort(int[] list)
{
for (int i = 0; i < list.Length - 1; ++i)
{
min = i;
for (int j = i + 1; j < list.Length; ++j)
{
if (list[j] < list[min])
min = j;
}
int t = list[min];
list[min] = list;
list = t;
// Console.WriteLine("{0}",list);
}
}
}
public class MainClass
{
public static void Main()
{
int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
SelectionSorter ss = new SelectionSorter();
ss.Sort(iArrary);
for (int m = 0; m <= 13; m++)
Console.WriteLine("{0}", iArrary[m]);
Console.ReadKey();
}
}

}
}


#6
使用道具
发表于 2009-10-24 10:26
五插入排序



using System;
public class InsertionSorter
{
public void Sort(int[] list)
{
for (int i = 1; i < list.Length; ++i)
{
int t = list;
int j = i;
while ((j > 0) && (list[j - 1] > t))
{
list[j] = list[j - 1];
--j;
}
list[j] = t;
}

}
}
public class MainClass
{
public static void Main()
{
int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
InsertionSorter ii = new InsertionSorter();
ii.Sort(iArrary);
for (int m = 0; m <= 13; m++)
Console.WriteLine("{0}", iArrary[m]);
Console.ReadKey();
}
}



#7
使用道具
发表于 2009-10-24 10:26
六希尔排序

using System;
public class ShellSorter
{
public void Sort(int[] list)
{
int inc;
for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
for (; inc > 0; inc /= 3)
{
for (int i = inc + 1; i <= list.Length; i += inc)
{
int t = list[i - 1];
int j = i;
while ((j > inc) && (list[j - inc - 1] > t))
{
list[j - 1] = list[j - inc - 1];
j -= inc;
}
list[j - 1] = t;
}
}
}
}
public class MainClass
{
public static void Main()
{
int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
ShellSorter sh = new ShellSorter();
sh.Sort(iArr

ary);
for (int m = 0; m <= 13; m++)
Console.WriteLine("{0}", iArrary[m]);
Console.ReadKey();
}
}


#8
使用道具
发表于 2009-10-24 10:26
七矩阵变换解一元n次方程


using System;
using System.Collections.Generic;
using System.Text;

namespace Object
{
public class Matrix
{
public Matrix()
{ }

public Matrix(double[,] matrix)
{
this.matrix = matrix;
}
double[,] matrix = new double[1, 1];//定义数组
public double[,] GetMatrix//获取设置数组
{
get { return matrix; }
set { matrix = value; }
}
public void Account(double[,] matrix, double[] mb, int number)//消除前排主项
{
for (int i = 0; i < number; i++)
{
for (int j = i + 1; j < number; j++)
{
double temp;
if (matrix[j, i] != 0)
{
temp = matrix[i, i] / matrix[j, i];
for (int k = 0; k < number; k++)
{
matrix[j, k] = matrix[i, k] - matrix[j, k] * temp;//消元
}
mb[j] = mb - mb[j] * temp;
}

}
} Console.WriteLine(mb[2].ToString());
for (int i = 0; i < number; i++)
{
for (int j = 0; j < number; j++)
{
Console.Write(matrix[i, j].ToString() + " ");
}
Console.Write(mb.ToString());
Console.WriteLine();
}
Console.ReadLine();
}
public void ReAccont(double[,] matrix, double[] mb, int number)////消除后排主项
{
for (int i = number - 1; i >= 0; i--)
{

for (int j = i - 1; j >= 0; j--)
{
double temp;
if (matrix[j, i] != 0)
{
temp = matrix[i, i] / matrix[j, i];
for (int k = 0; k < number; k++)
{
matrix[j, k] = matrix[i, k] - matrix[j, k] * temp;//消元

}
mb[j] = mb - mb[j] * temp;
}
}
}
for (int i = 0; i < number; i++) //输出消元后的矩阵
{
for (int j = 0; j < number; j++)
{
Console.Write(matrix[i, j].ToString() + " ");
}
Console.Write(mb.ToString());
Console.WriteLine();
}
Console.ReadLine();
for (int i = 0; i < number; i++)
{
if (matrix[i, i] !

= 0)
{
mb = mb / matrix[i, i];
matrix[i, i] = 1;
}
else
{
mb = 0;
}
}
for (int i = 0; i < number; i++) //高斯-约当消去法
{
for (int j = 0; j < number; j++)
{
Console.Write(matrix[i, j].ToString() + " \t ");
}
Console.Write(mb.ToString());
Console.WriteLine();
}
Console.ReadLine();
for (int i = 0; i < number; i++) //输出最后结果
{
Console.WriteLine("x" + i.ToString() + "=" + mb.ToString());
}
Console.ReadLine();
}
}
class Program
{
static void Main(string[] args)
{
double[,] mat = new double[,] {
{ 2, 2, 3, 2, 3, 8, 4, 6, 9, 10 },
{ 4, 7, 7, 12, 55, 6, 9, 8, 4, 65 },
{ -2, 4, 5, 5, 4, 6, 8, 4, 6, 9 },
{ 0,0,5,3,4,-4,-8,9,6,7},
{1,5,6,8,9,7,4,6,5,2},
{5,8,6,7,11,45,6,25,5,4},
{5,9,8,9,77,8,16,19,20,16},
{8,9.2,65,6.3,5,6,8,4,6,7},
{4,5,8,12,20,65,46,35,10,1},
{0,0,0,0,0,4,5,6,8,9}
};
double[] ma = new double[] { 3, 1, -7, 4, 6, 8, 9, 5, 12, 4 };
Matrix m = new Matrix(mat);

m.Account(mat, ma, 10);
m.ReAccont(mat, ma, 10);

}
}
}