分治策略是：
对于一个规模为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');
}
}
}到此这篇关于C#实现分治算法求解股票问题的文章就介绍到这了,更多相关C# 分治算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
