C#實現(xiàn)分治算法求解股票問題
更新時間：2022年04月27日 11:13:09 作者：Angel
本文主要介紹了C#實現(xiàn)分治算法求解股票問題，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習或者工作具有一定的參考學(xué)習價值，需要的朋友們下面隨著小編來一起學(xué)習學(xué)習吧
分治策略是：
對于一個規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計策略叫做分治法。
可使用分治法求解的一些經(jīng)典問題
（1）二分搜索
（2）大整數(shù)乘法
（3）Strassen矩陣乘法
（4）棋盤覆蓋
（5）合并排序
（6）快速排序
（7）線性時間選擇
（8）最接近點對問題
（9）循環(huán)賽日程表
（10）漢諾塔
分治算法 - 最大子數(shù)組問題
股票問題：
（1）暴力求解
嵌套循環(huán)，遍歷所有的子數(shù)組，找到最大的子數(shù)組，從13開始遍歷，一直遍歷到7，找到最大的子數(shù)組，再從-3開始遍歷，找到最大子數(shù)組，最簡單粗暴，耗費性能最高，最消耗時間。
/****************************************************
* 功能：使用暴力求解股票價格購買問題
*****************************************************/
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};//價格數(shù)組
int[] priceFluctuationArray = new int[priceArray.Length - 1];//價格波動的數(shù)組
for (int i = 1; i < priceArray.Length; i++)//給價格波動表賦值
{
priceFluctuationArray[i-1] = priceArray[i] - priceArray[i - 1];//當天價格-上一天價格
}
int total = priceFluctuationArray[0];//默認第一個元素是最大子數(shù)組的和
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < priceFluctuationArray.Length; i++)
{
//取得以i為子數(shù)組起點的所有子數(shù)組
for (int j = i; j < priceFluctuationArray.Length; j++)//以i開始以i結(jié)束
{
//由i,j就確定了一個子數(shù)組
int totalTemp = 0;//臨時最大子數(shù)組的和
for (int k = i; k < j+1; k++)
{
totalTemp += priceFluctuationArray[k];//當前子數(shù)組的和
}
if (totalTemp>total)//判斷當前子數(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]兩個區(qū)間，
i為子數(shù)組的開始索引，j為子數(shù)組的結(jié)束索引：
- i j 同時位于低區(qū)間
- i j 同時位于高區(qū)間
- i 位于低區(qū)間，j位于高區(qū)間
因為ij是由mid分隔的，分別取得在low mid里面的i值，mid high里面的j值
/****************************************************
* 功能：使用分治法求解股票價格購買問題
*****************************************************/
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};//價格數(shù)組
int[] priceFluctuationArray = new int[priceArray.Length - 1];//價格波動的數(shù)組
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這個數(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;//臨時的和
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;
}
}
}分治法實現(xiàn)大數(shù)相乘 C#實現(xiàn)
用C#實現(xiàn)，盡可能的利用C#的特性。本例中，只要拆分的數(shù)字小于9位數(shù)，就可以直接相乘計算，保證不會溢出。
在編程中，還需要用的加法和減法，也要通過字符串模擬實現(xiàn)。
最終的乘法運算，依賴遞歸思想得以實現(xiàn)。
本文的代碼還有一些可以優(yōu)化的地方，比如對于不使用字符串而是全部使用數(shù)組，可能會更快點。
代碼如下：
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ù)公式計算出值。
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是正數(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補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#實現(xiàn)分治算法求解股票問題的文章就介紹到這了,更多相關(guān)C# 分治算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于C# LINQ的基本使用教程，文中通過示例代碼介紹的非常詳細，對大家學(xué)習或者使用C# LINQ具有一定的參考學(xué)習價值，需要的朋友們下面來一起學(xué)習學(xué)習吧2020-08-08
這篇文章主要介紹了如何利用WPF繪制一個簡單的環(huán)形菜單，文中的示例代碼講解詳細，對我們學(xué)習或工作有一定幫助，需要的可以參考一下2022-07-07
這篇文章主要為大家詳細介紹了C#的觀察者模式，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要介紹了C#基于面向過程計算加權(quán)平均分的方法,涉及C#數(shù)學(xué)運算的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
如果要給方法傳遞一個方法參數(shù)時，就可以使用委托。下面這篇文章主要給大家介紹了關(guān)于C#沉淀之委托的相關(guān)資料，文中通過示例代碼介紹的非常詳細，需要的朋友可以參考下2018-09-09
這篇文章主要介紹了使用c#生成驗證碼的示例，大家參考使用吧2014-01-01
本篇文章主要介紹了說說C#的async和await的具體用法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-09-09
C#通過Win32API設(shè)置客戶端系統(tǒng)時間的方法詳解
在日常工作中,有時可能會需要獲取或修改客戶端電腦的系統(tǒng)時間,比如軟件設(shè)置了Licence有效期,本文以一個簡單的小例子,簡述如何通過C#獲取和設(shè)置客戶端電腦的系統(tǒng)時間,僅供學(xué)習分享使用,如有不足之處,還請指正,需要的朋友可以參考下2024-06-06
C#中實現(xiàn)PriorityQueue優(yōu)先級隊列的代碼
這篇文章主要介紹了C#中PriorityQueue優(yōu)先級隊列的實現(xiàn),構(gòu)造初始化這部分主要介紹關(guān)鍵的字段和方法，比較器的初始化以及堆的初始化，需要的朋友可以參考下2021-12-12
這篇文章主要介紹了C#遍歷刪除字符串中重復(fù)字符的方法,涉及C#遍歷字符串的相關(guān)技巧,非常具有實用價值,需要的朋友可以參考下2015-04-04