求s=a+aa+aaa+aaaa+aa...a的值

求s=a+aa+aaa+aaaa+aa...a的值,
其中a是一个数字。
例如2+22+222+2222+22222(此时共有5个数相加)。

1#include <stdio.h>
2
3long getNDigitSum(int digit, int n) {
4  long r=0, s=0;  // r表示所有数的和,s表示n个digit组成的数
5  int i=n;
6  while(i>0) {
7    s = s*10L + (long)digit;
8    r = r + s;
9    i--;
10  }
11  return r;
12}
13
14int main() {
15  int digit, n;
16  digit=2; n=5; printf("digit=%d, n=%d, result=%d\n", digit, n, getNDigitSum(digit, n));
17
18  return 0;
19}
#include <stdio.h>



long getNDigitSum(int digit, int n) {

  long r=0, s=0;  // r表示所有数的和,s表示n个digit组成的数

  int i=n;

  while(i>0) {

    s = s*10L + (long)digit;

    r = r + s;

    i--;

  }

  return r;

}



int main() {

  int digit, n;

  digit=2; n=5; printf("digit=%d, n=%d, result=%d\n", digit, n, getNDigitSum(digit, n));



  return 0;

}

两个整数的平均数

这个看起来很简单,(a+b)/2
但是需要考虑溢出问题,所以有人改为a+(b-a)/2
还需要考虑负数的问题,如a是整数,b是负数,还是可能溢出
int averagePerfect(int a, int b) {  
    return (a&b) + ((a^b) >> 1);  
}  
设a的二进制表示为a[31]a[30]a[29]...a[0],
类似的b的二进制表示为b[31]b[30]...b[0],
结果用c变量来存,同样他的二进制表示为c[31]c[30]..c[0].
那么c=(a+b)>>1用二进制表示就是
c[n]=((a[n+1]+b[n+1])的低位+(a[n]+b[n])的高位)=((a[n+1]^b[n+1]))+(a[n]&b[n]),
换成a,b,c来看就是c=(a&b) + ((a^b)>>1)了,
如果还不清楚,可以将n取的小一些,然后自己列列竖式就行了.
其实也可以这样理解,先求两者值和,表示为(a^b) + ((a&b)<<1)
然后除2就是右移,所以变成了((a^b) >> 1)+(a&b)


1#include <stdio.h>
2
3// 求整数的和
4int sum2int(int a, int b) {
5  int ret = (a^b) + ((a&b)<<1);
6  printf("Sum(%d, %d)=%d\n", a, b, ret);
7  return ret;
8}
9
10// 类似的方法求平均数
11int averagePerfect(int a, int b) {
12  int ret = (a&b) + ((a^b) >> 1);
13  printf("Average(%d, %d)=%d\n", a, b, ret);
14  return ret;
15}
16
17int main() {
18  sum2int(12, 345); averagePerfect(55, 534);
19  averagePerfect(115, 34);
20  return 0;
21}
22
23
#include <stdio.h>



// 求整数的和

int sum2int(int a, int b) {

  int ret = (a^b) + ((a&b)<<1);

  printf("Sum(%d, %d)=%d\n", a, b, ret);

  return ret;

}



// 类似的方法求平均数

int averagePerfect(int a, int b) {

  int ret = (a&b) + ((a^b) >> 1);

  printf("Average(%d, %d)=%d\n", a, b, ret);

  return ret;

}



int main() {

  sum2int(12, 345); averagePerfect(55, 534);

  averagePerfect(115, 34);

  return 0;

}





开心数


1/* 让我们定义正整数S0中每个数字的平方和为S1。
2 * 以相同的方法我们定义S1中 每个数字的平方和为S2,并依此类推。
3 * 假如有某个Si = 1( i >= 1)则我们说S0是一个Happy number。
4 * 如果某一个数不是Happy number,那他就是一个 Unhappy number。
5 * 例如: 7 是一个 Happy number,
6 * 因为 7 -> 49 -> 97 ->130 -> 10 -> 1。
7 * 但是 4 是一个Unhappy number,
8 * 因为 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4,永远也无法产生 1。
9 */
10
11#include <stdlib.h>
12#include <iostream>
13#include <vector>
14
15using namespace std;
16
17int happy_next(int n) {
18  int sum=0;
19  int c, r;
20
21  r=n;
22  while(1) {
23    c=r%10;
24    sum += (c*c);
25    r=r/10;
26
27    if(r==0) {
28      break;
29    }
30  }
31
32  return sum;
33}
34
35int dump_set(std::vector<int> &s) {
36  int i=1;
37  int vec_size = s.size();
38  std::vector<int>::iterator it=s.begin();
39  while(it!=s.end()) {
40    if(i==vec_size) {
41      cout << *it;
42    }
43    else {
44      cout << *it << " > ";
45    }
46    i++;
47    it++;
48  }
49
50  cout << endl;
51
52  return 0;
53}
54
55bool existing_element(std::vector<int> &s, int ele) {
56  int i=0;
57  std::vector<int>::iterator it=s.begin();
58  while(it!=s.end()) {
59    if((*it)==ele) {
60      return true;
61    }
62    it++;
63  }
64  return false;
65}
66
67int is_happy(int n) {
68  int h;
69  std::vector<int> s;
70
71  s.push_back(n);
72  h=n;
73  while(1) {
74    h=happy_next(h);
75    if(!existing_element(s, h)) {
76      s.push_back(h);
77
78      // 没有找到
79      if(h==1) {
80        dump_set(s);
81        return true;
82      }
83    }
84    else {
85      s.push_back(h);
86      dump_set(s);
87      return false;  // 出现了循环,那么一定不是开心数
88    }
89  }
90}
91
92int show_(int n) {
93  bool b;
94  b=is_happy(n);
95  if(b) {
96    std::cout << n << " is a happy number\n";
97  }
98  else {
99    std::cout << n << " isn't a happy number\n";
100  }
101
102  return 0;
103}
104
105int main(int argc, char* argv[]) {
106  int d;
107
108  if(argc==1) {
109    std::cout << "Usage: " << argv[0] << "  输入的数" << std::endl;
110    return -1;
111  }
112
113  d=atoi(argv[1]);
114  show_(d);
115
116  return 0;
117}
118
/* 让我们定义正整数S0中每个数字的平方和为S1。
 * 以相同的方法我们定义S1中 每个数字的平方和为S2,并依此类推。
 * 假如有某个Si = 1( i >= 1)则我们说S0是一个Happy number。
 * 如果某一个数不是Happy number,那他就是一个 Unhappy number。
 * 例如: 7 是一个 Happy number,
 * 因为 7 -> 49 -> 97 ->130 -> 10 -> 1。
 * 但是 4 是一个Unhappy number,
 * 因为 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4,永远也无法产生 1。
 */

#include <stdlib.h>
#include <iostream>
#include <vector>

using namespace std;

int happy_next(int n) {
  int sum=0;
  int c, r;

  r=n;
  while(1) {
    c=r%10;
    sum += (c*c);
    r=r/10;

    if(r==0) {
      break;
    }
  }

  return sum;
}

int dump_set(std::vector<int> &s) {
  int i=1;
  int vec_size = s.size();
  std::vector<int>::iterator it=s.begin();
  while(it!=s.end()) {
    if(i==vec_size) {
      cout << *it;
    }
    else {
      cout << *it << " > ";
    }
    i++;
    it++;
  }

  cout << endl;

  return 0;
}

bool existing_element(std::vector<int> &s, int ele) {
  int i=0;
  std::vector<int>::iterator it=s.begin();
  while(it!=s.end()) {
    if((*it)==ele) {
      return true;
    }
    it++;
  }
  return false;
}

int is_happy(int n) {
  int h;
  std::vector<int> s;

  s.push_back(n);
  h=n;
  while(1) {
    h=happy_next(h);
    if(!existing_element(s, h)) {
      s.push_back(h);

      // 没有找到
      if(h==1) {
        dump_set(s);
        return true;
      }
    }
    else {
      s.push_back(h);
      dump_set(s);
      return false;  // 出现了循环,那么一定不是开心数
    }
  }
}

int show_(int n) {
  bool b;
  b=is_happy(n);
  if(b) {
    std::cout << n << " is a happy number\n";
  }
  else {
    std::cout << n << " isn't a happy number\n";
  }

  return 0;
}

int main(int argc, char* argv[]) {
  int d;

  if(argc==1) {
    std::cout << "Usage: " << argv[0] << "  输入的数" << std::endl;
    return -1;
  }

  d=atoi(argv[1]);
  show_(d);

  return 0;
}


运行结果:
$ ./a.exe 9
9 > 81 > 65 > 61 > 37 > 58 > 89 > 145 > 42 > 20 > 4 > 16 > 37
9 isn't a happy number
$ ./a.exe 7
7 > 49 > 97 > 130 > 10 > 1
7 is a happy number
4 > 16 > 37 > 58 > 89 > 145 > 42 > 20 > 4
4 isn't a happy number

n阶阶乘

编写用C语言实现的求n阶阶乘问题的递归算法

递归方法实现


1#include <stdio.h>
2
3unsigned long int fact(unsigned int n) {
4  if(n==0||n==1) {
5    return 1;
6  }
7  else {
8    return n*fact(n-1);
9  }
10}
11
12int main() {
13  unsigned int i;
14  for(i=1; i<8; i++) {
15  printf("fact(%u)=%u\n", i, fact(i));
16  }
17  return 0;
18}
#include <stdio.h>



unsigned long int fact(unsigned int n) {

  if(n==0||n==1) {

    return 1;

  }

  else {

    return n*fact(n-1);

  }

}



int main() {

  unsigned int i;

  for(i=1; i<8; i++) {

	printf("fact(%u)=%u\n", i, fact(i));

  }

  return 0;

}

非递归方法实现


1#include <stdio.h>
2
3unsigned long int fact(unsigned int n) {
4  int i, ret;
5  if(n==0||n==1) {
6    return 1;
7  }
8  else {
9    ret = 1;
10    for(i=2; i<=n; i++) {
11      ret = ret * i; 
12    }
13    return ret;
14  }
15}
16
17int main() {
18  unsigned int i;
19  for(i=1; i<8; i++) {
20    printf("fact(%u)=%u\n", i, fact(i));
21  }
22  return 0;
23}
#include <stdio.h>



unsigned long int fact(unsigned int n) {

  int i, ret;

  if(n==0||n==1) {

    return 1;

  }

  else {

    ret = 1;

    for(i=2; i<=n; i++) {

      ret = ret * i; 

    }

    return ret;

  }

}



int main() {

  unsigned int i;

  for(i=1; i<8; i++) {

    printf("fact(%u)=%u\n", i, fact(i));

  }

  return 0;

}

运行结果

fact(1)=1
fact(2)=2
fact(3)=6
fact(4)=24
fact(5)=120
fact(6)=720
fact(7)=5040

正整数分解质因数

将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5

方法1

先求出质数列表,然后依次使用他们作为除数。

1/* 将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5
2 *
3 * 答案:
4 *
5 *
6 */
7
8#define P_NUM (100)
9
10#include <stdio.h>
11int pNo;
12int prime[P_NUM];
13
14int fill_prime() {
15  int i, j, ok;
16  int next=0;
17  prime[next++]=2;
18
19  for(i=3; i<=999; i++) {
20    ok=1;
21    for(j=0; j<next; j++) {
22      if(i%prime[j]==0) {
23        ok=0;
24        break;
25      }
26    }
27
28    if(ok) {
29      if(next<P_NUM) {
30        prime[next++]=i;
31      }
32    }
33  }
34
35  pNo=next;
36  while(next<P_NUM) {
37    prime[next++]=0;
38  }
39
40  return 0;
41}
42
43int dump_prime() {
44  int i;
45  for(i=0; i<pNo; i++) {
46    printf("%d, ", prime[i]);
47  }
48  printf("\n");
49  return 0;
50}
51
52int do_split(int d) {
53  int i, first=1;
54  while(1) {
55    for(i=0; i<pNo; i++) {
56      if(d%prime[i]==0) {
57        if(first) {
58          printf("%d", prime[i]);
59          first=0;
60        }
61        else {
62          printf("*%d", prime[i]);
63        }
64        d=d/prime[i];
65        if(d==1) {
66          printf("\n");
67          return 0;
68        }
69        else {
70          break;
71        }
72      }
73    }
74  }
75
76  return 0;
77}
78
79int main() {
80  int d;
81  fill_prime();
82  /*dump_prime();*/
83  d=90; printf("%d=", d);   do_split(d);
84  d=125; printf("%d=", d);   do_split(d);
85
86  return 0;
87}
/* 将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5

 *

 * 答案:

 *

 *

 */



#define P_NUM (100)



#include <stdio.h>

int pNo;

int prime[P_NUM];



int fill_prime() {

  int i, j, ok;

  int next=0;

  prime[next++]=2;



  for(i=3; i<=999; i++) {

    ok=1;

    for(j=0; j<next; j++) {

      if(i%prime[j]==0) {

        ok=0;

        break;

      }

    }



    if(ok) {

      if(next<P_NUM) {

        prime[next++]=i;

      }

    }

  }



  pNo=next;

  while(next<P_NUM) {

    prime[next++]=0;

  }



  return 0;

}



int dump_prime() {

  int i;

  for(i=0; i<pNo; i++) {

    printf("%d, ", prime[i]);

  }

  printf("\n");

  return 0;

}



int do_split(int d) {

  int i, first=1;

  while(1) {

    for(i=0; i<pNo; i++) {

      if(d%prime[i]==0) {

        if(first) {

          printf("%d", prime[i]);

          first=0;

        }

        else {

          printf("*%d", prime[i]);

        }

        d=d/prime[i];

        if(d==1) {

          printf("\n");

          return 0;

        }

        else {

          break;

        }

      }

    }

  }



  return 0;

}



int main() {

  int d;

  fill_prime();

  /*dump_prime();*/

  d=90; printf("%d=", d);   do_split(d);

  d=125; printf("%d=", d);   do_split(d);



  return 0;

}


方法2

对前面方法的优化,我们不用求质数,就从2到n,依次作为除数
因为如果我们使用了合数作为除数m*m的话,其必然先使用了质数m和n作为除数
这样代码可以简化

1#include <stdio.h>
2
3int main() {
4  int n,i;
5  printf("please input a number:\n");
6  scanf("%d",&n);
7  printf("%d=",n);
8  for(i=2;i<=n;i++) {
9    while(n!=i) {
10      if(n%i==0) {
11        printf("%d*",i);
12        n=n/i;
13      }
14      else {
15        break;
16      }
17    }
18  }
19  printf("%d",n);
20  return 0;
21}
#include <stdio.h>



int main() {

  int n,i;

  printf("please input a number:\n");

  scanf("%d",&n);

  printf("%d=",n);

  for(i=2;i<=n;i++) {

    while(n!=i) {

      if(n%i==0) {

        printf("%d*",i);

        n=n/i;

      }

      else {

        break;

      }

    }

  }

  printf("%d",n);

  return 0;

}


格雷码

在一组数的编码中,若任意两个相邻的代码只有一位二进制数不同,
则称这种编码为格雷码(Gray Code),
另外由于最大数与最小数之间也仅一位数不同,即“首尾相连”,因此又称循环码或反射码。

在数字系统中,常要求代码按一定顺序变化。
例如,按自然数递增计数,若采用8421码,则数0111变到1000时四位均要变化,
而在实际电路中,4位的变化不可能绝对同时发生,则计数中可能出现短暂的其它代码(1100、1111等)。
在特定情况下可能导致电路状态错误或输入错误。
使用格雷码可以避免这种错误。格雷码有多种编码形式。

格雷码(Gray Code)曾用过Grey Code、葛莱码、格莱码、戈莱码、循环码、反射二进制码、最小差错码等名字,
它们有的不对,有的易与其它名称混淆,建议不要再使用这些曾用名。

特点

格雷码属于可靠性编码,是一种错误最小化的编码方式。
因为,虽然自然二进制码可以直接由数/模转换器转换成模拟信号,
但在某些情况,例如从十进制的3转换为4时二进制码的每一位都要变,
能使数字电路产生很大的尖峰电流脉冲。
而格雷码则没有这一缺点,它在相邻位间转换时,只有一位产生变化。
它大大地减少了由一个状态到下一个状态时逻辑的混淆。
由于这种编码相邻的两个码组之间只有一位不同,
因而在用于方向的转角位移量-数字量的转换中,
当方向的转角位移量发生微小变化
(而可能引起数字量发生变化时,格雷码仅改变一位,这样与其它编码同时改变两位或多位的情况相比更为可靠,
即可减少出错的可能性。

格雷码是一种绝对编码方式,
典型格雷码是一种具有反射特性和循环特性的单步自补码,
它的循环、单步特性消除了随机取数时出现重大误差的可能,它的反射、自补特性使得求反非常方便。

由于格雷码是一种变权码,
每一位码没有固定的大小,
很难直接进行比较大小和算术运算,
也不能直接转换成液位信号,要经过一次码变换,变成自然二进制码,再由上位机读取。

典型格雷码是一种采用绝对编码方式的准权码,其权的绝对值为2^i-1(设最低位i=1)。

格雷码的十进制数奇偶性与其码字中1的个数的奇偶性相同。

常用的编码

2位格雷码

00 -> 01 -> 11 -> 10

3位格雷码

000 -> 001 -> 011 -> 010 -> 110 -> 111 -> 101 -> 100

4位格雷码

0000 -> 0001 -> 0011 -> 0010 -> 0110 -> 0111 -> 0101 -> 0100 ->
1100 -> 1101 -> 1111 -> 1110 -> 1010 -> 1011 -> 1001 -> 1000

转换方法

递归生成码表

这种方法基于格雷码是反射码的事实,利用递归的如下规则来构造:
  1. 1位格雷码有两个码字
  2. (n+1)位格雷码中的前2n个码字等于n位格雷码的码字,按顺序书写,加前缀0
  3. (n+1)位格雷码中的后2n个码字等于n位格雷码的码字,按逆序书写,加前缀1

异或转换

二进制码->格雷码(编码)
此方法从对应的n位二进制码字中直接得到n位格雷码码字,步骤如下:
对n位二进制的码字,从右到左,以0到n-1编号
如果二进制码字的第i位和i+1位相同,则对应的格雷码的第i位为0,否则为1, 也就是做异或操作
(当i+1=n时,二进制码字的第n位被认为是0,即第n-1位不变)

例如:二进制码0101,为4位数,所以其所转为之格雷码也必为4位数,
因此可取转成之二进位码第五位为0,即0 b3 b2 b1 b0。
0 xor 0=0,所以g3=0
0 xor 1=1,所以g2=1
1 xor 0=1,所以g1=1
0 xor 1=1,所以g0=1
因此所转换为之格雷码为0111

格雷码->二进制码(解码):
从左边第二位起,将每位与左边一位解码后的值异或,作为该位解码后的值(最左边一位依然不变)。
依次异或,直到最低位。
依次异或转换后的值(二进制数)就是格雷码转换后二进制码的值。
公式表示:(G:格雷码,B:二进制码)
B[n+1]=0, B[i]=G[i] xor B[i+1]
也就是比最高位还高一位的为0,其他按照第二个公式求值。
如果采集器器采到了格雷码:1010
就要将它变为自然二进制:
0 与第四位 1 进行异或结果为 1
上面结果1与第三位0异或结果为 1
上面结果1与第二位1异或结果为 0
上面结果0与第一位0异或结果为 0
因此最终结果为1100 这就是二进制码即十进制 12

应用

角度传感器

机械工具,汽车制动系统有时需要传感器产生的数字值来指示机械位置。
如图是编码盘和一些触点的概念图,根据盘转的位置,触点产生一个3位二进制编码,共有8个这样的编码。
盘中暗的区域与对应的逻辑1的信号源相连;亮的区域没有连接,触点将其解释为逻辑0。
使用格雷码对编码盘上的亮暗区域编码,使得其连续的码字之间只有一个数位变化。
这样就不会因为器件制造的精确度有限,而使得触点转到边界位置而出现错误编码。

九连环问题

智力玩具九连环的状态 变化符合格雷码的编码规律,汉诺塔的解法也与格雷码有关。
九连环中的每个环都有上下两种状态,如果把这两种状态用0/1来表示的话,
这个状态序列就会形成一种循环二进制编码(格雷码)的序列。
所以解决九连环问题所需要的状态变化数就是格雷码111111111所对应的十进制数341。

程序实现

数学公式

如果给定了一个B[n],可以通过前面的方法来得到对应的G[n]。
G = B ^ (B>>1)

1// 其对输入的整数输出对于的格雷码
2unsigned int binary_to_gray(unsigned int n) {
3  return n ^ (n >> 1);
4}
5
6// 输出位数为n的格雷码序列
7vector<int> grayCode(int n) {
8  vector<int> result;
9  const size_t size = 1 << n; // 2^n
10  result.reserve(size);   // 保留空间
11  for (size_t i = 0; i < size; ++i) {
12    result.push_back(binary_to_gray(i));
13  }
14  return result;
15}
// 其对输入的整数输出对于的格雷码

unsigned int binary_to_gray(unsigned int n) {

  return n ^ (n >> 1);

}



// 输出位数为n的格雷码序列

vector<int> grayCode(int n) {

  vector<int> result;

  const size_t size = 1 << n; // 2^n

  result.reserve(size);   // 保留空间

  for (size_t i = 0; i < size; ++i) {

    result.push_back(binary_to_gray(i));

  }

  return result;

}


递归方法

不用乘法求数的倍数

不用乘法或加法增加8倍。现在用同样的方法增加7倍。
左移3位表示增加8倍。

实现1


1#include <stdio.h>
2 
3unsigned int multiple(unsigned int a, unsigned  int b) {
4    unsigned int c = 0x1;
5    int i;
6    unsigned int r = 0;
7    unsigned int a1 = a;
8    
9    printf("  %d X %d = ", a, b);
10    
11    for(i=0; i<31; i++) {
12        if((b & c) != 0x0) {
13            r = r + a1;
14        }
15        
16        c = c<<1;
17        a1 = a1<<1;
18    }
19    
20    printf("%d \n", r);
21    return r;    
22}
23
24int main() {
25    multiple(3, 6);
26    multiple(13, 6);
27    multiple(13, 27);
28    return 0;
29}
#include <stdio.h>

 

unsigned int multiple(unsigned int a, unsigned  int b) {

    unsigned int c = 0x1;

    int i;

    unsigned int r = 0;

    unsigned int a1 = a;

    

    printf("  %d X %d = ", a, b);

    

    for(i=0; i<31; i++) {

        if((b & c) != 0x0) {

            r = r + a1;

        }

        

        c = c<<1;

        a1 = a1<<1;

    }

    

    printf("%d \n", r);

    return r;    

}



int main() {

    multiple(3, 6);

    multiple(13, 6);

    multiple(13, 27);

    return 0;

}

D:\httpHome\docs\funcode-c\code\num>gcc mulNomulDemo1.c
D:\httpHome\docs\funcode-c\code\num>a.exe
  3 X 6 = 18
  13 X 6 = 78
  13 X 27 = 351

实现2


1#include <stdio.h>
2 
3unsigned int multiple(unsigned int a, unsigned  int b) {
4    int i;
5    unsigned int r = 0;
6    unsigned int a1 = a;
7    
8    printf("  %d X %d = ", a, b);
9    if(b==0 || a==0) {
10        r = 0;
11    }
12    else {
13        while(b!=0x0) {
14            if((b & 0x1) != 0x0) {
15                r = r + a1;
16            }
17            
18            a1 = a1<<1;
19            b = b>>1;
20        }
21    }
22
23    printf("%d \n", r);
24    return r;    
25}
26
27int main() {
28    multiple(3, 6);
29    multiple(13, 6);
30    multiple(13, 27);
31    return 0;
32}
#include <stdio.h>

 

unsigned int multiple(unsigned int a, unsigned  int b) {

    int i;

    unsigned int r = 0;

    unsigned int a1 = a;

    

    printf("  %d X %d = ", a, b);

    if(b==0 || a==0) {

        r = 0;

    }

    else {

        while(b!=0x0) {

            if((b & 0x1) != 0x0) {

                r = r + a1;

            }

            

            a1 = a1<<1;

            b = b>>1;

        }

    }



    printf("%d \n", r);

    return r;    

}



int main() {

    multiple(3, 6);

    multiple(13, 6);

    multiple(13, 27);

    return 0;

}

D:\httpHome\docs\funcode-c\code\num>gcc mulNomulDemo2.c
D:\httpHome\docs\funcode-c\code\num>a.exe
  3 X 6 = 18
  13 X 6 = 78
  13 X 27 = 351

乘方

方法1

求pow(double a, int b)
如果最简单的方式就是循环b次得到积
但是可以将乘法的数量减少,
比如如果我们知道了p=pow(a, b)的值,那么pow(a, 2b)=p*p

1#include<stdio.h>
2#include<math.h>
3
4double pow1(double x, int n) {
5    if(0 == n)  return 1;
6    if(0 == x)  return 0;
7    int sign = 1;
8    if(n < 0){
9        sign = -1;
10        n = abs(n);
11    }
12    double temp = x;
13    double result = 1.0;
14    while(n > 0){
15        if(n&1 == 1) {
16            result *= temp;
17    }
18        temp *= temp;   // 平方
19        n >>= 1;
20    }
21    return -1 == sign? 1/result: result;
22}
23
24int check_pow(double x, int n) {
25    double r1, r2;
26    r1 = pow1(x, n);
27    
28    // double pow(double x, double y);
29    r2 = pow(x, (double)n);
30    
31    printf("  Standard pow(%f, %d)= %f\n", x, n, r2);
32    printf("  My pow(%f, %d)= %f \n\n", x, n, r1);
33    
34    return 0;
35}
36
37int main() {
38    check_pow(2.0, 5);
39    check_pow(2.7, 11);
40}
#include<stdio.h>

#include<math.h>



double pow1(double x, int n) {

    if(0 == n)  return 1;

    if(0 == x)  return 0;

    int sign = 1;

    if(n < 0){

        sign = -1;

        n = abs(n);

    }

    double temp = x;

    double result = 1.0;

    while(n > 0){

        if(n&1 == 1) {

            result *= temp;

		}

        temp *= temp;   // 平方

        n >>= 1;

    }

    return -1 == sign? 1/result: result;

}



int check_pow(double x, int n) {

    double r1, r2;

    r1 = pow1(x, n);

    

    // double pow(double x, double y);

    r2 = pow(x, (double)n);

    

    printf("  Standard pow(%f, %d)= %f\n", x, n, r2);

    printf("  My pow(%f, %d)= %f \n\n", x, n, r1);

    

    return 0;

}



int main() {

    check_pow(2.0, 5);

    check_pow(2.7, 11);

}

D:\httpHome\docs\funcode-c\code\num>gcc powDemo1.c
D:\httpHome\docs\funcode-c\code\num>a.exe
  Standard pow(2.000000, 5)= 32.000000
  My pow(2.000000, 5)= 32.000000

  Standard pow(2.700000, 11)= 55590.605666
  My pow(2.700000, 11)= 55590.605666

方法2

使用递归的方法来解决

1#include<stdio.h>
2#include<math.h>
3
4double power1(double x, int n) {
5    if (n == 0) {  // =0就直接返回
6        return 1;
7    }
8    
9    double v = power1(x, n / 2); // 一半
10    if (n % 2 == 0) {
11        return v * v;
12    }
13    else {
14        return v * v * x;
15    }
16}
17
18double pow1(double x, int n) {
19    if (n < 0)  {
20        return 1.0 / pow1(x, -n);  // 如果n为负数,求倒数
21    }
22    else {
23        return power1(x, n);
24    }
25}
26
27int check_pow(double x, int n) {
28    double r1, r2;
29    r1 = pow1(x, n);
30    
31    // double pow(double x, double y);
32    r2 = pow(x, (double)n);
33    
34    printf("  Standard pow(%f, %d)= %f\n", x, n, r2);
35    printf("  My pow(%f, %d)= %f \n\n", x, n, r1);
36    
37    return 0;
38}
39
40int main() {
41    check_pow(2.0, 5);
42    check_pow(2.7, 11);
43}
#include<stdio.h>

#include<math.h>



double power1(double x, int n) {

    if (n == 0) {  // =0就直接返回

        return 1;

    }

    

    double v = power1(x, n / 2); // 一半

    if (n % 2 == 0) {

        return v * v;

    }

    else {

        return v * v * x;

    }

}



double pow1(double x, int n) {

    if (n < 0)  {

        return 1.0 / pow1(x, -n);  // 如果n为负数,求倒数

    }

    else {

        return power1(x, n);

    }

}



int check_pow(double x, int n) {

    double r1, r2;

    r1 = pow1(x, n);

    

    // double pow(double x, double y);

    r2 = pow(x, (double)n);

    

    printf("  Standard pow(%f, %d)= %f\n", x, n, r2);

    printf("  My pow(%f, %d)= %f \n\n", x, n, r1);

    

    return 0;

}



int main() {

    check_pow(2.0, 5);

    check_pow(2.7, 11);

}

D:\httpHome\docs\funcode-c\code\num>gcc powDemo2.c
D:\httpHome\docs\funcode-c\code\num>a.exe
  Standard pow(2.000000, 5)= 32.000000
  My pow(2.000000, 5)= 32.000000

  Standard pow(2.700000, 11)= 55590.605666
  My pow(2.700000, 11)= 55590.605666

求平方根

平方根,又叫二次方根,表示为〔±√ ̄〕,
其中属于非负数的平方根称之为算术平方根(arithmetic square root)。
一个正数有两个实平方根,它们互为相反数;
0只有一个平方根,就是0本身;
负数有两个共轭的纯虚平方根。

牛顿迭代法

比如136161这个数字,首先我们找到一个和136161的平方根比较接近的数,任选一个,
比方说300到400间的任何一个数,这里选350,作为代表。
我们先计算0.5(350+136161/350),结果为369.5。
然后我们再计算0.5(369.5+136161/369.5)得到369.0003,我们发现369.5和369.0003相差无几,
并且369²末尾数字为1。我们有理由断定369²=136161。
一般来说,能够开方开的尽的,用上述方法算一两次基本结果就出来了。

牛顿迭代法(Newton's method)又称为牛顿-拉夫逊方法(Newton-Raphson method),
它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。
多数方程不存在求根公式,因此求精确根非常困难,甚至不可能,
从而寻找方程的近似根就显得特别重要。
方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。
牛顿迭代法是求方程根的重要方法之一,其最大优点是在方程f(x) = 0的单根附近具有平方收敛,
而且该法还可以用来求方程的重根、复根。
另外该方法广泛用于计算机编程中。

设r是f(x) = 0的根,选取x0作为r初始近似值,过点(x0,f(x0))做曲线y = f(x)的切线L,
L的方程为y = f(x0)+f'(x0)(x-x0),求出L与x轴交点的横坐标 x1 = x0-f(x0)/f'(x0),称x1为r的一次近似值。

过点(x1,f(x1))做曲线y = f(x)的切线,
并求该切线与x轴交点的横坐标 x2 = x1-f(x1)/f'(x1),称x2为r的二次近似值。
重复以上过程,得r的近似值序列,其中x(n+1)=x(n)-f(x(n))/f'(x(n)),称为r的n+1次近似值,上式称为牛顿迭代公式。

根据牛顿迭代的原理,可以得到以下的迭代公式:X(n+1)=[X(n)+p/Xn]/2

可以这么来理解0.5(350+136161/350)的由来
其是两个值的平均值,一个是预估值g,一个是x/g
如果x>1,那么平方数肯定比x/g小,而且大于g
如果1>x,那么平方数肯定比x/g大,而且小于g
所以平方根一定在g和x/g之间

1/* 迭代法求一个数的平方根 */
2
3/*控制解的精度*/
4#define Epsilon 1.0E-6
5
6#include <stdio.h>
7#include <math.h>
8#include <stdlib.h>
9
10// 求a的平方根
11float sqrt_demo(float a) {
12    float x0, x1;
13
14    x0 = a / 2.0;     // x0最初是等于a/2
15    x1 = (x0+a/x0) / 2.0;
16
17    while(fabs(x1-x0) >= Epsilon) {
18        x0=x1;
19        x1=(x0+a/x0) / 2;
20    }
21
22    return x1;
23}
24
25int main(int argc, char* argv[]) {
26  float a=0.0f, ret;
27  if(argc==1) {
28    printf("  Please Input >>> ");
29    scanf("%f", &a);
30  }
31  else {
32    a=atof(argv[1]);
33  }
34  
35  ret=sqrt_demo(a);
36  printf("    sqrt(%f) = [%f]\n", a, ret);
37}
/* 迭代法求一个数的平方根 */



/*控制解的精度*/

#define Epsilon 1.0E-6



#include <stdio.h>

#include <math.h>

#include <stdlib.h>



// 求a的平方根

float sqrt_demo(float a) {

    float x0, x1;



    x0 = a / 2.0;     // x0最初是等于a/2

    x1 = (x0+a/x0) / 2.0;



    while(fabs(x1-x0) >= Epsilon) {

        x0=x1;

        x1=(x0+a/x0) / 2;

    }



    return x1;

}



int main(int argc, char* argv[]) {

  float a=0.0f, ret;

  if(argc==1) {

    printf("  Please Input >>> ");

    scanf("%f", &a);

  }

  else {

    a=atof(argv[1]);

  }

  

  ret=sqrt_demo(a);

  printf("    sqrt(%f) = [%f]\n", a, ret);

}

D:\httpHome\docs\funcode-c\code\num>gcc sqrtCode.c -lm
D:\httpHome\docs\funcode-c\code\num>a.exe
  Please Input >>> 2
    sqrt(2.000000) = [1.414214]

二分查找法


1/* 迭代法求一个数的平方根 */
2
3/*控制解的精度*/
4#define Epsilon 1.0E-6
5
6#include <stdio.h>
7#include <math.h>
8//#include <stdlib.h>
9
10// 求a的平方根
11float sqrt_demo(float a) {
12    float x0, x1, mid;
13    x0 = 0;
14    x1 = a;
15
16    while(fabs(x1-x0) >= Epsilon) {
17        mid = (x0+x1)/2.0;
18        if(mid*mid > a) {    // 在x0和mid之间
19            x1 = mid;
20        }
21        else {               // 在mid和x1之间
22            x0 = mid;
23        }
24    }
25
26    return x1;
27}
28
29int main(int argc, char* argv[]) {
30    float a=0.0f, ret, sret;
31    if(argc==1) {
32        printf("  Please Input >>> ");
33        scanf("%f", &a);
34    }
35    else {
36        a=atof(argv[1]);
37    }
38
39    ret  = sqrt_demo(a);
40    
41    // 标准答案
42    // float   sqrtf (float x)
43    // long   sqrtl (long double x)
44    // double   sqrt (double x)
45    sret = sqrt(a); 
46    printf("    sqrt(%f) = [%f], Expected: [%f]\n", a, ret, sret);
47}
/* 迭代法求一个数的平方根 */



/*控制解的精度*/

#define Epsilon 1.0E-6



#include <stdio.h>

#include <math.h>

//#include <stdlib.h>



// 求a的平方根

float sqrt_demo(float a) {

    float x0, x1, mid;

    x0 = 0;

    x1 = a;



    while(fabs(x1-x0) >= Epsilon) {

        mid = (x0+x1)/2.0;

        if(mid*mid > a) {    // 在x0和mid之间

            x1 = mid;

        }

        else {               // 在mid和x1之间

            x0 = mid;

        }

    }



    return x1;

}



int main(int argc, char* argv[]) {

    float a=0.0f, ret, sret;

    if(argc==1) {

        printf("  Please Input >>> ");

        scanf("%f", &a);

    }

    else {

        a=atof(argv[1]);

    }



    ret  = sqrt_demo(a);

    

    // 标准答案

    // float 	sqrtf (float x)

    // long 	sqrtl (long double x)

    // double 	sqrt (double x)

    sret = sqrt(a); 

    printf("    sqrt(%f) = [%f], Expected: [%f]\n", a, ret, sret);

}

D:\httpHome\docs\funcode-c\code\num>gcc sqrtCode2.c -lm
D:\httpHome\docs\funcode-c\code\num>a.exe
  Please Input >>> 2.0
    sqrt(2.000000) = [1.414214], Expected: [1.414214]

开平方并取倒

倒数(reciprocal / multiplicative inverse),
是指数学上设一个数x与其相乘的积为1的数,记为1/x或x,
过程为“乘法逆”,除了0以外的数都存在倒数,
分子和分母相倒并且两个乘积是1的数互为倒数,0没有倒数.
Quake III公开源码后,有人在game/code/q_math.c里发现了这样一段代码。
它的作用是将一个数开平方并取倒,
经测试这段代码比(float)(1.0/sqrt(x))快4倍,
1float Q_rsqrt( float number ) {
2    long i;
3    float x2, y;
4    const float threehalfs = 1.5F;
5    x2 = number * 0.5F;
6    y  = number;
7    i  = * ( long * ) &y;       
8    i  = 0x5f3759df - ( i >> 1 );
9    y  = * ( float * ) &i;
10    y  = y * ( threehalfs - ( x2 * y * y ) );
11    // y  = y * ( threehalfs - ( x2 * y * y ) );
12#ifndef Q3_VM
13#ifdef __linux__
14    assert( !isnan(y) );
15#endif
16#endif
17    return y;
18}
19
float Q_rsqrt( float number ) {

    long i;

    float x2, y;

    const float threehalfs = 1.5F;

    x2 = number * 0.5F;

    y  = number;

    i  = * ( long * ) &y;       

    i  = 0x5f3759df - ( i >> 1 );

    y  = * ( float * ) &i;

    y  = y * ( threehalfs - ( x2 * y * y ) );

    // y  = y * ( threehalfs - ( x2 * y * y ) );

#ifndef Q3_VM

#ifdef __linux__

    assert( !isnan(y) );

#endif

#endif

    return y;

}


D:\httpHome\docs\funcode-c\code\num>gcc sqrtReciprocal.c -lm
D:\httpHome\docs\funcode-c\code\num>a.exe
  Please Input >>> 2
    sqrt(2.000000) = [1.414214]

如果有任何问题请发邮件到 isteps@126.com


广告内容, 如果不忙, 跪求点击