JAVA经典40例算法-.pdf

JAVA 经典算法 40 例题【程序 1】题目：古典问题：有一对兔子，从出生后第3 个月起每个月都生一对兔子，小兔子长到第四个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？1.程序分析：兔子的规律为数列1,1,2,3,5,8,13,21.publicclass exp2 publicstaticvoid main(String args)int i=0;for(i=1;i=20;i+)System.out.println(f(i);publicstaticint f(int x)if(x=1|x=2)return 1;elsereturnf(x-1)+f(x-2);或publicclass exp2 publicstaticvoid main(String args)int i=0;math mymath=new math();for(i=1;i=20;i+)System.out.println(mymath.f(i);class math publicint f(int x)if(x=1|x=2)return 1;elsereturn f(x-1)+f(x-2);【程序 2】题目：判断 101-200之间有多少个素数，并输出所有素数。1.程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除，则表明此数不是素数，反之是素数。publicclass exp2 publicstaticvoid main(String args)int i=0;math mymath=new math();for(i=2;i=200;i+)if(mymath.iszhishu(i)=true)System.out.println(i);class math publicint f(int x)if(x=1|x=2)return 1;elsereturn f(x-1)+f(x-2);publicboolean iszhishu(int x)for(int i=2;i=x/2;i+)if(x%2=0)returnfalse;returntrue;【程序 3】题目：打印出所有的水仙花数，所谓水仙花数是指一个三位数，其各位数字立方和等于该数本身。例如：153 是一个水仙花数，因为 153=1的三次方 5 的三次方 3的三次方。1.程序分析：利用for 循环控制 100-999个数，每个数分解出个位，十位，百位。publicclass exp2 publicstaticvoid main(String args)int i=0;math mymath=new math();for(i=100;i=999;i+)if(mymath.shuixianhua(i)=true)System.out.println(i);class math publicint f(int x)if(x=1|x=2)return 1;elsereturn f(x-1)+f(x-2);publicboolean iszhishu(int x)for(int i=2;i=x/2;i+)if(x%2=0)returnfalse;returntrue;publicboolean shuixianhua(int x)int i=0,j=0,k=0;i=x/100;j=(x%100)/10;k=x%10;if(x=i*i*i+j*j*j+k*k*k)returntrue;elsereturnfalse;【程序 4】题目：将一个正整数分解质因数。例如：输入90,打印出 90=2*3*3*5。程序分析：对 n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。(2)如果 n k，但 n 能被 k整除，则应打印出k的值，并用 n 除以k的商,作为新的正整数你,重复执行第一步。(3)如果 n 不能被 k整除，则用 k+1 作为 k的值,重复执行第一步。publicclass exp2 public exp2()publicvoid fengjie(int n)for(int i=2;i=90分的同学用A 表示，60-89分之间的用B 表示，60 分以下的用C 表示。1.程序分析：(a b)?a:b这是条件运算符的基本例子。import javax.swing.*;publicclass ex5 publicstaticvoid main(String args)String str=;str=JOptionPane.showInputDialog(请输入 N的值（输入 exit退出）：);int N;N=0;try N=Integer.parseInt(str);catch(NumberFormatException e)e.printStackTrace();str=(N90?A:(N60?B:C);System.out.println(str);【程序 6】题目：输入两个正整数m 和 n，求其最大公约数和最小公倍数。1.程序分析：利用辗除法。最大公约数：publicclass CommonDivisor publicstaticvoid main(String args)commonDivisor(24,32);staticint commonDivisor(int M,int N)if(N0|M0)System.out.println(ERROR!);return-1;if(N=0)System.out.println(the biggest common divisor is:+M);return M;returncommonDivisor(N,M%N);最小公倍数和最大公约数：import java.util.Scanner;publicclass CandC /下面的方法是求出最大公约数publicstaticint gcd(int m,int n)while(true)if(m=m%n)=0)return n;if(n=n%m)=0)return m;publicstaticvoid main(String args)throws Exception /取得输入值/Scanner chin=new Scanner(System.in);/int a=chin.nextInt(),b=chin.nextInt();int a=23;int b=32;int c=gcd(a,b);System.out.println(最小公倍数：+a*b/c+n最大公约数：+c);【程序 7】题目：输入一行字符，分别统计出其中英文字母、空格、数字和其它字符的个数。1.程序分析：利用while 语句,条件为输入的字符不为n.import java.util.Scanner;publicclass ex7 publicstaticvoid main(String args)System.out.println(请输入字符串：);Scanner scan=new Scanner(System.in);String str=scan.next();String E1=u4e00-u9fa5;String E2=a-zA-Z;int countH=0;int countE=0;char arrChar=str.toCharArray();String arrStr=new StringarrChar.length;for(int i=0;iarrChar.length;i+)arrStri=String.valueOf(arrChari);for(String i:arrStr)if(i.matches(E1)countH+;if(i.matches(E2)countE+;System.out.println(汉字的个数 +countH);System.out.println(字母的个数 +countE);【程序 8】题目：求 s=a+aa+aaa+aaaa+aa.a的值，其中 a 是一个数字。例如2+22+222+2222+22222(此时共有 5 个数相加)，几个数相加有键盘控制。1.程序分析：关键是计算出每一项的值。import java.io.*;publicclass Sumloop publicstaticvoid main(String args)throws IOException int s=0;String output=;BufferedReader stadin=new BufferedReader(new InputStreamReader(System.in);System.out.println(请输入 a的值 );String input=stadin.readLine();for(int i=1;i=Integer.parseInt(input);i+)output+=input;int a=Integer.parseInt(output);s+=a;System.out.println(s);另解:import java.io.*;publicclass Sumloop publicstaticvoid main(String args)throws IOException int s=0;int n;int t=0;BufferedReader stadin=new BufferedReader(new InputStreamReader(System.in);String input=stadin.readLine();n=Integer.parseInt(input);for(int i=1;i=n;i+)t=t*10+n;s=s+t;System.out.println(t);System.out.println(s);【程序 9】题目：一个数如果恰好等于它的因子之和，这个数就称为完数。例如 6=1 2 3.编程找出 1000以内的所有完数。publicclass Wanshu publicstaticvoid main(String args)int s;for(int i=1;i=1000;i+)s=0;for(int j=1;ji;j+)if(i%j=0)s=s+j;if(s=i)System.out.print(i+);System.out.println();【程序 10】题目：一球从100 米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在第 10 次落地时，共经过多少米？第10次反弹多高？publicclass Ex10 publicstaticvoid main(String args)double s=0;double t=100;for(int i=1;i=10;i+)s+=t;t=t/2;System.out.println(s);System.out.println(t);【程序 11】题目：有 1、2、3、4 个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。publicclass Wanshu publicstaticvoid main(String args)int i=0;int j=0;int k=0;int t=0;for(i=1;i=4;i+)f or(j=1;j=4;j+)for(k=1;k=4;k+)if(i!=j&j!=k&i!=k)t+=1;System.out.println(i*100+j*10+k);System.out.println(t);【程序 12】题目：企业发放的奖金根据利润提成。利润(I)低于或等于10 万元时，奖金可提10%；利润高于10 万元，低于20 万元时，低于 10 万元的部分按10%提成，高于10 万元的部分，可可提成7.5%；20 万到 40 万之间时，高于20 万元的部分，可提成5%；40 万到 60万之间时高于40 万元的部分，可提成3%；60 万到 100 万之间时，高于60 万元的部分，可提成1.5%，高于 100 万元时，超过100 万元的部分按 1%提成，从键盘输入当月利润I，求应发放奖金总数？1.程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。import java.util.*;publicclass test publicstaticvoid main(Stringargs)double sum;/声明要储存的变量应发的奖金Scanner input=new Scanner(System.in);/导入扫描器System.out.print(输入当月利润 );double lirun=input.nextDouble();/从控制台录入利润if(lirun=100000)sum=lirun*0.1;elseif(lirun=200000)sum=10000+lirun*0.075;elseif(lirun=400000)sum=17500+lirun*0.05;elseif(lirun=600000)sum=lirun*0.03;elseif(lirun=1000000)sum=lirun*0.015;else sum=lirun*0.01;System.out.println(应发的奖金是+sum);后面其他情况的代码可以由读者自行完善.【程序 13】题目：一个整数，它加上100后是一个完全平方数，加上168 又是一个完全平方数，请问该数是多少？1.程序分析：在10 万以内判断，先将该数加上100 后再开方，再将该数加上268 后再开方，如果开方后的结果满足如下条件，即是结果。请看具体分析：publicclass test publicstaticvoid main(Stringargs)long k=0;for(k=1;k2)/*如果是闰年且月份大于2,总天数应该加一天*/sum+;System.out.println(It is the the day:+sum);【程序 15】题目：输入三个整数x,y,z，请把这三个数由小到大输出。1.程序分析：我们想办法把最小的数放到x 上，先将 x 与 y 进行比较，如果x y 则将 x 与 y 的值进行交换，然后再用x 与 z 进行比较，如果x z则将 x 与 z 的值进行交换，这样能使x 最小。import java.util.*;publicclass test publicstaticvoid main(Stringargs)int i=0;int j=0;int k=0;int x=0;System.out.print(请输入三个数n);Scanner input=new Scanner(System.in);i=input.nextInt();j=input.nextInt();k=input.nextInt();if(ij)x=i;i=j;j=x;if(ik)x=i;i=k;k=x;if(jk)x=j;j=k;k=x;System.out.println(i+,+j+,+k);【程序 16】题目：输出9*9口诀。1.程序分析：分行与列考虑，共9 行 9 列，i 控制行，j 控制列。publicclass jiujiu publicstaticvoid main(String args)int i=0;int j=0;for(i=1;i=9;i+)for(j=1;j=9;j+)System.out.print(i+*+j+=+i*j+t);System.out.println();不出现重复的乘积(下三角)publicclass jiujiu publicstaticvoid main(String args)int i=0;int j=0;for(i=1;i=9;i+)for(j=1;j=i;j+)System.out.print(i+*+j+=+i*j+t);System.out.println();上三角publicclass jiujiu publicstaticvoid main(String args)int i=0;int j=0;for(i=1;i=9;i+)for(j=i;j=9;j+)System.out.print(i+*+j+=+i*j+t);System.out.println();【程序 17】题目：猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第 10 天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。1.程序分析：采取逆向思维的方法，从后往前推断。publicclass猴子吃桃 staticint total(int day)if(day=10)return 1;else return(total(day+1)+1)*2;publicstaticvoid main(String args)System.out.println(total(1);【程序 18】题目：两个乒乓球队进行比赛，各出三人。甲队为a,b,c三人，乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a 说他不和 x 比，c 说他不和 x,z 比，请编程序找出三队赛手的名单。1.程序分析：判断素数的方法：用一个数分别去除2 到 sqrt(这个数)，如果能被整除，则表明此数不是素数，反之是素数。import java.util.ArrayList;publicclass pingpang String a,b,c;publicstaticvoid main(String args)String op=x,y,z;ArrayList arrayList=new ArrayList();for(int i=0;i 3;i+)for(int j=0;j 3;j+)for(int k=0;k 3;k+)pingpang a=new pingpang(opi,opj,opk);if(!a.a.equals(a.b)&!a.b.equals(a.c)&!a.a.equals(x)&!a.c.equals(x)&!a.c.equals(z)arrayList.add(a);for(Object a:arrayList)System.out.println(a);public pingpang(String a,String b,String c)super();this.a=a;this.b=b;this.c =c;Overridepublic String toString()/TODO Auto-generated method stubreturna 的对手是 +a+,+b 的对手是 +b+,+c 的对手是 +c+n;【程序 19】题目：打印出如下图案（菱形）*1.程序分析：先把图形分成两部分来看待，前四行一个规律，后三行一个规律，利用双重for 循环，第一层控制行，第二层控制列。三角形：publicclass StartG publicstaticvoid main(String args)int i=0;int j=0;for(i=1;i=4;i+)for(j=1;j=1;i-)for(j=1;j=2*i-3;j+)System.out.print(*);System.out.println();菱形：publicclass StartG publicstaticvoid main(String args)int i=0;int j=0;for(i=1;i=4;i+)for(int k=1;k=4-i;k+)System.out.print();for(j=1;j=1;i-)for(int k=1;k=5-i;k+)System.out.print();for(j=1;j=2*i-3;j+)System.out.print(*);System.out.println();【程序 20】题目：有一分数序列：2/1，3/2，5/3，8/5，13/8，21/13.求出这个数列的前20 项之和。1.程序分析：请抓住分子与分母的变化规律。publicclass test20 publicstaticvoid main(String args)float fm=1f;float fz=1f;float temp;float sum=0f;for(int i=0;i20;i+)temp=fm;fm=fz;fz=fz+temp;sum+=fz/fm;/System.out.println(sum);System.out.println(sum);【程序 21】题目：求 1+2!+3!+.+20!的和1.程序分析：此程序只是把累加变成了累乘。publicclass Ex21 staticlongsum=0;staticlongfac =0;publicstaticvoid main(String args)long sum=0;long fac=1;for(int i=1;i 1)value=n*recursion(n-1);return value;【程序 23】题目：有 5 个人坐在一起，问第五个人多少岁？他说比第4 个人大 2 岁。问第 4 个人岁数，他说比第3 个人大 2 岁。问第三个人，又说比第2 人大两岁。问第2 个人，说比第一个人大两岁。最后问第一个人，他说是10 岁。请问第五个人多大？1.程序分析：利用递归的方法，递归分为回推和递推两个阶段。要想知道第五个人岁数，需知道第四人的岁数，依次类推，推到第一人（10 岁），再往回推。publicclass Ex23 staticint getAge(int n)if(n=1)return 10;return 2+getAge(n-1);publicstaticvoid main(String args)System.out.println(第五个的年龄为:+getAge(5);【程序 24】题目：给一个不多于5 位的正整数，要求：一、求它是几位数，二、逆序打印出各位数字。import java.util.Scanner;publicclass Ex24 publicstaticvoid main(String args)Ex24 tn=new Ex24();Scanner s=new Scanner(System.in);long a=s.nextLong();if(a 100000)System.out.println(Error Input,please run this program Again);System.exit(0);if(a=0&a=10&a=100&a=1000&a=10000&a=0;i-)System.out.print(chi);【程序 25】题目：一个5 位数，判断它是不是回文数。即12321是回文数，个位与万位相同，十位与千位相同。import java.util.Scanner;publicclass Ex25 staticint a=newint5;staticint b=newint5;publicstaticvoid main(String args)boolean is=false;Scanner s=new Scanner(System.in);long l=s.nextLong();if(l 99999|l=0;i-)ai=(int)(l/(long)Math.pow(10,i);l=(l%(long)Math.pow(10,i);System.out.println();for(int i=0,j=0;i5;i+,j+)bj=ai;for(int i=0,j=4;i5;i+,j-)if(ai!=bj)is=false;break;else is=true;if(is=false)System.out.println(is not a Palindrom!);elseif(is=true)System.out.println(is a Palindrom!);【程序 26】题目：请输入星期几的第一个字母来判断一下是星期几，如果第一个字母一样，则继续判断第二个字母。1.程序分析：用情况语句比较好，如果第一个字母一样，则判断用情况语句或if 语句判断第二个字母。import java.util.Scanner;publicclass Ex26 publicstaticvoid main(String args)/保存用户输入的第二个字母char weekSecond;/将Scanner类示例化为 input对象，用于接收用户输入 Scanner input=new Scanner(System.in);/开始提示并接收用户控制台输入 System.out.print(请输入星期值英文的第一个字母，我来帮您判断是星期几：);String letter=input.next();/判断用户控制台输入字符串长度是否是一个字母if(letter.length()=1)/利用取第一个索引位的字符来实现让Scanner接收 char 类型输入char weekFirst=letter.charAt(0);switch(weekFirst)casem:/当输入小写字母时，利用switch结构特性执行下一个带break语句的 case 分支，以实现忽略用户控制台输入大小写敏感的功能caseM:System.out.println(星期一(Monday);break;caset:/当输入小写字母时，利用switch结构特性执行下一个带break语句的 case 分支，以实现忽略用户控制台输入大小写敏感的功能caseT:System.out.print(由于星期二(Tuesday)与星期四(Thursday)均以字母 T开头，故需输入第二个字母才能正确判断：);letter=input.next();/判断用户控制台输入字符串长度是否是一个字母if(letter.length()=1)/利用取第一个索引位的字符来实现让Scanner接收 char类型输入 weekSecond=letter.charAt(0);/利用或（|）运算符来实现忽略用户控制台输入大小写敏感的功能if(weekSecond=U|weekSecond=u)System.out.println(星期二(Tuesday);break;/利用或（|）运算符来实现忽略用户控制台输入大小写敏感的功能 elseif(weekSecond=H|weekSecond=h)System.out.println(星期四(Thursday);break;/控制台错误提示 else System.out.println(输入错误，不能识别的星期值第二个字母，程序结束！);break;else /控制台错误提示 System.out.println(输入错误，只能输入一个字母，程序结束！);break;casew:/当输入小写字母时，利用switch结构特性执行下一个带break语句的 case 分支，以实现忽略用户控制台输入大小写敏感的功能caseW:System.out.println(星期三(Wednesday);break;casef:/当输入小写字母时，利用switch结构特性执行下一个带break语句的 case 分支，以实现忽略用户控制台输入大小写敏感的功能caseF:System.out.println(星期五(Friday);break;cases:/当输入小写字母时，利用switch结构特性执行下一个带break语句的 case 分支，以实现忽略用户控制台输入大小写敏感的功能caseS:System.out.print(由于星期六(Saturday)与星期日(Sunday)均以字母 S开头，故需输入第二个字母才能正确判断：);letter=input.next();/判断用户控制台输入字符串长度是否是一个字母if(letter.length()=1)/利用取第一个索引位的字符来实现让Scanner接收 char类型输入 weekSecond=letter.charAt(0);/利用或（|）运算符来实现忽略用户控制台输入大小写敏感的功能if(weekSecond=A|weekSecond=a)System.out.println(星期六(Saturday);break;/利用或（|）运算符来实现忽略用户控制台输入大小写敏感的功能 elseif(weekSecond=U|weekSecond=u)System.out.println(星期日(Sunday);break;/控制台错误提示 else System.out.println(输入错误，不能识别的星期值第二个字母，程序结束！);break;else/控制台错误提示 System.out.println(输入错误，只能输入一个字母，程序结束！);break;default:/控制台错误提示 System.out.println(输入错误，不能识别的星期值第一个字母，程序结束！);break;else/控制台错误提示 System.out.println(输入错误，只能输入一个字母，程序结束！);【程序 27】题目：求 100 之内的素数publicclass Ex27 publicstaticvoid main(String args)int sum,i;for(sum=2;sum=100;sum+)for(i=2;isum/2)System.out.println(sum+是素数 );【程序 28】题目：对 10 个数进行排序1.程序分析：可以利用选择法，即从后9 个比较过程中，选择一个最小的与第一个元素交换，下次类推，即用第二个元素与后8 个进行比较，并进行交换。import java.util.Arrays;import java.util.Random;import java.util.Scanner;publicclass Ex28 publicstaticvoid main(String args)int arr=newint11;Random r=new Random();for(int i=0;i10;i+)arri=r.nextInt(100)+1;/得到 10 个100 以内的整数 Arrays.sort(arr);for(int i=0;iarr.length;i+)System.out.print(arri+t);System.out.print(nPlease Input a int number:);Scanner sc=new Scanner(System.in);arr10=sc.nextInt();/输入一个 int值 Arrays.sort(arr);for(int i=0;iarr.length;i+)System.out.print(arri+t);【程序 29】题目：求一个3*3矩阵对角线元素之和1.程序分析：利用双重for 循环控制输入二维数组，再将aii累加后输出。publicclass Ex29 publicstaticvoid main(String args)double sum=0;int array=1,2,3,4,5,6,7,7,8;for(int i=0;i3;i+)for(int j=0;j3;j+)if(i=j)sum=sum+arrayij;System.out.println(sum);【程序 30】题目：有一个已经排好序的数组。现输入一个数，要求按原来的规律将它插入数组中。1.程序分析：首先判断此数是否大于最后一个数，然后再考虑插入中间的数的情况，插入后此元素之后的数，依次后移一个位置。import java.util.Random;publicclass ArraySort publicstaticvoid main(String args)int temp=0;int myarr=newint12;Random r=new Random();for(int i=1;i=10;i+)myarri=r.nextInt(1000);for(int k=1;k=10;k+)System.out.print(myarrk+,);for(int i=1;i=9;i+)for(int k=i+1;kmyarrk)temp=myarri;myarri=myarrk;myarrk=temp;System.out.println();for(int k=1;k=10;k+)System.out.print(myarrk+,);myarr11=r.nextInt(1000);for(int k=1;kmyarr11)temp=myarr11;for(int j=11;j=k+1;j-)myarrj=myarrj-1;myarrk=temp;System.out.println();for(int k=1;k=1;k-)System.out.print(myarrk+,);【程序 32】题目：取一个整数a 从右端开始的47 位。程序分析：可以这样考虑：(1)先使 a 右移 4 位。(2)设置一个低4 位全为 1,其余全为 0 的数。可用(0 4)(3)将上面二者进行&运算。publicclass Ex32 publicstaticvoid main(String args)int a=0;long b=18745678;a=(int)Math.floor(b%Math.pow(10,7)/Math.pow(10,3);System.out.println(a);【程序 33】题目：打印出杨辉三角形（要求打印出10 行如下图）1.程序分析：1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 publicclass Ex33 publicstaticvoid main(String args)int i,j;int a;a=newint88;for(i=0;i8;i+)aii=1;ai0=1;for(i=2;i8;i+)for(j=1;j=i-1;j+)aij=ai-1j-1+ai-1j;for(i=0;i8;i+)for(j=0;j=0;)for(int j=0;jarraysj+1)int temp=arraysj;arraysj=arraysj+1;arraysj+1=temp;for(int n=0;narrays.length;n+)System.out.println(arraysn);【程序 35】题目：输入数组，最大的与第一个元素交换，最小的与最后一个元素交换，输出数组。import java.util.*;publicclass Ex35 publicstaticvoid main(String args)int i,min,max,n,temp1,temp2;int a;System.out.println(输入数组的长度:);Scanner keyboard=new Scanner(System.in);n=keyboard.nextInt();a=newintn;for(i=0;i n;i+)System.out.print(输入第 +(i+1)+个数据 );ai=keyboard.nextInt();/以上是输入整个数组max=0;min=0;/设置两个标志,开始都指向第一个数for(i=1;i amax)max=i;/遍历数组,如果大于 amax，就把他的数组下标赋给maxif(ai amin)min=i;/同上，如果小于amin,就把他的数组下标赋给min /以上 for循环找到最大值和最小值，max是最大值的下标，min 是最小值