UC知道一道C语言编程题目，要怎样效率比较高呢？
来源：百度知道 编辑：UC知道 时间：2024/06/21 23:50:59
比如一串数a[100000]={1,2,3,6,8,3,2,0,9……}然后执行代码如下
for(i=0;i<n;i++)//n为数字个数
for(j=i;j<n;j++)
ans+=a[i]*a[j];
这样明显的每次都多做了不必要的计算，当N变得大了之后效率会很低，请问大家要如何实现同功用而效率高很多呢？
谢谢了
不好意思写错了，第二个循环里应该是for(j=0;j<n;j++) ，如果用很大的二维数组保存结果的话估计会超内存，是要DP吗？不会啊 ，我只是想求一个效率高的，要是会溢出的话，改成这样如何？ans+=a[i]+a[j] ,请回答者先弄清楚在哪里冗余计算了，再回答好吗
for(i=0;i<n;i++)//n为数字个数
for(j=i;j<n;j++)
ans+=a[i]*a[j];
这样明显的每次都多做了不必要的计算，当N变得大了之后效率会很低，请问大家要如何实现同功用而效率高很多呢？
谢谢了
不好意思写错了，第二个循环里应该是for(j=0;j<n;j++) ，如果用很大的二维数组保存结果的话估计会超内存，是要DP吗？不会啊 ，我只是想求一个效率高的，要是会溢出的话，改成这样如何？ans+=a[i]+a[j] ,请回答者先弄清楚在哪里冗余计算了，再回答好吗
这样写： for(int i=0;i<n;i++)
{
ans+=a[i]*a[i];
for(int k=i+1;k<n;k++)
{
ans+=2*a[i]*a[k];
}
}
判断a[i]!=0才for(j=0;j<n;j++)
每多一个0,就少算一轮.合算..
你的结果...很容易超过界限溢出的.
------------关于冗余
你根本没有说什么才是不要的计算,按你写的程序,就是所有的元素都要算一次.
只有当一个元素为0的时候,才是冗余的,判断a[i]!=0,代价最小
for(i=0;i<n;i++)ans+=a[i];
ans*=ans;
让别人回答，要把你的题意说明白了，到现在不知道你要算一个什么结果，别人怎么回答
你这是要问什么呢？？你是问这个题目吗？？一个数*它后面的积！~！我想是没有更好的办法了！~因为每一步都是必要的！~少一个都不行！~！~
对了，，你可以判断a[i]是否是0，，要是0就不用了，，不过这样的话，用来判断的也会比不判断得多多了，！~所以怎么都不行！~1
我觉得没办法。。