第2题：
double mysqrt(double y)
{
double low,high,x; //here x is the same as middle;
low=0.0,high=y;
x=(low+high)/2;
while(low <= high && !(abs(x*x - y) <= 0.001)){
if(x*x - y > 0){ //x is larger than supposed;
high=x;
x=(low+high)/2;
}else if(x*x - y < 0){ ////x is smaller than supposed;
low=x;
x=(low+high)/2;
}
else
break;
}
return x;
}
不好意思，上面的代码测试有个问题；可能是abs()精度不够，修改如下就可以了。
double mysqrt(double y)
{
double low,high,x; //here x is the same as middle;
low=0.0,high=y;
x=(low+high)/2;
while(low <= high && !(x*x - y <= 0.001 && x*x - y >= -0.000001)){
if(x*x - y > 0) //x is larger than supposed;
high=x;
else if(x*x - y < 0) ////x is smaller than supposed;
low=x;
else
break;
x=(low+high)/2;
}
return x;
}第3题：
思想是把n换成2进制，5=101=1*1+10*0+100*1=1+0+4,
则x的n次方=x^(1+0+4)=x^1 * X^4 ,略过0位就可以了；程序如下：
double mypow(double x, int n)
{
int bin[128],i,max;
double pow,prepow;
for(i=0;n>=1;++i){ //convert n to binary;
bin[i]=n%2;
n=n/2;
}
max=--i;
pow=1.0,prepow=x;
for(i=0;i<=max;++i){
(bin[i]==1)?(pow=pow*prepow):0;
prepow=prepow*prepow;
}
return pow;
}递归版：
#include <stdio.h>
double mypow(double x, int n)
{
if (n)
if (n % 2 == 0)
return mypow(x, n/2) * mypow(x, n/2);
else
return x * mypow(x, n-1);
else
return 1;
}
int main(void)
{
printf("%f\n", mypow(2, 4));
return 0;
}
循环版：
#include <stdio.h>
double mypow(double x, int n)
{
int i = 1, temp = n;
double product = x;
if (n % 2 != 0)
temp = n - 1;
while (i < temp) {
product = product * product;
i *= 2;
}
if (temp == n - 1)
product *= x;
return product;
}
int main(void)
{
printf("%f\n", mypow(2, 5));
return 0;
}例 11.5. 带有测试代码的折半查找 int mustbe(int start, int end, int number) 这个函数不很矛盾吗？本来是折半的，又搞个遍历？查错不能这样处理吧。
所以才要用NDEBUG和assert，非DEBUG版不调用mustbe
第2题：
#include <stdio.h>
double mysqrt(double y)
{
double x, low = 0.0, high = y;
while (low <= high) {
x = (low + high) / 2;
if (x * x - y >= 0.001)
high = x;
else if (x * x - y < 0 && x * x - y <= -0.001)
low = x;
else
break;
}
return x;
}
int main(void)
{
printf("%f\n", mysqrt(64.0000));
return 0;
}
循环版第三题
/*
* =========================================================================
*
* Filename: mypow.c
*
* Description: 编写一个函数double mypow(double x, int n);
* 求x的n次方，参数n是正整数。算法复杂度考虑lgn。
*
* Created: 2010年12月05日 17时20分36秒
* Compiler: gcc
* ==========================================================================
*/
#include <stdio.h>
double mypow(double x, int n)
{
int j, product = x, i = 2;
if (n == 1)
return x;
while (i <= n) {
product *= product;
i *= 2;
}
for (j = 0; j < n - i / 2; j++)
product *= x;
return product;
}
int main(void)
{
printf("%f\n", mypow(2, 10));
return 0;
}
递归版：
/*
=========================================================================
*
* Filename: mypow.c
*
* Description: 编写一个函数double mypow(double x, int n);
* 求x的n次方，参数n是正整数。算法复杂度考虑lgn。
*
* Compiler: gcc
* ==========================================================================
*/
#include <stdio.h>
double mypow(double x, int n)
{
if (n == 0)
return 1;
if (n == 1)
return x;
if (n % 2 != 0)
return x * mypow(x, n - 1);
else
return mypow(x, n / 2) * mypow(x, n / 2);
}
int main(void)
{
printf("%f\n", mypow(2, 11));
return 0;
}
to laciqs : 你的循环算法，n [1,9]是正确的，到了10就错误了。
递归平方：
double mypow(double x, int n)
{
if (2 == n)
return x*x;
else if (1 == n)
return x;
else if (0 == n)
return 1;
return mypow3(mypow3(x, n/2), 2) * (n % 2 ? x : 1);
}
循环算法写不出来……double mypow(double x, int n) 改成 double mypow3(double x, int n)
#include<stdio.h>
//循环算法
double mypow(double x,int num)
{
int i=1,pow=x,flag = 0;
if(num % 2 != 0){
num += 1;
flag = 1;
}
while(i < num){
pow *= pow;
i *= 2;
}
if(flag){
pow /= x;
}
return pow;
}
//递归算法
double mypow2(int pow, int num, int i)
{
if(i < num){
pow *= pow;
i *= 2;
return mypow2(pow, num, i);
}else{
return pow;
}
}
//递归算法
double get_mypow(double x, int num)
{
int i=1, pow=x, flag = 0;
if(num % 2 != 0){
num += 1;
flag = 1;
}
pow = mypow2(pow, num,i);
if(flag){
pow /= x;
}
return pow;
}
int main(void)
{
printf("%f\n",mypow(2,8));
return 0;
}第一题：
#include <stdio.h>
#define LEN 8
int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };
int binarysearch(int number)
{
int mid, start = 0, end = LEN - 1;
int result = -1;
while (start <= end) {
mid = (start + end) / 2;
if (a[mid] < number)
start = mid + 1;
else if (a[mid] > number)
end = mid - 1;
else {
if (number == a[mid]) {
result = mid;
end = mid - 1;
}
}
}
return result;
}
int main(void)
{
printf("%d\n", binarysearch(2));
return 0;
}
另外，上面我写的mypow递归版中，return那句造成算法度高一个等级 应将 return mypow(x, n / 2) * mypow(x, n / 2); 改为 return mypow(x*x, n / 2);
回头看看，自己写的函数真是惨不忍睹
mypow 递归版
#include <stdio.h>
double mypow(double x, int n)
{
if (n == 0)
return 1;
if (n % 2 != 0)
return x * mypow(x, n - 1);
else
return mypow(x, n / 2) * mypow(x, n / 2);
}
int main(void)
{
printf("%f\n", mypow(2, 8));
return 0;
}
晕，直接copy&&paste了
修改之
mypow 递归版
#include <stdio.h>
double mypow(double x, int n)
{
if (n == 0)
return 1;
if (n % 2 != 0)
return mypow(x*x, n - 1);
else
return mypow(x, n / 2) * mypow(x, n / 2);
}
int main(void)
{
printf("%f\n", mypow(2, 8));
return 0;
}
靠，喝多了，还是错了
#include <stdio.h>
double mypow(double x, int n)
{
if (n == 0)
return 1;
if (n % 2 != 0)
return mypow(x, n - 1) * x;
else
return mypow(x * x, n / 2);
}
int main(void)
{
printf("%f\n", mypow(2, 16));
return 0;
}
递归版：
#include <stdio.h>
#include <stdlib.h>
double mypow(double x, int n)
{
double product = 1;
if (n == 0)
return 1;
while (n)
if (n % 2 == 0) {
product *= x * x;
n -= 2;
} else {
product *= x;
n -= 1;
}
return product;
}
int main(int argc, char *argv[])
{
printf("%f\n", mypow(2, 32));
return EXIT_SUCCESS;
}
这样，递归版算法对了，循环版算法复杂度还是On
我再想想
嗯，想出来了。。。
#include <stdio.h>
#include <stdlib.h>
double mypow(double x, int n)
{
double product = 1;
if (n == 0)
return 1;
while (n)
if (n % 2 == 0) {
product = product * product * x;
n /= 2;
} else {
product *= x;
n -= 1;
}
return product;
}
int main(int argc, char *argv[])
{
printf("%f\n", mypow(3, 32));
return EXIT_SUCCESS;
}
这样，递归版算法对了，循环版算法复杂度还是On 我再想想 晕，循环版经验证，错误 麻烦老师大大把前面错误的都删除吧 我睡觉去，明天再做
Errr，还是没做出循环版mypow
参考的别人的代码
#include <math.h>
#include <stdio.h>
#include <stdio.h>
#include <math.h>
double mypow(double x, int n)
{
double result = 1.0;
if (n == 0)
return 1;
while (n) {
if (n & 1)
result *= x;
x *= x;
n >>= 1;
}
return result;
}
int main(void)
{
for (int i = 0; i < 16; i++)
printf("%-2d: mypow: %-10.0f \t pow:%-10.0f\n", i,
mypow(2, i), pow(2, i));
return 0;
}
上面有位同仁给的不完全正确，这里给出我的补充，不要见笑。
#include<stdio.h>
#define LEN 8
int a[LEN]={1,2,2,2,5,6,8,9};
//bool flag=true;
int binarysearch(int number)
{
int mid,start=0,end=LEN-1,temp=0;
// bool flag=true;
while(start<=end){
mid=(start+end)/2;
if(a[mid]<number)
start=mid+1;
else if(a[mid]>number)
end=mid-1;
else
{
temp=mid-1;
while(1)
{
// temp=mid-1;
if(a[temp]==a[mid])
temp--;
else{
mid=temp+1;
break;
}
}
return mid;
}
}
return -1;
}
int main()
{
int i=0;
i=binarysearch(2);
printf("%d\n",i);
}可参考 SICP exercise 1.16
利用状态变量a（初始为1）, 使a*b^n为一不变值，逐渐将n减少，直至n为0时，a就取得开始时a*b^n即pow(base, n)的值。
#include <stdio.h>
/* a loop inplementation */
double mypow(double base, int exp)
{
double a = 1.0;
while (1)
{
if (exp == 0)
return a;
else if (exp % 2 == 0)
{
base *= base;
exp /= 2;
}
else if (exp % 2 != 0)
{
a *= base;
exp--;
}
}
}
int main(void)
{
double x = 2.0;
int exp = 4;
printf("%lf\n", mypow(x, exp));
return 0;
}如果您有建设性意见，哪怕只是纠正一个错别字，也请不吝赐教，您留下的姓名和email将会出现在本书前言的致谢中。再次感谢您的宝贵意见！