計算と所与の数の連続正の整数数列

例えばsn=100の場合、総和が100の連続正整数数列には1 100 2 18 19 20 21 22 3 9 10 11 12 13 14 15 16
このアルゴリズムの設計では,1からsnまですべての数をループし,この数を起点とする合計がちょうどsnであるか否かを各数について再循環計算することが最も容易に考えられる.このアルゴリズムの時間的複雑度はO(n*log 2 n)程度であり,このように計算するとsn=100万の場合,2000万回程度のサイクルが必要となる.このようにするのは自然に効率が低い.では、上記の方法よりも効率的な方法はありますか?答えは肯定的だ.
まず,等差数列の和を求める式を見る:Sn=n(a 1+an)/2=na 1+n(n-1)/2
この式から,Snとnが固定されているときのa 1を求めることは,a 1＝(Sn‐n(n‐1)／2)／nの線形関数であることが明らかになった.
この関数があれば,このアルゴリズムを最適化することは簡単であるが,nを1から遍歴し,(Sn−n(n−1)/2)题目:1～500の500の整数の中で、连続加算が500に等しい数を探し出しますか?
簡単な分析:int[]X={1,2,i,............499}
条件は、i+(i+1)+......+(i+k)=500(1式)
等差数列を用いて式を求める:(k+1)*i+(k+1)*k/2=500(2式)
このうちiとkにはもう一つの隠し関係i*k<500(3式)がある
そこで自然に次のような解法が得られます.

 0 && ($h + $i - 1) <= $max) {
for ($j = 0; $j < $i; ++$j) {
echo $h++ . ';';
}
echo '
';
}
}
?>