C# 分治算法
Angel 人气:0分治策略是:
对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
可使用分治法求解的一些经典问题
(1)二分搜索
(2)大整数乘法
(3)Strassen矩阵乘法
(4)棋盘覆盖
(5)合并排序
(6)快速排序
(7)线性时间选择
(8)最接近点对问题
(9)循环赛日程表
(10)汉诺塔
分治算法 - 最大子数组问题
股票问题:
(1)暴力求解
嵌套循环,遍历所有的子数组,找到最大的子数组,从13开始遍历,一直遍历到7,找到最大的子数组,再从-3开始遍历,找到最大子数组,最简单粗暴,耗费性能最高,最消耗时间。
/**************************************************** * 功能:使用暴力求解股票价格购买问题 *****************************************************/ using System.Collections; using System.Collections.Generic; using UnityEngine; public class Test : MonoBehaviour { void Start() { Suanfa(); } void Suanfa() { int[] priceArray = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97};//价格数组 int[] priceFluctuationArray = new int[priceArray.Length - 1];//价格波动的数组 for (int i = 1; i < priceArray.Length; i++)//给价格波动表赋值 { priceFluctuationArray[i-1] = priceArray[i] - priceArray[i - 1];//当天价格-上一天价格 } int total = priceFluctuationArray[0];//默认第一个元素是最大子数组的和 int startIndex = 0; int endIndex = 0; for (int i = 0; i < priceFluctuationArray.Length; i++) { //取得以i为子数组起点的所有子数组 for (int j = i; j < priceFluctuationArray.Length; j++)//以i开始以i结束 { //由i,j就确定了一个子数组 int totalTemp = 0;//临时最大子数组的和 for (int k = i; k < j+1; k++) { totalTemp += priceFluctuationArray[k];//当前子数组的和 } if (totalTemp>total)//判断当前子数组的和是否大于总和 { total = totalTemp;//最大子数组的和 startIndex = i;//最大子数组的开始索引 endIndex = j;//最大子数组的结束索引 } } } Debug.Log("startIndex:"+startIndex); Debug.Log("endIndex:"+endIndex); Debug.Log("购买日期是第"+startIndex+"天 出售日期是第"+(endIndex+1)+"天"); } }
(2)分治法
求low和high数组的最大子数组(区间)(和最大):
由low和high取得中间的mid索引,由最初的[low,high]区间得到[low,mid][mid+1,high]两个区间,
i为子数组的开始索引,j为子数组的结束索引:
- i j 同时位于低区间
- i j 同时位于高区间
- i 位于低区间,j位于高区间
因为ij是由mid分隔的,分别取得在low mid里面的i值,mid high里面的j值
/**************************************************** * 功能:使用分治法求解股票价格购买问题 *****************************************************/ using System.Collections; using System.Collections.Generic; using UnityEngine; public class Test : MonoBehaviour { struct SubArray//最大子数组的结构体 { public int startIndex; public int endIndex; public int total; } void Start() { Suanfa(); } void Suanfa() { int[] priceArray = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97};//价格数组 int[] priceFluctuationArray = new int[priceArray.Length - 1];//价格波动的数组 for (int i = 1; i < priceArray.Length; i++)//给价格波动表赋值 { priceFluctuationArray[i-1] = priceArray[i] - priceArray[i - 1];//当天价格-上一天价格 } SubArray subArray = GetMaxSubArray(0, priceFluctuationArray.Length - 1, priceFluctuationArray); Debug.Log("startIndex:"+subArray.startIndex); Debug.Log("endIndex:"+subArray.endIndex); Debug.Log("购买日期是第"+ subArray.startIndex+"天 出售日期是第" +(subArray.endIndex + 1)+"天"); } static SubArray GetMaxSubArray(int low, int high, int[] array)//用来取得array这个数组从low到high之间的最大子数组 { if (low==high)//递归结束的终止条件 { SubArray subArray; subArray.startIndex = low; subArray.endIndex = high; subArray.total = array[low]; return subArray; } int mid = (low + high) / 2;//低区间[low,mid]高区间[mid+1,high] SubArray subArray1=GetMaxSubArray(low, mid, array);//低区间最大子数组 SubArray subArray2=GetMaxSubArray(mid + 1, high, array);//高区间最大子数组 //从[low,mid]找到最大子数组[i,mid] int total1 = array[mid];//最大子数组的和 int startIndex = mid;//最大子数组的开始索引 int totalTemp = 0;//临时的和 for (int i = mid; i >=low; i--)//从mid向low遍历 { totalTemp += array[i]; if (totalTemp>total1) { total1 = totalTemp; startIndex = i; } } //从[mid+1,high]找到最大子数组[mid+1,j] int total2 = array[mid+1];//最大子数组的和 int endIndex = mid+1;//最大子数组的结束索引 totalTemp = 0; for (int j = mid+1; j <= high; j++)//从mid+1向high遍历 { totalTemp += array[j]; if (totalTemp>total2) { total2 = totalTemp; endIndex = j; } } SubArray subArray3; subArray3.startIndex = startIndex; subArray3.endIndex = endIndex; subArray3.total = total1 + total2; if (subArray1.total>=subArray2.total&&subArray1.total>=subArray3.total) { return subArray1; } else if (subArray2.total >= subArray1.total && subArray2.total >= subArray3.total) { return subArray2; } else { return subArray3; } } }
分治法实现大数相乘 C#实现
用C#实现,尽可能的利用C#的特性。本例中,只要拆分的数字小于9位数,就可以直接相乘计算,保证不会溢出。
在编程中,还需要用的加法和减法,也要通过字符串模拟实现。
最终的乘法运算,依赖递归思想得以实现。
本文的代码还有一些可以优化的地方,比如对于不使用字符串而是全部使用数组,可能会更快点。
代码如下:
namespace bigIntMultiply { class Program { static void Main(string[] args) { string a = "99999999999999"; string b = "123456789001234567890"; Stopwatch sw = new Stopwatch(); sw.Start(); string s = Multiply(b, b); sw.Stop(); Console.WriteLine(s); Console.WriteLine(sw.Elapsed); } //字符串模拟乘法操作 static string Multiply(string x, string y) { //deep++;// Console.WriteLine("-" + deep + "-"); string negative = ""; if ((x.StartsWith("-") && y.StartsWith("-")) || (!x.StartsWith("-") && !y.StartsWith("-"))) { x = x.TrimStart('-'); y = y.TrimStart('-'); negative = ""; } else if ((x.StartsWith("-") && !y.StartsWith("-")) || (!x.StartsWith("-") && y.StartsWith("-"))) { x = x.TrimStart('-'); y = y.TrimStart('-'); negative = "-"; } //如果长度都小于9,直接相乘,返回就行了。 if (x.Length <= 9 && y.Length <= 9) { long tmp = (long.Parse(x) * long.Parse(y)); if (tmp == 0) return tmp.ToString(); return negative + (long.Parse(x) * long.Parse(y)).ToString(); } //公式里的abcd string a, b, c, d; if (x.Length <= 9) { a = "0"; b = x; } else { if (x.Length % 2 != 0) x = "0" + x; a = x.Substring(0, x.Length / 2); b = x.Substring(x.Length / 2); } if (y.Length <= 9) { c = "0"; d = y; } else { if (y.Length % 2 != 0) y = "0" + y; c = y.Substring(0, y.Length / 2); d = y.Substring(y.Length / 2); } int n = x.Length >= y.Length ? x.Length : y.Length; string t1, t2, t3; //递归调用,根据公式计算出值。 string ac = Multiply(a, c); string bd = Multiply(b, d); t1 = Multiply(Subtract(a, b), Subtract(d, c)); t2 = Add(Add(t1, ac), bd); t3 = Add(Add(Power10(ac, n), Power10(t2, n / 2)), bd).TrimStart('0'); if (t3 == "") return "0"; return negative + t3; } //字符串模拟加法操作 static string Add(string x, string y) { if (x.StartsWith("-") && !y.StartsWith("-")) { return Subtract(y, x.TrimStart('-')); } else if (!x.StartsWith("-") && y.StartsWith("-")) { return Subtract(x, y.TrimStart('-')); } else if (x.StartsWith("-") && y.StartsWith("-")) { return "-" + Add(x.TrimStart('-'), y.TrimStart('-')); } if (x.Length > y.Length) { y = y.PadLeft(x.Length, '0'); } else { x = x.PadLeft(y.Length, '0'); } int[] sum = new int[x.Length + 1]; for (int i = x.Length - 1; i >= 0; i--) { int tmpsum = int.Parse(x[i].ToString()) + int.Parse(y[i].ToString()) + sum[i + 1]; if (tmpsum >= 10) { sum[i + 1] = tmpsum - 10; sum[i] = 1;//表示进位 } else { sum[i + 1] = tmpsum; } } string returnvalue = string.Concat(sum); if (sum[0] == 1) { return returnvalue; } else { return returnvalue.Remove(0, 1); } } //字符串模拟减法操作 static string Subtract(string x, string y) { //if (x.StartsWith("-") && !y.StartsWith("-")) //{ // return "-" + Add(x.TrimStart('-'), y); //} //if (y.StartsWith("-")) //{ // return Add(x, y.TrimStart('-')); //} //x是正数,y也是正数 int flag = checkBigger(x, y); if (flag == 0) { return "0"; } else if (flag == -1) { string tmp = y; y = x; x = tmp; } //保证了x>=y y = y.PadLeft(x.Length, '0');//y补0与x对齐 int[] difference = new int[x.Length]; for (int i = x.Length - 1; i >= 0; i--) { int tmpdifference; tmpdifference = int.Parse(x[i].ToString()) - int.Parse(y[i].ToString()) + difference[i]; if (tmpdifference < 0) { tmpdifference += 10; difference[i - 1] = -1;//表示借位 } difference[i] = tmpdifference; } StringBuilder returnvalue = new StringBuilder(string.Concat(difference).TrimStart('0')); { if (returnvalue.ToString() == "") { return "0"; } } if (flag == -1) { returnvalue = returnvalue.Insert(0, "-"); } return returnvalue.ToString(); } //比较大小 static int checkBigger(string x, string y) { if (x.Length > y.Length) { return 1; } else if (x.Length < y.Length) { return -1; } else { for (int i = 0; i < x.Length; i++) { if (int.Parse(x[i].ToString()) > int.Parse(y[i].ToString())) { return 1; } else if (int.Parse(x[i].ToString()) < int.Parse(y[i].ToString())) { return -1; } continue; } return 0; } } //模拟移位 static string Power10(string num, int n) { return num.PadRight(num.Length + n, '0'); } } }
加载全部内容