求 1 到 n 的和值(算法没设计好 , 会超时的哟) 时间限制 : 4 Sec 内存限制 : 128 MB [ 提交 ] 题目描述 你的超时吗,要学数据结构了,让你了解一下,算法中如果循环次数太多,不想办法优化一下,会超时的。 问题仍然是求 1 到 n 的和值。 输入 每行输入一个 n 值( n<=50000 ) 行数最多可达 1000000 行。 输出 与输入相对应,每行输出计算的和值。 样例输入 10 100 1000 10000 样例输出 s=55 s=5050 s=500500 s=50005000 提示 考虑大部分学生情况,不要求使用 __int64 或 long long ,如果怕数据长度不够,最多用 unsigned int 就足够了。另外,如果用循环超时,就要考虑算法简化,看能不能结合数学知识简化求解,节约程序运行时间。 针对上面的问题,首先编写程序采用循环累加的方法求累加和,结果为 “ Time Limit Exceeded” (即超时),为什么?程序可点击题头位置的 “ 【提交】 ” ,在 ACM 网站提交。 #include int main() { int n,i,s=0; while ( scanf ( "%d" ,&n)!=EOF) { s=0; for (i=1;i<=n;i++) s=s+i; printf ( "s=%d\n" ,s); } return 0; } 分析:对于上面的程序,最多有 ______ 行数据,每行数据最多循环累加 ________ 次,所以累加操作最多可达 _________ 次。而 1 秒仅可执行约“ 10 的 8 次方”次累加操作,本题时间限制为 4 秒,仅可执行约“ 4 乘以 10 的 8 次方”次累加操作,所以超时。 为了提高程序执行效率,正确的解法是推导数学模型,将循环累加改为用公式计算,程序如下所示。 #include int main() { unsigned int n,i,s; // freopen("d:\\1.in","r",stdin); // freopen("d:\\1.out","w",stdout); while ( scanf ( "%d" ,&n)!=EOF) { s=0; s=n*( _________ )/2; printf ( "s=%u\n" ,s); } return 0; } 分析:对于上面的程序,最多有 ______ 行数据,每行数据最多计算公式 ________ 次,所以公式计算最多可达 _________ 次。而本题限制时间为 1 秒,可执行约“ 10 的 8 次方”次累加操作,所以不会超时。