费氏(Fibonacci)数列、最大公约数,最小公倍数

  • Post author:
  • Post category:其他


费式数列

说明

Fibonacci为1200年代的欧洲数学家,在他的着作中曾经提到:「若有一只免子每个月生一只小免子,一个月后小免子也开始生产。起初只有一只免子,一个月后就有两只免子,二个月后有三只免子,三个月后有五只免子(小免子投入生产)……。

如果不太理解这个例子的话,举个图就知道了,注意新生的小免子需一个月成长期才会投入生产,类似的道理也可以用于植物的生长,这就是Fibonacci数列,一般习惯称之为费氏数列,例如以下: 1、1 、2、3、5、8、13、21、34、55、89……

解法

依说明,我们可以将费氏数列定义为以下:

fn = fn-1 + fn-2 if n > 1

fn = n if n = 0,1

#include <stdio.h>
#include <stdlib.h>
#define N 20

int main(void) {
    int Fib[N+1] = {0};
    int i;
    Fib[0] = 0;
    Fib[1] = 1;
 /*
按下标理解,第一个月一只小兔子,第二个月一只大兔子,第三个月两只兔子
(一大一小)。。。
或者就对应fibonacci数列相应的数字也可以:
1、1 、2、3、5、8、13、21、34、55、89
*/

    for(i = 2; i <=N; i++)
        Fib[i] = Fib[i-1] + Fib[i-2];
    for(i = 1; i <=N; i++)
        printf("%d ", Fib[i]);
    printf("\n");
    return 0;
}

最大公因数、最小公倍数、因式分解

说明最大公因数使用辗转相除法来求,最小公倍数则由这个公式来求:

GCD * LCM = 两数乘积(最大公约数*最小公倍数)

解法最大公因数可以使用递归与非递归求解,因式分解基本上就是使用小于输入数的数值当 作除数,去除以输入数值,如果可以整除就视为因数,要比较快的解法就是求出小于该数的所 有质数,并试试看是不是可以整除,求质数的问题是另一个课题,请参考Eratosthenes 筛选求 质数。


#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int m, n, r;
    int s;
    printf("输入两数:");
    scanf("%d %d", &m, &n);
    s = m * n;
    //辗转相除法,数论的内容。
    while(n != 0) {
        r = m % n;
        m = n;
        n = r;
    }
    printf("GCD:%d\n", m);
    printf("LCM:%d\n", s/m);
    return 0;
}

//因式分解
//C(不用质数表)

#include <stdio.h>
#include <stdlib.h>
int main(void) {
    int i, n;
    printf("请输入整数:");
    scanf("%d", &n);
    printf("%d = ", n);
    //不用eratorthenes法求,直接求n的质数因子,全部相乘得到n。
    for(i = 2; i * i <= n;) {
        if(n % i == 0) {
            printf("%d * ", i);
            n /= i;
        }
        else//层层递增寻找n的质数因子。下面直接在质数表中寻找,自然会稍快一些。
            i++;
    }
    printf("%d\n", n);
    return 0;
}


//C(使用质数表)

#include <stdio.h>
#include <stdlib.h>
#define N 1000
int prime(int*); // 求质数表
void factor(int*, int); // 求factor

int main(void) {
    int ptable[N+1] = {0};
    int count, i, temp;
    count = prime(ptable);
    printf("请输入一数:");
    scanf("%d", &temp);
    factor(ptable, temp);
    printf("\n");
    return 0;
}

//注意这里的传参,参数是指针,传入数组的首地址。
int prime(int* pNum) {
    int i, j;
    int prime[N+1];
    for(i = 2; i <= N; i++)
        prime[i] = 1;
    for(i = 2; i*i <= N; i++) {
        if(prime[i] == 1) {
            for(j = 2*i; j <= N; j++) {
                if(j % i == 0)
                    prime[j] = 0;
            }
        }
    }

    for(i = 2, j = 0; i < N; i++) {
        //将质数保存在pNum里面。
        if(prime[i] == 1)
            pNum[j++] = i;
    }
    return j;
}

void factor(int* table, int num) {

    int i;
    for(i = 0; table[i] * table[i] <= num;) {
        if(num % table[i] == 0) {
            printf("%d * ", table[i]);
            num /= table[i];
        }
        else  //和上面的筛选差不多,只不过这里i++在质数表里,上面在自然数集上。
            i++;
    }
    printf("%d\n", num);
}



版权声明:本文为qq_29611345原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。