C#基础算法实例

class MainClass{public static void Main(string[] args){#region 选择题// 1 B// 2 D// 3 C// 4 BCD// 5 CD// 6 A// 7 B// 8 ABD// 9 B// 10 B#endregion#region 第1题调用//int[] nums = { 5, 7, 6, 9, 8 };//string[] numss = { \"abd\", \"abc\", \"bcd\", \"cbd\", \"bdc\", \"ab\", \"b\" };//SortArray(nums);//SortArray(nums, (a, b) =>//{//    for (int i = 0; i < a.Length && i < b.Length; i++)//    {//        if (a[i] != b[i])//        {//            return a[i] - b[i];//        }//    }//    return a.Length - b.Length;//});//foreach (var item in nums)//{//    Console.WriteLine(item);//}#endregion#region 第2题调用int[] numss1 = { 5, 7, 6, 9, 8 };int max, min;if (GetMaXMin(numss1, out max, out min)){Console.WriteLine(\"Max : \" + max + \", Min : \" + min);}#endregion#region 第3题调用int[] nums1 = { 2, 1, 3, 5, 8, 10, 7, 2, 7, 4, 3, 1, 5 };Sort(nums1);foreach (var item in nums1){Console.WriteLine(item);}#endregion#region 第4题调用Console.WriteLine(Monkey(1));#endregion#region 第5题调用foreach (var item in GetPrimeNumber(0, 200)){Console.WriteLine(item);}#endregion#region 第6题调用Shape[] shapes = { new Rectangle(5, 10), new Circle(5) };foreach (var item in shapes){Console.WriteLine(item.GetArea());Console.WriteLine(item.GetLength());}#endregion#region 第7题调用int checkin, rabbit;if (GetNum(5, 14, out checkin, out rabbit)){Console.WriteLine(\"鸡 ：\" + checkin + \", 兔 ： \" + rabbit);}#endregion#region 第8题调用BuyChecken(100, true);#endregion#region 第9题调用MyFunction(12);Console.WriteLine(fib(12));#endregion}#region 1.    写一个方法可以实现对一个数组实现升序排序： 使用冒泡排序实现数组内的排序static void SortArray<T>(T[] array){for (int i = 0; i < array.Length; i++){for (int j = 0; j < array.Length - 1 - i; j++){IComparable<T> comparable = array[j] as IComparable<T>;if (comparable != null){if (comparable.CompareTo(array[j + 1]) > 0){T tmp = array[j];array[j] = array[j + 1];array[j + 1] = tmp;}}}}}static void SortArray<T>(T[] array, Comparison<T> comparison){for (int i = 0; i < array.Length; i++){for (int j = 0; j < array.Length - 1 - i; j++){if (comparison(array[j], array[j + 1]) > 0){T tmp = array[j];array[j] = array[j + 1];array[j + 1] = tmp;}}}}#endregion#region 2.  写一个方法试着用最少的比较次数去寻找数组中的最大值和最小值static bool GetMaXMin(int[] array, out int max, out int min){if (array == null || array.Length == 0){max = min = 0;return false;};// 把数组两两分组 小的放左边 大的方右边        比较次数 n/2 次// 最小值在左边找                          比较次数 n/2 次// 最大值在右边找                          比较次数 n/2 次// 总的比较次数                                  3n/2 次// 优化：不做交换 直接和每组比 每组比较的次数 3次max = min = array[0];// 长度为偶数if (array.Length % 2 == 0){for (int i = 0; i < array.Length; i += 2){if (array[i] > array[i + 1]){if (array[i] > max) max = array[i];if (array[i + 1] < min) min = array[i + 1];}else{if (array[i + 1] > max) max = array[i + 1];if (array[i] < min) min = array[i];}}}else  // 长度为奇数{for (int i = 0; i < array.Length - 1; i += 2){if (array[i] > array[i + 1]){if (array[i] > max) max = array[i];if (array[i + 1] < min) min = array[i + 1];}else{if (array[i + 1] > max) max = array[i + 1];if (array[i] < min) min = array[i];}}if (max < array[array.Length - 1]) max = array[array.Length - 1];if (min > array[array.Length - 1]) min = array[array.Length - 1];}return true;}#endregion#region 3.  写一个方法实现输入一个数组，实现一个函数，让所有奇数都在偶数前面static void Sort(int[] array){// 两个指针// 左边的找到第一个偶数// 右边的找到第一个奇数// 如果两个指针满足  左边的 < 右边的 就交换这两个数int left = 0;int right = array.Length - 1;while (left < right){// 找左边的偶数while (left < right){if (array[left] % 2 != 0){left++;}else break;}// 找右边的奇数while (left < right){if (array[right] % 2 == 0){right--;}else break;}if (left < right){int tmp = array[left];array[left] = array[right];array[right] = tmp;}}}#endregion#region 4.  猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾就多吃了一个。第二天早上又将剩下的桃子吃了一半，还是不过瘾又多吃了一个。以后每天都吃前一天剩下的一半再加一个。到第10天刚好剩一个。问猴子第一天摘了多少个桃子？//          7        2*7 + 1        15//          8        2*3 + 1        7//          9        2*1 + 1        3//          10       1              1static int Monkey(int day){if (day > 10) return 0;else if (day == 10) return 1;else return 2 * (Monkey(day + 1) + 1);}#endregion#region 5.  写一个方法可以求N到M之间的质数 N>0 M<200;static List<int> GetPrimeNumber(int left, int right)  // (]{List<int> primeNumber = new List<int>();int start = left < right ? left : right;start = start >= 2 ? start : 2;int end = left < right ? right : left;end = end >= 2 ? end : 2;for (int i = start; i < end; i++){// 判断每一个数字 i 是否是质数bool isPrimeNumber = true;// 除了1和自己 能被其他数字整除就不是质数for (int j = 2; j < i; j++){if (i % j == 0)  // 能被其中一个数字整除了 就不是质数了{isPrimeNumber = false;break;}}if (isPrimeNumber){primeNumber.Add(i);}}return primeNumber;}#endregion#region 6.  多态实现求面积和周长（矩形和圆形）abstract class Shape{public abstract int GetArea();public abstract int GetLength();}class Rectangle : Shape{int width;int height;public Rectangle(int width, int height){this.width = width;this.height = height;}public override int GetArea(){return this.width * this.height;}public override int GetLength(){return (width + height) * 2;}}class Circle : Shape{int radius;public Circle(int radius){this.radius = radius;}public override int GetArea(){return (int)(radius * radius * Math.PI);}public override int GetLength(){return (int)(Math.PI * 2 * radius);}}#endregion#region 7.  有若干只鸡兔同在一个笼子里，从上面数，有N个头，从下面数，有M只脚。问笼中各有多少只鸡和兔？static bool GetNum(int head, int foot, out int checkin, out int rabbit){if (foot % 2 != 0 || foot < 2 * head){checkin = rabbit = 0;return false;}// 二元一次方程  假设x只鸡， y只兔子//foot = x * 2 + y * 4;//head = x + y;              => x = head - y// => foot = (head - y) * 2 + y * 4// => foot = head * 2 - 2 * y + y * 4// => y = (foot - head * 2)/2rabbit = (foot - head * 2) / 2;checkin = head - rabbit;return true;}#endregion#region 8.  小明带有一百文钱，去市场买鸡，公鸡5文钱，母鸡3文钱，小鸡1文钱3只; 问:小明要如何配比才能买一百只，他一共有几种方案// 100文钱                                 只//         公鸡     5         1            x        5x//         母鸡     3         1            y        3y//         小鸡     1         3            z        z/3// x  + y  + z    = 100// 5x + 3y + z/3 <= 100static void BuyChecken(int totalMoney, bool allin = false){int num;   // 买鸡的数量int cost;  // 花费// 买小鸡for (int i = 0; i <= totalMoney * 3; i += 3)          // 小鸡的个数{// 买公鸡for (int j = 0; j <= totalMoney / 5; j++){// 买母鸡for (int k = 0; k <= totalMoney / 3; k++){num = i + j + k;cost = i / 3 + 5 * j + 3 * k;if (allin){if (num == 100 && cost == 100){Console.WriteLine($\"小鸡:{i}只, 公鸡{j}只, 母鸡:{k}只\");}}else{if (num == 100 && cost <= 100){Console.WriteLine($\"小鸡:{i}只, 公鸡{j}只, 母鸡:{k}只\");}}}}}}#endregion#region 9.  有一对兔子每一个月可以生一对小兔子，小兔子出生后第三个月又开始生小兔子，问一年后（十二个月），有多少只兔子。/// <summary>/// 非递归方法/// </summary>/// <param name=\"months\"></param>public static void MyFunction(int months){int lastLastGiveBirth = 0;    //上上个月可生育的兔子数量int lastGiveBirth = 0;        //上个月可生育的兔子数量int count = 1;              //总数量  初始化为一对兔子for (int month = 1; month <= months; month++){int giveBirth = lastGiveBirth + lastLastGiveBirth;if (month == 3){giveBirth = 1;}lastLastGiveBirth = lastGiveBirth;lastGiveBirth = giveBirth;count = count + giveBirth;Console.WriteLine(\"第\" + month + \"个月的兔子对数：\" + count);}}//递归方法实现(我认为好的方法)public static int fib(int month){if (month == 1 || month == 2){return 1;}else{return fib(month - 1) + fib(month - 2);}}#endregion}