xin

关心

随笔 - 84, 评论 - 739, 引用 - 40

关于

所有内容均属个人意见，没有任何担保或授权，以"现状"提供。“现状”到底是什么，我也不一定清楚。

每月存档

留言反馈

#re: ms2.3 培训和程序练习编辑

一个数组a存{1, x1, x1*x2, x1*x2*x3, ..., x1*...*x(n-1) }
一个数组b存{x2*...*xn, x3*...*xn, ..., xn, 1}
构造这俩数组都只需要O(n)
输出result[i] = a[i] * b[i]

2006-08-22 19:53:00 | [匿名:lookus]

#re: ms2.3 培训和程序练习编辑

你这个算法，只是换了一个除法的算法，能够满足要求吗？
我有一个算法，计算下来，似乎比O(N)大一点
long double results[1024];
long double inputs[1024];

long double calc(int nBegin, int nEnd)
{
//计算inputs[nBegin]到inputs[nEnd]的乘积
//同时计算results[nBegin]到results[nEnd]
if (nBegin==nEnd)
{
return inputs[nBegin];
}
else if (nBegin==(nEnd-1))
{
results[nBegin]*=inputs[nEnd];
results[nEnd]*=inputs[nBegin];
return inputs[nBegin]*inputs[nEnd];
}
else
{
//二分
int nMid=(nEnd+nBegin)/2;
long double fFirst=calc(nBegin, nMid);
long double fLast=calc(nMid+1, nEnd);
//再计算乘积
for (size_t i=nBegin; i<=nEnd; i++)
{
if (i<=nMid)
{
results[i]*=fLast;
}
else
{
results[i]*=fFirst;
}
}
return fFirst*fLast;
}
}

int main()
{
calc(0, n-1);
output(results);
}

2006-07-19 20:40:00 | [匿名:aaa]

#re: ms2.3 培训和程序练习编辑

先求n个数中非零数的积记为S，所有数中零的个数记为Z,复杂度O(n)，
即，
S:=1;
Z:=0;
for i:=1 to n do
if Xi=0 then
Z:=Z+1
else
S:=S*Xi;

然后
for i=1 to n do
begin
if Xi=0 then
if Z=1 then
result:=S
else
result:=0
else //Xi<>0
if Z>0 then
result:=0
else
//计算S乘以Xi的倒数
//因为不能用除法，所以用以下公式计算：
//1/Xi=Xi^(-1)

if Xi>0 then
//log(1/Xi)=log(Xi^(-1))=-log(Xi)
//so, 1/Xi=exp(-log(Xi))
result:=S*exp(-log(Xi))
else //当Xi<0
//1/Xi=-exp(-log(-Xi))
result:=-S*exp(-log(-Xi));

output(result);
end;

两趟1~n的循环即可。不知道是否满足要求？:-)

2006-06-29 07:22:00 | [匿名:menway]

#re: ms2.3 培训和程序练习编辑

用随即方法得到一个随即数

2006-06-15 02:25:00 | [匿名:吃掉大象的蚂蚁]

#re: ms2.3 培训编辑

7周难忘的经历～～为老师们的精彩课程和同学们的passion所深深感染！

2006-06-04 06:19:00 | [匿名:NickLedson]

对不起，目前本随笔不允许发表新评论.

xin

导航

关于

标签

每月存档

最新留言

广告

留言反馈