連續的演算法

1. 離散拉普拉斯演算法和連續拉普拉斯演算法有什麼區別

離散的是不連續的，比如1，2，3，4，5
連續的是不間斷的，比如1~5;
離散拉普拉斯演算法適用於離散的函數，連續拉普拉斯演算法適用於連續的函數

2. C#求連續數字的演算法

usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;

/*
*先排序（用sort方法），再依次求連續的數字的個數，選擇最長的列印。
*/

{
classProgram
{
staticvoidMain(string[]args)
{
intnTmpStart=0;
intnResultStart=0;
intnTmpConsecutiveNum=1;
intnResultConsecutiveNum=0;
int[]num={1,4,6,5,8,9,10,15,3,19,18,21,20,21,17};
Array.Sort(num);

nTmpStart=num[0];
for(inti=1;i<num.Length;i++)
{
if(num[i]==num[i-1])
{
if(i==num.Length-1)
{
if(nTmpConsecutiveNum>nResultConsecutiveNum)
{
nResultConsecutiveNum=nTmpConsecutiveNum;
nResultStart=nTmpStart;
}
}
else
{
continue;
}
}
elseif(num[i]==(num[i-1]+1))
{
nTmpConsecutiveNum++;
if(i==num.Length-1)
{
if(nTmpConsecutiveNum>nResultConsecutiveNum)
{
nResultConsecutiveNum=nTmpConsecutiveNum;
nResultStart=nTmpStart;
}
}
}
else
{
if(nTmpConsecutiveNum>nResultConsecutiveNum)
{
nResultConsecutiveNum=nTmpConsecutiveNum;
nResultStart=nTmpStart;
}
nTmpStart=num[i];
nTmpConsecutiveNum=1;
}
}
Console.WriteLine("最長連續數字：");
for(intj=0;j<nResultConsecutiveNum;j++)
{
Console.Write("{0}	",nResultStart+j);
}
Console.WriteLine();
}
}
}

3. 演算法實現——連續和問題

//VC 2005 測試通過

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int GetCount( int num )
{
//如果27=27 , 也算作在內請把cnt賦值為1
int sum=0, cnt=0;
int index=0, i=0;

while ( i <= num /2 +1 )
{
sum = i * (i+1) /2 - index *(index-1) /2;
if ( sum == num )
{

//cout<<endl<<num<<"="<<index;
//for ( int k=index+1; k<=i; k++ )
//{
//cout<< "+"<<k;
//}
index=++i;
cnt++;
}
else if ( sum > num )
{
index++;

}
else
{
i++;
}
}

return cnt;
}
void main()
{
int num=0;
string inPath="c:\\inFile.txt";
string outPath="c:\\outFile.txt";

ifstream inFile( inPath.c_str(), ios_base::in);

if ( !inFile )
{
cerr<<"Open file :" << inPath <<" failed! Exit....";
return;
}
ofstream outFile( outPath.c_str(), ios_base::out );
if ( !outFile )
{
cerr<< "Open file: " << outPath <<" failed! Exit...";
return;
}

while ( !inFile.eof() )
{
if ( inFile >>num )
{
outFile<<GetCount(num) <<endl;
}
else
{
inFile.clear();
inFile.get();
}
}
inFile.close();
outFile.close();

cout<<"\nEnter key to exit...";
cin.get();

}

4. 求最大連續區間和的幾種方法

定義最大連續區間和：給定一個長度為n的序列a[1],a[2]...a[n]，求一個連續的子序列a[i],a[i+1]...a[j-1],a[j]使得a[i]+a[i+1]...+a[j-1]+a[j]最大。

1、根據定義來枚舉：枚舉上下界i,j，維護一個max值

其中枚舉上下界的復雜度為O(n²)，求區間和復雜度為O(n)，所以總的時間復雜度是O(n^3)。

for(int i = 1; i <= n ; i++)

for(int j = i; j<= n; j++)

ans = max(ans,accumulate(a+i,a+j+1,0));

2、對求區間和的操作做預處理，令sum[i] = a[0] + a[1] + a[2] ... + a[i-1] + a[i] 計算區間和的復雜度可降為O(1)，枚舉上下界的復雜度不變，所以總的時間復雜度為O(n²)。

for(int i =1;i<=n;i++)

sum[i] = sum[i-1] + a[i];

for(int i = 1; i <= n ; i++)

for(int j = i; j<= n; j++)

ans = max(ans,sum[j]-sum[i-1]);

3、利用動態規劃的思維來繼續優化，得到一個線性的基本演算法，也是基本連續子區間和的標准演算法：

定義maxn[i]為以i為結尾的最大連續和，則很容易找到遞推關系：maxn[i] = max{0,max[i-1] + a[i]}

所以只要掃描一遍即可，總時間復雜度為O(n)。

for(int i =1; i <= n; i++)

{

last = max(0,maxn[i-1]) + a[i];

ans = max(ans,last);

}