《Java基础编程题含答案》由会员分享，可在线阅读，更多相关《Java基础编程题含答案（40页珍藏版）》请在人人文库网上搜索。

1、50道JAVA基础编程练习题【程序1】题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子对数为多少？ 程序分析： 兔子的规律为数列1,1,2,3,5,8,13,21. public class Prog1public static void main(String args)int n =

false;【程序4】题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。(2)如果nk，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数n,重复执行第一步。(3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。pu

System.out.println(); 【程序10】题目：一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在 第10次落地时，共经过多少米？第10次反弹多高？import java.util.Scanne

;System.out.println(经过第+n+次反弹后，小球共经过+length+米，+第+n+次反弹高度为+h+米);【程序11】题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。public class Prog11public static

profit_sub*0.1;return prize;【程序13】题目：一个整数，它加上100后是一个完全平方数，再加上168又是一个完全平方数，请问该数是多少？程序分析：在10万以内判断，先将该数加上100后再开方，再将该数加上268后再开方，如

System.out.println(小猴子共摘了+m+桃子);【程序18】题目：两个乒乓球队进行比赛，各出三人。甲队为a,b,c三人，乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三队赛手的名单。 import java.util.ArrayList;public clas

35、t n)if(n=1) return 1;else return fact(n-1)*n;【程序23】题目：有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？

   这是最基础的背包问题，特色是：每种物品仅有一件，能够选择放或不放。函数

面对每一个物品，咱们只有选择拿与不拿两种选择，不可以选择装入物品的一部分，也不能装入同一物品屡次。spa

2)   当 v >= W[i] 时，这是背包容量能够放下第i件物品，能够选择拿仍是不拿，判断标准：拿这件物品是否能获取更大的价值。for循环

究竟拿不拿，取决于哪一种状况使价值最大，由此可获得状态转移方程：

//若是容量为j的背包放得下第i个物体
 //两种选择：放与不放第i个物体，策略：哪一个使价值最大就选用哪一种策略
 //放不下，只能选择不放第i个物体
 

 咱们最终要求的就是： F[ N ] [ V ]，表示 N件物品恰放入一个容量恰为V的背包能够得到的最大价值。
 
 

 举例分析：假设有5个物体，背包容量为10，物体的体积分别是2 2 6 5 4，物体的收益分别是6 3 5 4 6。假设要求F[1][3]，则须要求解的是：
 
 

 
 

 
 

 
 

 

 
 

 其时间复杂度已经不能再优化了，可是空间复杂度能够优化到O(V)，具体看2.4节。
 
 

2.3 如何肯定哪些物品构成最大价值？

 

 在3.1节咱们已经能够肯定每一种状态可得到的最大价值，可是并不清楚具体选择哪几样物品可以得到最大价值。
 
 

 那么，如何肯定哪几样物品可以得到最大价值呢？
 
 

 
 

 F[i][j]，它是最优值，那么若是：
 
 

 

 具体实现代码能够看3.2节。
 
 

2.4 空间复杂度优化（降维）

 

 空间复杂度能够优化为O(V)，只适用于求最大价值，可是若是要求解哪些物体构成最大价值，则不能够降维。
 
 

 
 

 

 

 考虑3.1节基本思路的具体实现，每一次都有一个主循环i = 1 .. N，每次算出来二维数组F[ i ][0 .. V]的全部值。那么，若是只用一维数组F[0 .. V]，能不能保证 第i次循环结束后F[v]中表示的就是咱们定义的状态F[i][v]呢？

 

 
 

 
 

 看上面的伪代码，其实对于外层循环的每个i值，实际上是不须要记录的。在进行第i次循环时，全部的F[0 ... V]都还未更新时，F[v]此时记录的表示前i-1个物品在背包空间为 v 时的最大价值，这样就至关于还记录着F[i-1,v]和F[i-1,v-Ci]。
 
 

 那么为什么内层循环要递减遍历？
 
 

 第i次循环时，刚开始F[0 ... V]还未更新时，F[v]此时记录的表示前i-1个物品在背包空间为 v 时的最大价值，那么如何保证F[v]在进行更新时，每一次用到的最优值都是未更新前的？ 进行逆序遍历，就能够保证更新正确。
 
 

 2000，此时max用到的F[2]是已经更新过的，因此正序遍历会形成错误的结果。
 
 

 那么为何逆序遍历就不会出错了呢？
 
 

 
 

 
 

 虽然降维有效下降了空间复杂度，可是若是题目要求算出哪些物体组成最大价值的话，仍是得用二维数组。具体可看2.3节。
 
 

 java具体实现代码在3.3小节。
 
 

2.5 扩展——改为“刚好装满背包”

 

 求最优解的背包问题中，有两种不太相同的问法：
 
 

• 有的题目要求“刚好装满背包”时的最优解
• 有的题目则没有要求必须把背包装满

 

 一种实现方法的区别仅在初始化的时候有所不一样：
 
 

• 对于第一种问法，要求刚好装满背包，那么在初始化时除了F[0]为0，其他F[1 .. V]均设为-INF，这样就能够确保最终获得的F[V]是一种刚好装满背包的最优解。
• 若是没有要求必须把背包装满，只是但愿价格尽可能大，初始化时应该将F[0 .. V]所有设为0。

• 初始化的F数组事实上就是在没有任何物体放进背包的合法状态。若是要求背包刚好装满，那么此时只有容量为0的背包能够在什么也不装且价值为0的状况下被“刚好装满”，其它容量的背包均没有合法解，属于未定义的状态，应该赋值为-INF。
• 若是背包并不是必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，因此初始时状态的值所有为0。

 

 为何取负无穷大为不合法的状态？
 
 

 由于状态选择方程中，F[v]是经过max函数取值较大的那个，因此将不合法的状态设为负无穷，则这种状态怎么样都不会被选到。
 
 

 
 

 
 

 
 

 
 

 * 使用二维数组非递归的方法求解0/1背包问题
 // N表示物体的个数，V表示背包的载重
 //用于存储每一个物体的重量，下标从1开始
 //存储每一个物体的收益，下标从1开始
 //二维数组，用来保存每种状态下的最大收益
 //对二维数组F进行初始化
 //注意边界问题，i是从1开始的，j是从0开始的
 //若是容量为j的背包放得下第i个物体
 //放不下，只能选择不放第i个物体
 //打印全部结果，咱们要求的是F[N][V]
 * 求解F[n][m]这个最优值具体选取哪几样物品能得到最大价值，但只会输出一种状况
 * 第一行是物体个数、背包总空间；
 * 第二行是每一个物体的空间；
 * 第三行是每一个物体的收益。
 //下标从1开始，表示第1个物品
 3.2 肯定哪些物品构成最大值
 
 

 在3.1的代码基础上添加如下代码：
 
 * 求解F[n][m]这个最优值具体选取哪几样物品能得到最大价值，但只会输出一种状况
 
 * 0/1背包的降维，将空间复杂度降为O(V)
 // N表示物体的个数，V表示背包的载重
 //用于存储每一个物体的重量，下标从1开始
 //存储每一个物体的收益，下标从1开始
 //降成一维数组，用来保存每种状态下的最大收益
 //对一维数组F进行初始化
 //注意边界问题，i是从1开始的
 //打印全部结果，咱们要求的是F[V]
 * 第一行是物体个数、背包总空间；
 * 第二行是每一个物体的空间；
 * 第三行是每一个物体的收益。
 //下标从1开始，表示第1个物品
 

3.4 扩展——改为“刚好装满背包”

 * 0/1背包问题变种：求刚好装满背包的最优解
 // N表示物体的个数，V表示背包的载重
 //用于存储每一个物体的重量，下标从1开始
 //存储每一个物体的收益，下标从1开始
 //降成一维数组，用来保存每种状态下的最大收益
 //注意边界问题，i是从1开始的
 //打印全部结果，咱们要求的是F[V]
 * 第一行是物体个数、背包总空间；
 * 第二行是每一个物体的空间；
 * 第三行是每一个物体的收益。
 //下标从1开始，表示第1个物品