Java程序员面试宝典第15篇.pdf

第15 章 Java 编程试题 Java API 算法是任何程序的灵魂，一些开发人员认为 提供了丰富的 ，已经可以比较容 易地完成大多数的功能，因此程序员可以不用管算法了，只要熟悉API 的用法就好。这是 Java 错误的想法，事实上， 程序的执行效率大多数情况下，依然是取决于开发人员的算法。 尤其对于应届毕业生，招聘单位往往不会考察应届毕业生太多实践的东西，而是要求他们 具有敏捷的一个算法头脑。不仅一些传统的经典算法是Java 笔试或面试的重点，还有一些 开发模式也是 Java 面试考察的重点。本章将包含关于 Java 算法和开发模式一些常见面试 题，并且分析这些题目和知识点，帮助读者梳理这些方面的知识。 15.1 基础编程试题 一些简单的算法，可以通过比较少的代码表现出来。但是，通过这些代码却可以看出 求职者编程的功底和习惯。本节将集中讨论有关基础的结构化编程和数据结构算法的常见 面试题。 面试题160 打印出100 以内的素数 相信大多数读者都应该见过类似的题目，它本质上就是判断一个整数是否为素数。实 现可以多种多样，但是效率却不同。怎样实现才能达到高效率呢？本例在回答该问题的同 时，详细地讲解高效率的判断素数的算法。 【出现频率】★★★★ 【关键考点】  结构化编程基础；  编程实践能力。 【考题分析】 1 1 素数又称为质数，它的定义是：只能被 和被自己整除的整数。其中， 不是素数， 1 任何时候都不用考虑 。 素数的判断方法是比较明确的，就是拿比自己小的整数依次进行“除以”操作，若能 除尽则表示不是素数，因此很容易就想到如下的做法： for(int i=2;inum;i++){ //循环遍历 if(num % i ==0){ //取余 return false; //一旦除尽则直接返回false } } 第15 章 Java 编程试题 return true; //若一直到最后都没返回，证明它是素数 以上的做法是可以达到目的的，也比较符合素数的定义。但是，效率就很低了，进行 了很多次不必要的循环。例如，一个数字肯定不能被大于它的 1/2 的整数所整除，因此， for 改进一下 循环的条件，不必遍历那么多次，修改以后如下所示： for(int i=2;inum/2;i++){ //循环num 的二分之一次就够了 ... } 尽管以上的做法已经比较有效率了，但是还不够。对数字敏感一点人就会知道，其实 只需要小于该数字的二次根也是可以达到目的的，因为大于该数字二次根的数字也是不能 for 整除了，所以，再改进一下 循环的条件，代码如下。 for(int i=2;iMath.sprt(num);i++){ //循环到num 的二次根次就够了 ... } 注意：以上的代码中还有一个小小的问题，就是每一次循环都进行一次取二次根的操 作，这是会影响效率的。所以，应该在循环之前就把二次根的值取好。 【答案】 该编程题的思路大致如下： 1 （）完成一个判断某整数是否为素数的方法。 2 1 100 （）循环 ～ 。 3 true （）每循环一次就判断一次，返回 则打印。 以下是该题目的编程示例： package ch15; public class Prime {