對于一個(gè)規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解決，否則將其分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計(jì)策略叫做分治法。

可使用分治法求解的一些經(jīng)典問題

（1）二分搜索

（2）大整數(shù)乘法

（3）Strassen矩陣乘法

（4）棋盤覆蓋

（5）合并排序

（6）快速排序

（7）線性時(shí)間選擇

（8）最接近點(diǎn)對問題

（9）循環(huán)賽日程表

（10）漢諾塔

分治算法 - 最大子數(shù)組問題

股票問題：

（1）暴力求解

嵌套循環(huán)，遍歷所有的子數(shù)組，找到最大的子數(shù)組，從13開始遍歷，一直遍歷到7，找到最大的子數(shù)組，再從-3開始遍歷，找到最大子數(shù)組，最簡單粗暴，耗費(fèi)性能最高，最消耗時(shí)間。

/****************************************************
 *  功能：使用暴力求解股票價(jià)格購買問題
*****************************************************/
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};//價(jià)格數(shù)組
        int[] priceFluctuationArray = new int[priceArray.Length - 1];//價(jià)格波動(dòng)的數(shù)組
        for (int i = 1; i < priceArray.Length; i++)//給價(jià)格波動(dòng)表賦值
        {
            priceFluctuationArray[i-1] = priceArray[i] - priceArray[i - 1];//當(dāng)天價(jià)格-上一天價(jià)格
        }
        int total = priceFluctuationArray[0];//默認(rèn)第一個(gè)元素是最大子數(shù)組的和
        int startIndex = 0;
        int endIndex = 0;
        for (int i = 0; i < priceFluctuationArray.Length; i++)
        {
            //取得以i為子數(shù)組起點(diǎn)的所有子數(shù)組
            for (int j = i; j < priceFluctuationArray.Length; j++)//以i開始以i結(jié)束
            {
                //由i,j就確定了一個(gè)子數(shù)組
                int totalTemp = 0;//臨時(shí)最大子數(shù)組的和
                for (int k = i; k < j+1; k++)
                {
                    totalTemp += priceFluctuationArray[k];//當(dāng)前子數(shù)組的和
                }
                if (totalTemp>total)//判斷當(dāng)前子數(shù)組的和是否大于總和
                {
                    total = totalTemp;//最大子數(shù)組的和
                    startIndex = i;//最大子數(shù)組的開始索引
                    endIndex = j;//最大子數(shù)組的結(jié)束索引
                }
            }
        }
        Debug.Log("startIndex："+startIndex);
        Debug.Log("endIndex："+endIndex);
        Debug.Log("購買日期是第"+startIndex+"天 出售日期是第"+(endIndex+1)+"天");
    }
}

（2）分治法

?求low和high數(shù)組的最大子數(shù)組（區(qū)間）（和最大）：

由low和high取得中間的mid索引，由最初的[low,high]區(qū)間得到[low,mid][mid+1,high]兩個(gè)區(qū)間，

i為子數(shù)組的開始索引，j為子數(shù)組的結(jié)束索引：

i j 同時(shí)位于低區(qū)間
i j 同時(shí)位于高區(qū)間
i 位于低區(qū)間，j位于高區(qū)間

因?yàn)閕j是由mid分隔的，分別取得在low mid里面的i值，mid high里面的j值

/****************************************************
 *  功能：使用分治法求解股票價(jià)格購買問題
*****************************************************/
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Test : MonoBehaviour
{
    struct SubArray//最大子數(shù)組的結(jié)構(gòu)體
    {
        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};//價(jià)格數(shù)組
        int[] priceFluctuationArray = new int[priceArray.Length - 1];//價(jià)格波動(dòng)的數(shù)組
        for (int i = 1; i < priceArray.Length; i++)//給價(jià)格波動(dòng)表賦值
        {
            priceFluctuationArray[i-1] = priceArray[i] - priceArray[i - 1];//當(dāng)天價(jià)格-上一天價(jià)格
        }
        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這個(gè)數(shù)組從low到high之間的最大子數(shù)組
    {
        if (low==high)//遞歸結(jié)束的終止條件
        {
            SubArray subArray;
            subArray.startIndex = low;
            subArray.endIndex = high;
            subArray.total = array[low];
            return subArray;
        }
        int mid = (low + high) / 2;//低區(qū)間[low,mid]高區(qū)間[mid+1,high]
        SubArray subArray1=GetMaxSubArray(low, mid, array);//低區(qū)間最大子數(shù)組
        SubArray subArray2=GetMaxSubArray(mid + 1, high, array);//高區(qū)間最大子數(shù)組
        //從[low,mid]找到最大子數(shù)組[i,mid]
        int total1 = array[mid];//最大子數(shù)組的和
        int startIndex = mid;//最大子數(shù)組的開始索引
        int totalTemp = 0;//臨時(shí)的和
        for (int i = mid; i >=low; i--)//從mid向low遍歷
        {
            totalTemp += array[i];
            if (totalTemp>total1)
            {
                total1 = totalTemp;
                startIndex = i;
            }
        }
        //從[mid+1,high]找到最大子數(shù)組[mid+1,j]
        int total2 = array[mid+1];//最大子數(shù)組的和
        int endIndex = mid+1;//最大子數(shù)組的結(jié)束索引
        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;
        }
    }
}

分治法實(shí)現(xiàn)大數(shù)相乘 C#實(shí)現(xiàn)

用C#實(shí)現(xiàn)，盡可能的利用C#的特性。本例中，只要拆分的數(shù)字小于9位數(shù)，就可以直接相乘計(jì)算，保證不會(huì)溢出。

在編程中，還需要用的加法和減法，也要通過字符串模擬實(shí)現(xiàn)。

最終的乘法運(yùn)算，依賴遞歸思想得以實(shí)現(xiàn)。

本文的代碼還有一些可以優(yōu)化的地方，比如對于不使用字符串而是全部使用數(shù)組，可能會(huì)更快點(diǎn)。

代碼如下：

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;
            //遞歸調(diào)用，根據(jù)公式計(jì)算出值。
            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;//表示進(jìn)位
                }
                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是正數(shù)，y也是正數(shù)
            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補(bǔ)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');
        }
                                      
    }
}

到此這篇關(guān)于C#實(shí)現(xiàn)分治算法求解股票問題的文章就介紹到這了,更多相關(guān)C# 分治算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: