费式数列
说明
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 版权协议,转载请附上原文出处链接和本声明。