java算法思想-第六章

六——数学问题6.1.1完数（一个数恰好等于它的因子之和）#include<iostream>usingnamespacestd;#definen10intmain(){ longp[30];longi,num,count,s,c=0; for(num=2;num<=1000;num++)#include<iostream>usingnamespacestd;//#definen10intmain(){ longfaciend,num,mod,n_mod,p_mod; longi,t,n; for(i=1;i<1000000;i++) { faciend=i; mod=1; do{ mod*=10; faciend/=10; }while(faciend>0); p_mod=mod; faciend=0; n_mod=10; while(mod>0) { t=i%(mod*10); n=i%n_mod-i%(n_mod/10); t=t*n; faciend=(faciend+t)%p_mod; mod/=10; n_mod*=10; } if(i==faciend) cout<<i<<""; } return0;} { count=0; s=num; for(i=1;i<num;i++) { if(num%i==0) { p[count++]=i; s-=i; } } if(s==0) { cout<<num<<"是完数"<<endl; //cout<<1<<""; for(i=0;i<count;i++) cout<<p[i]<<""; cout<<endl; } } return0;}6.1.2亲密数：a的因子之和等于b，b的因子之和等与a，因子包括1，不包括其本身#include<iostream>usingnamespacestd;//#definen10intmain(){ intp1[100],p2[100];inti,a,b1,b2,m,count,count1,s,c=0; for(a=1;a<=3000;a++) { count=0; b1=0; for(i=1;i<a/2+1;i++) { if(a%i==0) { p1[count++]=i; b1+=i; } } count1=0; b2=0; for(i=1;i<b1/2+1;i++) { if(b1%i==0) { p2[count1++]=i; b2+=i; } } if(a==b2&&a<b1) { cout<<a<<"和"<<b1<<"是亲密数"<<endl; cout<<a<<"的因子为"; for(i=0;i<count;i++) cout<<p1[i]<<""; cout<<endl; cout<<b1<<"的因子为"; for(i=0;i<count1;i++) cout<<p2[i]<<""; cout<<endl; } } return0;}6.1.3水仙数#include<iostream>usingnamespacestd;//#definen10intmain(){inta,i,j,k,g;for(i=100;i<1000;i++){ j=i/100; k=(i%100)/10; g=(i%100)%10; if(i==j*j*j+k*k*k+g*g*g) cout<<i<<""; } return0;}6.1.4自守数：一个数的平方的尾数恰好是该数本身（这个实在是太麻烦了，能看懂，就是在这个思路太乱了，不知道这个作者是怎么写出来的）#include<iostream>usingnamespacestd;//#definen10intmain(){ longfaciend,num,mod,n_mod,p_mod; longi,t,n; for(i=1;i<1000000;i++) { faciend=i; mod=1; do{ mod*=10; faciend/=10; }while(faciend>0); p_mod=mod; faciend=0; n_mod=10; while(mod>0) { t=i%(mod*10); n=i%n_mod-i%(n_mod/10); t=t*n; faciend=(faciend+t)%p_mod; mod/=10; n_mod*=10; } if(i==faciend) cout<<i<<""; } return0;}6.1.5最大公约数和最小公倍数1.o欧几里得算法#include<iostream>usingnamespacestd;intgcd(inta,intb){ intm,n,r; m=a>=b?a:b; n=a<b?a:b; r=m%n; while(r!=0) { m=n; n=r; r=m%n; } returnn;}intlcm(inta,intb){ intt=gcd(a,b); return(a*b)/t;}intmain(void){ inta,b; cout<<"请输入两个数"; cin>>a>>b; cout<<gcd(a,b); cout<<lcm(a,b); return0;}2.stein算法(只有整数移位和加减，不需要进行除法和取模)#include<iostream>usingnamespacestd;intgcd(inta,intb){ intm,n,r; m=a>=b?a:b; n=a<b?a:b;/* if(a>b) { m=a; n=b; }if(a<b) { m=b; n=a; } */ //r=m%n;if(0==n) returnm;if(m%2==0&&n%2==0) return2*gcd(m/2,n/2);if(m%2==0) returngcd(m/2,n);if(n%2==0) returngcd(m,n/2);returngcd((m+n)/2,(m-n)/2);//如果m，n都是奇数，则调用gcd这个函数}intlcm(inta,intb){ intt=gcd(a,b); return(a*b)/t;}intmain(void){ inta,b; cout<<"请输入两个数"; cin>>a>>b; cout<<"最大公约数"<<gcd(a,b)<<endl; cout<<"最小公倍数"<<lcm(a,b)<<endl; return0;}6.2求素数#include<iostream>usingnamespacestd;intprime(inti){ intj,flag=1; for(j=2;j*j<i;j++) { if(i%j==0) { flag=0; break; } } returnflag;}intmain(void){ inti,j,c=0; inta[1000]; for(i=2;i<=1000;i++) a[i]=1; for(i=3;i<=1000;i++) a[i]=prime(i); for(i=2;i<1000;i++) { if(a[i]==1) { cout<<i<<""; c++; if(c%10==0) cout<<endl; } }return0;}用筛选法求素数（删去合数）#include<iostream>usingnamespacestd;intmain(void){ inti,j,c=0; inta[1000]; for(i=2;i<=1000;i++)//初始化 a[i]=1; for(i=2;i*i<1000;i++)//把2,3,5,7,11，，，的倍数全部筛去，也就是删去和数 { if(a[i]==1) { for(j=2*i;j<=1000;j++) { if(j%i==0) a[j]=0; } } } for(i=2;i<1000;i++)//输出素数 { if(a[i]==1) { cout<<i<<""; c++; if(c%10==0) cout<<endl; } }return0;}6.2.2回文数（一个多位数左读和右读都一样）#include<iostream>//1000以内的回文数usingnamespacestd;intprime(inti){ intj,flag=1; for(j=2;j*j<i;j++) { if(i%j==0) { flag=0; break; } } returnflag;}intmain(void){ inti,j,t,k,s,c=0; inta[1000]; for(i=2;i<=1000;i++) a[i]=1; for(i=3;i<=1000;i++) a[i]=prime(i); for(i=0;i<=9;i++) { for(j=0;j<=9;j++) { for(k=1;k<=9;k++) { s=i*100+j*10+k; t=k*100+j*10+i; if(i==0) t/=10; if(s==t) if(prime(s)==1) cout<<s<<""; } } }return0;}2.平方回文数（一个数是回文数，他的平方还是回文数）#include<iostream>//1000以内的回文数usingnamespacestd;intmain(){ ints1,high,low,s,count=0; intb[10]; for(s=10;s<1000;s++) {s1=s*s; high=0; while(s1>0) { b[high++]=s1%10; s1/=10; } low=-1;//低位指示器 while(++low<--high) { if(b[low]!=b[high]) break; } if(low>=high) cout<<++count<<""<<s<<""<<s*s<<endl; } return0;}6.2.3哥德巴赫猜想（每个不小于6的偶数都是两个素数的和）#include<iostream>//1000以内的回文数usingnamespacestd;intprime(inti){ intj,flag=1; for(j=2;j*j<i;j++) { if(i%j==0) { flag=0; break; } } returnflag;}intmain(){ intn,i,j,flag; cout<<"请输入最大范围"; cin>>n; if(n<6) { cout<<"数据输出错误"; return0; } for(i=6;i<=n;i+=2) { flag=1; for(j=2;j<=i/2;j++) { if(j%2==0||((i-j)%2==0)) continue; if(prime(j)&&prime(i-j)) { cout<<i<<""<<j<<""<<i-j<<endl; flag=0; break; } } if(1==flag) cout<<"找到一个不符合要求的偶数"<<j; } return0;}（有改进的方法，只不过是删除合数，跟之前素数的改进的方法一样）6.3阶乘6.3.1用递归计算阶乘#include<iostream>//1000以内的回文数usingnamespacestd;intfac(intn){ if(n<0) return0; if(1==n) return1; else returnn*fac(n-1);}intmain(){ intn; cout<<"请输入一个数"; cin>>n; cout<<n<<"的阶乘"<<"="<<fac(n); return0;}6.3.2大数阶乘（一个很小的数的阶乘都容易越界，所以需要将下一个数依次乘以前一个数的每一位）#include<iostream>//1000以内的回文数usingnamespacestd;voidcarry(intbit[],intpos){ inti,carry=0; for(i=0;i<=pos;i++) { bit[i]+=carry; if(bit[i]<=9) carry=0; elseif(bit[i]>9&&i<pos) { carry=bit[i]/10; bit[i]=bit[i]%10; } elseif(bit[i]>9&&i>=pos) { while(bit[i]>9) { carry=bit[i]/10; bit[i]=bit[i]%10; i++; bit[i]=carry; } } }}intmain(){ intnum,pos,digit,i,j,m,n; doublesum=0; int*fact;//保存阶乘结果的指针 cout<<"输入一个数"; cin>>num; for(i=1;i<=num;i++) sum+=log10(i);//计算阶乘结果的位数 digit=(int)sum+1;//数据长度 if(!(fact=(int*)malloc((digit+1)*sizeof(int)))) { cout<<"分配内存失败"; return0; } for(i=0;i<=digit;i++) fact[i]=0; fact[0]=1; for(i=2;i<=num;i++)//讲2-num逐个与原来的积相乘 { for(j=digit;j<=pos;j++)//查找最高位 if(fact[j]!=0) { pos=j; break; } for(j=0;j<=pos;j++) fact[j]*=i;//每一位与i相乘 carry(fact,pos);//进位处理 } for(j=digit;j>=0;j--) if(fact[j]!=0) { pos=j; break; } m=0; n=0; cout<<"输出阶乘的结果"; for(i=pos;i>=0;i--) { cout<<fact[i]; m++; if(m%5==0) cout<<""; if(40==m) { cout<<endl;