C语言--用二分法快速计算指定整数的整数平方根

题目：给定一个正整数，小于2的63次方。要求不是用pow,sqrt等算法库函数，快速计算指定正整数的平方根（保留整数部分）。

普通办法是从1开始计算平方数，如果给定的正整数在相邻两个平方数之间，那么 较小的整数就是所需要的答案。但此方法效率较低，比如2的60次方的平方根可能要计算很长时间。那么可以采用二分法进行搜索，平方根肯定小于整数的一半，所以可以在1到n/2之间进行二分法搜索。分别找出比指定整数大和小且差值为1的整数，即为结果。

#include <stdio.h> #include <stdlib.h> int main() {long long x,left,right,h,l,mid;int k=0;while(scanf("%lld",&x) == 1 && x != 0){left = 1;right = x/2;h = right;l = left;k = 0;while(left < right){k++;mid = (left + right)/2;if(mid * mid == x){printf("%lld * %lld = %lld\n",mid,mid,mid*mid);break;}else if(mid * mid < x){if(mid == h-1){printf("%lld * %lld = %lld\n",mid,mid,mid*mid);break;}left = mid;l = left;}else{if(mid == l+1){ printf("%lld * %lld = %lld\n",l,l,l*l);break;}right = mid;h = right;}}printf("k=%d\n",k); //显示计算的次数}return 0; }

总结

以上是生活随笔为你收集整理的C语言--用二分法快速计算指定整数的整数平方根的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。