关于算法中的数学知识

编程基础 • 2024-12-31 07:17 • 阅读 37

最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。

用两个数的乘积除以最大公约数即可：

a*b/gcd(a,b)

闰年：能被400整除或能被4整除，并且不能被100整除

编程表达：if((year%400==0)||(year%4==0)&&(year%100!=0))

最大公约数：最大公因数，也称最大最大公约数，指两个或多个整数共有中最大的一个。

编程表达：辗转相除法

int measure(int x, int y) { int z = y; while(x%y!=0) { z = x%y; x = y; y = z; } return z; }

博客上的简便法：

int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }

斐波那契数列：1,1,2,3,5,8,13…这样一个数列就是斐波那契数列

观察数列可得，除了第一项和第二项，所有的数列的值都是前一项和前一项的前一项的加和，转换成函数也就是f(n) = f(n-1) + f(n-2)

编程表达：顺序求法 O(n)

int f2(int n) { if(n < 1) { return 0; }else if(n == 1 || n == 2) { return 1; } int res = 1; int pre = 1; int temp = 0; for(int i = 3; i <=n; i++) { temp = res; res = pre + res; pre = temp; } return res; }

素数：素数是指在大于1的自然数中,除了1和它本身以外,不能被其他自然数整除的数.

编程表达：①直接法

int isprime(int n){ if (n <= 3) { return n > 1;//2,3会返回1，0，1会返回0 } for(int i = 2; i < n; i++){ if (n % i == 0) { return 0; } } return 1; } 有可能会超时

②sqrt法

int IsPrime(int number ) { int i,k=0; if(number==1) return 0; else { for(i=2;i<=sqrt(number);i++) { if(number%i==0) { k=1; return 0; break; } } if(k==0) return 1; } } 因break的存在效率较高

真因数：是指一个自然数除自身以外的因数

例：6的因数有1、2、3、6，真因数则是1、2、3。

编程表达：真因数较为简单看看即可

int SumProperFactor(int x) { if(x>0){ int sum=0; for(int i=1;i<x;i++) { if(x%i==0) { sum+=i; } } return sum; } else return 0; }

回文数：

bool huiwen(int s[]) { for (int i = 0; i < 4; i++) { if (s[i] != s[7 - i]) return false; } return true; } include<stdio.h> int main() { int a,sum=0,m,x,y;//定义变量 scanf("%d%d",&x,&y);//输入要找对称日的区间 for(m=x;m<=y;m++) { a=m; while(a!=0) { sum=sum*10+a%10;//利用循环算出此数的倒序数 a/=10; } if(sum==m)//若倒序数等于正序数 { printf("%d ",m);//输出这个数 } sum=0; } printf("\n");//全部数找完后结束 return 0; }

今天的文章关于算法中的数学知识分享到此就结束了，感谢您的阅读。

关于算法中的数学知识

相关推荐