C#.NET 算法题 初级篇
冒泡排序
冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
查看代码
c#
public static void BubbleSort(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
for (int j = 0; j < arr.Length - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
// 常规交换值
// int temp = arr[j];
// arr[j] = arr[j + 1];
// arr[j + 1] = temp;
// 使用元组交换值
(arr[j + 1], arr[j]) = (arr[j], arr[j + 1]);
}
}
}
}斐波拉契数列
斐波那契数列（Fibonacci sequence） 又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。
查看代码
c#
//斐波那契数列算法1：递归
public static int Fibonacci1(int n)
{
if (n <= 0)
return 0;
if (n == 1 || n == 2)
return 1;
return Fibonacci1(n - 1) + Fibonacci1(n - 2);
}
//斐波那契数列算法2：循环
public static int Fibonacci2(int n)
{
if (n <= 0)
return 0;
if (n == 1 || n == 2)
return 1;
int a = 1, b = 1, c = 0;
for (int i = 3; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
//斐波那契数列算法3：矩阵
public static int Fibonacci3(int n)
{
if (n <= 0)
return 0;
if (n == 1 || n == 2)
return 1;
int[,] matrix = { { 1, 1 }, { 1, 0 } };
int[,] result = MatrixPower(matrix, n - 2);
return result[0, 0] + result[0, 1];
}
private static int[,] MatrixPower(int[,] matrix, int n)
{
int[,] result = { { 1, 0 }, { 0, 1 } };
while (n > 0)
{
if ((n & 1) == 1)
result = MatrixMultiply(result, matrix);
matrix = MatrixMultiply(matrix, matrix);
n >>= 1;
}
return result;
}
private static int[,] MatrixMultiply(int[,] matrix1, int[,] matrix2)
{
int[,] result = new int[2, 2];
result[0, 0] = matrix1[0, 0] * matrix2[0, 0] + matrix1[0, 1] * matrix2[1, 0];
result[0, 1] = matrix1[0, 0] * matrix2[0, 1] + matrix1[0, 1] * matrix2[1, 1];
result[1, 0] = matrix1[1, 0] * matrix2[0, 0] + matrix1[1, 1] * matrix2[1, 0];
result[1, 1] = matrix1[1, 0] * matrix2[0, 1] + matrix1[1, 1] * matrix2[1, 1];
return result;
}
//斐波那契数列算法4：通项公式
public static int Fibonacci4(int n)
{
if (n <= 0)
return 0;
double sqrt5 = Math.Sqrt(5);
double fibn = Math.Pow((1 + sqrt5) / 2, n) - Math.Pow((1 - sqrt5) / 2, n);
return (int)Math.Round(fibn / sqrt5);
}水仙花数
所谓“水仙花数”是指一个三位的整数，其各位数字立方和等于该数本身。
查看代码
c#
public static void NarcissisticNumber()
{
for (int i = 100; i < 1000; i++)
{
int a = i / 100;
int b = i / 10 % 10;
int c = i % 10;
if (a * a * a + b * b * b + c * c * c == i)
{
Console.WriteLine(i);
}
}
}两数之和
不用算术运算符完成两个数求和
查看代码
c#
/// <summary>
/// 思路：不使用算术运算求和那么只能考虑直接在二进制位上进行位运算，
/// 事实上利用异或运算（^）和与运算（&）就能完成加法运算要做的事情，
/// 其中异或运算完成相加但是不进位，而与运算计算出哪些地方需要进位，
/// 再通过左移运算就可以完成进位操作了。
/// </summary>
/// <param name="a">整形A</param>
/// <param name="b">整形B</param>
/// <returns>A+B</returns>
public static int SumAB(int a,int b)
{
if (b == 0) return a;
int c = a ^ b;
int d = (a & b) << 1;
return SumAB(c, d);
}红包算法
经典的红包分配算法
查看代码
c#
/// <summary>
/// 红包算法
/// </summary>
/// <param name="remainMoney">要分配的总额度</param>
/// <param name="remainCount">要分配的份数</param>
/// <returns></returns>
public static List<double> GetMoneys(double remainMoney, int remainCount)
{
//人均最小金额
double min = 0.01;
if (remainMoney < remainCount * min)
return null;
int num = remainCount;
List<double> array = new List<double>();
Random r = new Random();
for (int i = 0; i < num; i++)
{
if (remainCount == 1)
{
remainCount--;
array.Add(Convert.ToDouble(remainMoney.ToString("0.00")));
// Console.WriteLine(string.Format("第{0}个红包：{1}元", i + 1, Convert.ToDouble(remainMoney.ToString("0.00"))));
}
else
{
//(remainMoney - (remainCount - 1) * min)：保存剩余金额可以足够的去分配剩余的红包数量
double max = (remainMoney - (remainCount - 1) * min) / remainCount * 2;
double money = r.NextDouble() * max;
money = Convert.ToDouble((money <= min ? min : money).ToString("0.00"));
remainCount--;
remainMoney -= money;
array.Add(money);
// Console.WriteLine(string.Format("第{0}个红包：{1}元", i + 1, money));
}
}
//再次随机
return array.OrderBy(o => Guid.NewGuid()).ToList();
}
