java 面试之经典算法篇

Java 经典算法

【示例 1】题目：判断 101-200 之间有多少个素数，并输出所有素数。

1.程序分析：判断素数的方法：用一个数分别去除 2 到 sqrt(这个数)，如果能被整除，

则表明此数不是素数，反之是素数。

public class exp2{ public static void 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

{ public int f(int x)

{ if(x==1 || x==2) return 1; else

return f(x-1)+f(x-2);

}public boolean iszhishu(int x)

{ for(int i=2;i<=x/2;i++) if (x % 2==0 ) return false; return true;

}

}

【示例 2】题目：古典问题：有一对兔子，从出生后第 3 个月起每个月都生一对兔子，小兔子长到第四个月后每个月又生一对兔子，假如兔子都不

死，问每个月的兔子总数为多少？

1.程序分析： 兔子的规律为数列 1,1,2,3,5,8,13,21....

public class exp2{ public static void main(String args[]){ int i=0; for(i=1;i<=20;i++)

System.out.println(f(i));

}public static int f(int x)

{ if(x==1 || x==2) return 1; else

return f(x-1)+f(x-2);

}

}

或

public class exp2{ public static void main(String args[]){ int i=0;

math mymath = new math(); for(i=1;i<=20;i++)

System.out.println(mymath.f(i));

}

}class math

{ public int f(int x)

{ if(x==1 || x==2) return 1; else

return f(x-1)+f(x-2);

}

}

【示例 3】题目：打印出所有的 "水仙花数 "，所谓 "水仙花数 "是指一个三位数，其各位数字立方和等于该数本身。例如：153 是一个 "水仙花

数 "，因为 153=1 的三次方＋5 的三次方＋3 的三次方。

1.程序分析：利用 for 循环控制 100-999 个数，每个数分解出个位，十位，百位。

public class exp2{

public static void 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

{ public int f(int x)

{ if(x==1 || x==2) return 1; else

return f(x-1)+f(x-2);

}public boolean iszhishu(int x)

{ for(int i=2;i<=x/2;i++) if (x % 2==0 ) return false; return true;

}public boolean shuixianhua(int x)

{ int i=0,j=0,k=0;

i=x / 100;

j=(x % 100) /10;

ik=fx % 10; (x==iii+jjj+kkk) return true; else

return false;

}

}

【示例 4】题目：将一个正整数分解质因数。例如：输入 90,打印出 90=233*5。

程序分析：对 n 进行分解质因数，应先找到一个最小的质数 k，然后按下述步骤完成：

(1)如果这个质数恰等于 n，则说明分解质因数的过程已经结束，打印出即可。

(2)如果 n <> k，但 n 能被 k 整除，则应打印出 k 的值，并用 n 除以 k 的商,作为新的正整数你,重复执行第一步。

(3)如果 n 不能被 k 整除，则用 k+1 作为 k 的值,重复执行第一步。

public class exp2{ public exp2(){} public void fengjie(int n){ for(int i=2;i<=n/2;i++){ if(n%i==0){

System.out.print(i+"*");

fengjie(n/i);

}

}

System.out.print(n);

System.exit(0);///不能少这句，否则结果会出错

}public static void main(String[] args){

String str="";

exp2 c=new exp2();

str=javax.swing.JOptionPane.showInputDialog("请输入 N 的值（输入 exit 退出）：");

int N;

Nt=r0y;{

N=Integer.parseInt(str);

}catch(NumberFormatException e){

e.printStackTrace();

}

System.out.print(N+"分解质因数："+N+"=");

c.fengjie(N);

}

}

【示例 5】题目：利用条件运算符的嵌套来完成此题：学习成绩> =90 分的同学用 A 表示，60-89 分之间的用 B 表示，60 分以下的用 C 表示。

1.程序分析：(a> b)?a:b 这是条件运算符的基本例子。

import javax.swing.*; public class ex5 { public static void main(String[] args){

String str="";

str=JOptionPane.showInputDialog("请输入 N 的值（输入 exit 退出）：");

int N;

Nt=r0y;{

N=Integer.parseInt(str);

ca}tch(NumberFormatException e){

e.printStackTrace();

}

str=(N>90?"A":(N>60?"B":"C"));

System.out.println(str);

}

}

【示例 6】题目：输入两个正整数 m 和 n，求其最大公约数和最小公倍数。

1.程序分析：利用辗除法。

最大公约数：

public class CommonDivisor{ public static void main(String args[])

{ commonDivisor(24,32);

}static int commonDivisor(int M, int N)

{ if(N<0||M<0)

{

Sryesttuermn.out.println("ERROR!"); -1;

}if(N==0)

{

rSeytsutrenm.out.println("the biggest common divisor is :"+M); M;

}return commonDivisor(N,M%N);

}

}

最小公倍数和最大公约数：

import java.util.Scanner; public class CandC

{

//下面的方法是求出最大公约数

public static int gcd(int m, int n)

{while (true)

{if ((m = m % n) == 0) return n; if ((n = n % m) == 0) return m;

}}

public static void main(String args[]) throws Exception

{

//取得输入值

//Scanner chin = new Scanner(System.in);

/i/ntint a = chin.nextInt(), b = chin.nextInt(); 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; public class ex7 { public static void main(String args[])

{

System.out.println("请输入字符串：");

Scanner scan=new Scanner(System.in);

String str=scan.next();

String E1="[\u4e00-\u9fa5]";

Sintrting E2="[a-zA-Z]"; countH=0; int countE=0; char[] arrChar=str.toCharArray();

String[] arrStr=new String[arrChar.length]; for (int i=0;i<arrChar.length ;i++ )

{

arrStr[i]=String.valueOf(arrChar[i]);

}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.*; public class Sumloop { public static void main(String[] args) throws IOException

{ int s=0;

String output="";

BufferedReader stadin = new BufferedReader(new InputStreamReader(System.in));

System.out.println("请输入 a 的值");

Sfotrring input =stadin.readLine(); (int i =1;i<=Integer.parseInt(input);i++)

{

ionuttput+=input; a=Integer.parseInt(output);

s+=a;

}

System.out.println(s);

}

}

另解:

import java.io.*; public class Sumloop { public static void 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();

fno=rInteger.parseInt(input); (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 以内的所有完数。

public class Wanshu { public static void main(String[] args)

{ int s; for(int i=1;i<=1000;i++)

{

fs=o0r;(int j=1;j<i;j++) if(i % j==0)

if s=s+j; (s==i)

System.out.print(i+" ");

}

System.out.println();

}

}

【示例 10】题目：一球从 100 米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在第 10 次落地时，共经过多少米？第 10 次反弹

多高？

public class Ex10 { public static void 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。组成所有的排列后再去掉不满足条件的排列。

public class Wanshu { public static void main(String[] args)

{ int i=0; int j=0; int k=0; int t=0; for(i=1;i<=4;i++) for(j=1;j<=4;j++) for(k=1;k<=4;k++) if(i!=j && j!=k && i!=k)

{t+=1;

System.out.println(i100+j10+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.*; public class test { public static void main (String[]args){

double sum;//声明要储存的变量应发的奖金

Scanner input =new Scanner (System.in);//导入扫描器

System.out.print ("输入当月利润");

double lirun=input .nextDouble();//从控制台录入利润

if(lirun<=100000){

sum=lirun*0.1;

}else if (lirun<=200000){

sum=10000+lirun*0.075;

}else if (lirun<=400000){

sum=17500+lirun*0.05;

}else if (lirun<=600000){

sum=lirun*0.03;

}else if (lirun<=1000000){

sum=lirun*0.015;

} else{

sum=lirun*0.01;

}

System.out.println("应发的奖金是"+sum);

}

}

后面其他情况的代码可以由读者自行完善.

【示例 13】

题目：一个整数，它加上 100 后是一个完全平方数，加上 168 又是一个完全平方数，请问该数是多少？

1.程序分析：在 10 万以内判断，先将该数加上 100 后再开方，再将该数加上 268 后再开方，如果开方后的结果满足如下条件，即是结果。请看具体

分析：

public class test { public static void main (String[]args){

long k=0; for(k=1;k<=100000l;k++) if(Math.floor(Math.sqrt(k+100))==Math.sqrt(k+100) &&

Math.floor(Math.sqrt(k+168))==Math.sqrt(k+168))

System.out.println(k);

}

}

【示例 14】题目：输入某年某月某日，判断这一天是这一年的第几天？

1.程序分析：以 3 月 5 日为例，应该先把前两个月的加起来，然后再加上 5 天即本年的第几天，特殊情况，闰年且输入月份大于 3 时需考虑多加一

天。

import java.util.*; public class test { public static void main (String[]args){ int day=0; int month=0; int year=0; int sum=0; int leap;

System.out.print("请输入年,月,日\n");

Scanner input = new Scanner(System.in);

year=input.nextInt();

month=input.nextInt();

day=input.nextInt();

switch(month) /先计算某月以前月份的总天数/

{case 1:

sum=0;break; case 2:

sum=31;break; case 3:

sum=59;break; case 4:

sum=90;break; case 5:

sum=120;break; case 6:

sum=151;break; case 7:

sum=181;break; case 8:

sum=212;break; case 9:

sum=243;break; case 10:

sum=273;break; case 11:

sum=304;break; case 12:

sum=334;break; default:

System.out.println("data error");break;

}

sum=sum+day; /再加上某天的天数/

if(year%400==0||(year%4==0&&year%100!=0))/判断是不是闰年/

elseleap=1;

leap=0;

if(leap==1 && month>2)/如果是闰年且月份大于 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.*; public class test { public static void main (String[]args){ 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=iifnput.nextInt(); (i>j)

{

x=i;

i=j;

j=x;

}if(i>k)

{

x=i;

i=k;

k=x;

}if(j>k)

{

x=j;

j=k;

k=x;

}

System.out.println(i+", "+j+", "+k);

}

}

【示例 16】题目：输出 9*9 口诀。

1.程序分析：分行与列考虑，共 9 行 9 列，i 控制行，j 控制列。

public class jiujiu { public static void 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+"="+ij+"\t");

System.out.println();

}

}}

不出现重复的乘积(下三角)

public class jiujiu { public static void 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+"="+ij+"\t");

System.out.println();

}

}}

上三角

public class jiujiu { public static void 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+"="+ij+"\t");

System.out.println();

}

}}

【示例 17】题目：猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个 第二天早上又将剩下的桃子吃掉一半，

又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第 10 天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。

1.程序分析：采取逆向思维的方法，从后往前推断。

public class 猴子吃桃 {

static int total(int day){ if(day == 10){ return 1;

}else{ return (total(day+1)+1)*2;

}

public s}tatic void 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; public class pingpang {

pSutbrliincg sat,abt,icc; void main(String[] args) {

String[] op = { "x", "y", "z" };

ArrayList<pingpang> arrayList=new ArrayList<pingpang>(); 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(op[i],op[j],op[k]); 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;

}

@pOubvelircride String toString() {

// TODO Auto-generated method stub

return "a 的对手是"+a+","+"b 的对手是"+b+","+"c 的对手是"+c+"\n";

}

}

【示例 19】题目：打印出如下图案（菱形）

1.程序分析：先把图形分成两部分来看待，前四行一个规律，后三行一个规律，利用双重 for 循环，第一层控制行，第二层控制列。

三角形：

public class StartG { public static void main(String [] args)

{ int i=0; int j=0; for(i=1;i<=4;i++)

{ for(j=1;j<=2*i-1;j++)

System.out.print("*");

System.out.println("");

}for(i=4;i>=1;i--)

{ for(j=1;j<=2*i-3;j++)

System.out.print("*");

System.out.println("");

}

}

}

菱形：

public class StartG { public static void 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 for .print(" "); (j=1;j<=2*i-1;j++)

System.out.print("*");

System.out.println("");

}for(i=4;i>=1;i--)

{ for(int k=1; k<=5-i;k++)

for System.out.print(" "); (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.程序分析：请抓住分子与分母的变化规律。

public class test20 { public static void main(String[] args) { float fm = 1f; float fz = 1f; float temp; float sum = 0f; for (int i=0;i<20;i++){

temp = fm;

fm = fz;

fz = fz + temp;

sum += fz/fm;

//System.out.println(sum);

}

System.out.println(sum);

}

}

资料已整理成文档，需要获取的小伙伴可以+ VX: mxk6072