求两个或N个数的最大公约数(gcd)和最小公倍数(lcm)的较优算法

http://www.cppblog.com/linqiu/archive/2007/08/01/29145.html

[cpp] view plain copy

print ?

1. #include <iostream>  
2. #include <cmath>  
3. using namespace std;  
4.   
5. int gcd(int a, int b);  
6. int ngcd(int *a, int n);  
7. int lcm(int a, int b);  
8. int nlcm(int *a, int n);  
9.   
10. int main()  
11. {  
12.  //int a,b;  
13.  //cin >> a >> b;  
14.  //cout << lcm(a, b) << endl;  
15.  int *a = new int[3];  
16.  a[0] = 3;  
17.  a[1] = 4;  
18.  a[2] = 5;  
19.  cout << nlcm(a, 3) << endl;  
20.   
21.  return 0;  
22. }  
23.   
24. //两个数的最大公约数--欧几里得算法  
25. int gcd(int a, int b)  
26. {  
27.  if (a < b)  
28.   swap(a, b);  
29.   
30.  if (b == 0)  
31.   return a;  
32.  else  
33.   return gcd(b, a%b);  
34. }  
35.   
36. //n个数的最大公约数算法  
37. //说明:   
38. //把n个数保存为一个数组  
39. //参数为数组的指针和数组的大小(需要计算的数的个数)  
40. //然后先求出gcd(a[0],a[1]), 然后将所求的gcd与数组的下一个元素作为gcd的参数继续求gcd  
41. //这样就产生一个递归的求ngcd的算法  
42. int ngcd(int *a, int n)  
43. {  
44.  if (n == 1)  
45.   return *a;  
46.   
47.  return gcd(a[n-1], ngcd(a, n-1));  
48. }  
49.   
50. //两个数的最小公倍数(lcm)算法  
51. //lcm(a, b) = a*b/gcd(a, b)  
52. int lcm(int a, int b)  
53. {  
54.  return a*b/gcd(a, b);  
55. }  
56.   
57. //n个数的最小公倍数算法  
58. //算法过程和n个数的最大公约数求法类似  
59. //求出头两个的最小公倍数,再将欺和大三个数求最小公倍数直到数组末尾  
60. //这样产生一个递归的求nlcm的算法  
61. int nlcm(int *a, int n)  
62. {  
63.  if (n == 1)  
64.   return *a;  
65.  else  
66.   return lcm(a[n-1], nlcm(a, n-1));  
67. } 
    
68. ----------------------------------分割线-------------------------
69. 今天写一道题方法很类似，是求多个数与非
70. nand(与非)
    
71. ∙ 0 nand 0 = 1
    ∙ 0 nand 1 = 1
    ∙ 1 nand 0 = 1
    ∙ 1 nand 1 = 0
72. #include<stdio.h>
    #include<iostream>
    #include<string.h>
    #include<stdlib.h>
    #define SIZE 200010
    using namespace std;
    int nand(int a,int b){
        return !(a&&b);
    }
    int nnand(int *a,int n){
        if(n==0)
            return (*a);    
        return nand(a[n],nnand(a,n-1));
            
    }
    int main(){
        int n,a[SIZE];
        cin>>n;
        
        for(int i=0;i<=n;i++)
        cin>>a[i];
        int ans=nnand(a,n);
        cout<<ans<<endl;
        return 0;
    }