波浪线算法解答


现在给一个数,1000
计算后返回一个序列,类似于20 50 100 200 100 50 20的一个序列,这个序列的和等于刚才给的数字。
有点像在画波浪线,最好还能有个参数,可以指定这个波浪的大小

讨论 数据结构 算法

醋11111 12 years, 2 months ago

特征:
一,此序列点数量为奇数个,对称,先增后减。(设点的数量为D)
二,后边(不包括最大值)和固定。(设和为S,最大值为M,后边和为rearSum,点数为rearDot).

参数:
S,D,M都需要自己设置
关于S,以下算法都是基于S>0。
关于D,要求是奇数。
关于M,M>S/D,还一点要求见下边<Mark1>。

算法:
rearDot初值为((D-1)/2),rearSum初值为(S-M)/2。由此我们可以从顶端开始构造序列的后半部分:
第一个值为(rearSum/rearDot,M)中的一个数,关于怎么选见下边<Mark2>。选完后用这个值替换M,rearSum变为rearSum减M,rearDot自减1。
第二个值同上处理。
……
……
第((D-1)/2)个值,即序列的第一个值,是rearSum。停止循环。

<Mark1>:
不知道楼主是否要求所有数都是整数,如果要求,则注意M的奇偶取决于S。
<Mark2>:
关于(rearSum/rearDot,M)中的一个数要选,楼主可以随机,也可以自己选,这决定了“波浪的形状”。如果想要曲线是馒头状,建议选M-k (M-rearSum/rearDot)/rearDot; 如果想要曲线是玫瑰刺状,建议选rearSum/rearDot+k (M-rearSum/rearDot)/rearDot。其中k是调节参数,取值范围(0,1)。以前者为例写下代码:

代码:

   
  ……                    #输入常量S,D,M,k;
  
$S=S;$D=D;$M=M;$k=k;
$rearDot=(($D-1)/2);

$rearSum=($S-$M)/2;

   
  for($i=0,$i<((D-1)/2-1),$i++)    #序列从顶部开始向下延伸,一直到最小数。
  
{
$arrayRear[$i]=$M-$k*($M-$rearSum/$rearDot)/$rearDot;
$M=$arrayRear[$i];
$rearSum=$rearSum-$M;
$rearDot--;
}
array_push ($arrayHead,$rearSum); #将最小数压入数组。
$arrayHead=reverse_array($arrayRear); #前半部分需要对称上。
array_push ($arrayHead,M); #将最大值压入数组。

print_r(array_merge($arrayHead,$arrayRear));#合并前后数组并输出。

wyf4get answered 12 years, 1 month ago

Your Answer