鸿运当头,恭喜您获得 1 金币
最近还在做经典程序一百例,发现了几个数学问题的
算法,以及我以前例子,想些一个总结的文章,包括以前
的例子,就是几个数学的概念:
包括素数,和数,约数,
分解质因数,求最大公约数,最小公约数,求水仙花数,
验证哥德巴赫猜想,总结他们的共同点和所使用的方法.
他们之间使用的一个最常用的算法就是求余,看看是不
是余数为0,这个是一个重要的判断标准.
最基本的就是素数这个概念,它是一个最基础的东西,
哥德巴赫猜想,以及因数,都有赖于这个判定函数的给出
所以,要想盖大楼,最基础的砖块就是给定一个判断素数
的函数,从它的概念入手,什么叫做素数?只有1和他本身
,没有别的约数的数,所以我们可以考虑用2和它的一半
去除它,看看是否有余数,如果余数为零,那么,它就是和
数,为什么循环到它的一半就行了呢?因为到一半,得出
的结果一组,除另一半,就相当于交换了除数和被除数的
位置,除到一半,出没有除开已经一目了然,前一半没有
除开,后一半可定也不会除开,因为知识交换了除数和被
除数的位置.所以,我们就此写出判断素数的程序:
int sushu(int m)
{
int i,n=1;
for(i=2;i<=m/2;i++)
if(m%i==0)
n=0;
return(n);
}
函数的返回值不能搞反,是素数,返回1,不是,返回0
以前,我有一种写法,是不对的。
int sushu(int m)
{
int i;
for(i=2;i<=m/2;i++)
if(m%i==0)
return(0);
else
reurn(1);
}
这个写法就不对了,因为i是一个循环递加的过程,
也许当i得2的时候,初步开,返回1,但是当i得3的时
候,又返回0,这样程序会混乱的,所以,得有一个跟
踪变量,当然,变量只要跟踪,如果得0的时候,变量
的值改变,然后返回这个变量n就可以了。
它的一个应用就是哥德巴赫猜想:它的命题是一个大
偶数可以分解成两个素数之和,1不是素数,2不是素数
,从3开始吧那就,从键盘接受一个大偶数,然后,从3
开始,一直到循环到那个大偶数,判断其中的素数,判
断一个是素数,就用大偶数减素数,在判断这个差是不
是素数,如果是,输出,如果不是,进行下一轮。
main()
{
int m,i;
scanf("%d",&m);
for(i=3;i<=m;i++)
if(sushu(i)&&sushu(m-i))
printf("%d=%d+%d",m,i,m-i);
}
这个程序还没有在tc上调试呢
下面一个就是我还不太明白的地方,就是把一个数分解
成质因数相乘的形式,比如9=3*3,但是,也就是素数
相乘的形式。他的项数很多了,
他的算法分为两步,第一步就是从2开始一直到他本
身,循环去除它,看看哪一个是他的约数
第二步,如果他能够整除,就显示这个约数,然后
把商赋值回来,然后再看看还有没有该约数,如果有在
重复循环,直到和这个约束一边大,或者不能整除为止
。
main()
{
int m,i;
scanf("%d",&m);
printf("%d=",m);
for(i=2;i<=m;i++)
{
while(m!=i)
{
if(m%i==0)
printf("%d*",i);m=m/i;
else
break;
}
}
printf("%d",m);
}
我一直觉得这个分解质因数的程序能用递归来实现,可
是想起来一时间又没有头绪。