课堂作业(模块1：Java编程逻辑)

1、.课堂作业模块1 Java编程逻辑【第1课】【作业1】编写一个Java程序，在控制台上输出如下两行信息：Hello，World！Hello，Java！考核点1：了解一个Java程序的启动位置（即程序入口）。考核点2：掌握基本输出语句：System.out.println(字符串)【第2课】【作业1】从键盘输入3个整数a、b、c，计算a+b*c的结果后输出，验证计算结果是否遵循运算符的优先级顺序。考核点1：使用Scanner类获取键盘输入。考核点2：基本运算符及其优先级顺序。【作业2】从键盘输入1个实数r，计算以r为半径的圆的面积并输出结果，要求将定义为符号常量。考核点：符号常量的基本用法。【第

2、3课】【作业1】从键盘输入3个整数，比较大小后输出最大者。考核点：if-else语句的运用。【作业2】从键盘输入一个3位数，判断其是否为水仙花数。所谓“水仙花数”是指一个三位整数，其各位数字立方和等于该数本身。例如：153=13+53+33,所以153是一个水仙花数。考核点：基本数学运算符和逻辑运算符的用法。【第4课】【作业1】从键盘输入3个整数，比较大小后按由小到大的顺序输出。考核点：if-else语句嵌套运用。【作业2】从键盘输入一个年份和一个月份，输出此月份有多少天（考虑闰二月的情况）。考核点：使用switch-case多分支语句。【第5课】【作业1】从键盘输入一个正整数，判断其是否为素

3、数。素数指只有1和它本身两个因子的整数。考核点：基本循环语句的用法。【作业2】输出100-999之间的全部水仙花数。考核点：基本循环语句的用法。【作业3】从键盘输入一个正整数，判断并输出该正整数是几位数。考核点1：基本循环语句的用法。考核点2：分离一个整数各个位数字的方法。【第6课】【作业1】编写一个Java程序，输出如下图案，图案的行数由键盘输入。（1）观察图案中行、列及星星个数之间的关系。（2）扩展练习，输出如下图案，图案的行数由键盘输入。（3）扩展练习，输出如下图案，图案的行数由键盘输入。考核点1：发现图案中的变化规律(即逻辑）。考核点2：循环嵌套的用法。【作业2】从键盘输入一个正整数n

4、，利用求的近似值，n为求和的总项数。考核点：发现公式中的计算规律（即计算逻辑）。【作业3】百钱百鸡问题：公鸡每只5元、母鸡每只3元、小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数。考核点1：多重循环的使用。考核点2：提炼和化简计算逻辑，将多重循环改进为单重循环。【第7课】【作业1】将输入的一个偶数n(n>=6)分解为两个素数之和。例如8=5+3。【作业2】有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，请输出这n个人退出圈子的整个次序。【第8课】【作业1】将一个n×n方阵就地转置，即行列元素互换。（1）扩展成矩阵转置，将一

5、个矩阵a(m×n)转置成一个新矩阵b(n×m)。【作业2】建立如下的杨辉三角，行数n由键盘输入。（1）分析出杨辉三角形中每个元素的计算逻辑。（2）使用System.out.printf()方法进行格式化输出。【第9课】【作业1】回文串：输入一个字符串，判断其是否为回文串并输出结果。回文串是指从左向右读与从右向左读都相同的一个字符串，如12a3a21就是一个回文串。【作业2】超大整数求和：编写一个Java程序，能对输入的两个超大非负整数求和。例如：输入“12345678”和“111”，其和为“12345789”。（1）每个超大非负整数以字符串形式存储。（2）求和的结果也以字符

6、串形式存储。【作业3】将一个正整数（万以内的数字）的每一位数值转换成中文中的数值表示（如将 5036 转换成“伍仟零叁拾陆”）。（1）使用数据表来简化转换逻辑。（2）注意逻辑思维的严密性。一组转换数据样例（万以内的数字）数字串汉字串0零100壹佰90000玖万90001玖万零壹90500玖万零伍佰91002玖万壹仟零贰90070玖万零柒拾90055玖万零伍拾伍90909玖万零玖佰零玖90990玖万零玖佰玖拾【第10课】【作业1】编写一个Java程序，定义Java静态方法实现下面数学分段函数并进行验证。【作业2】编写一个Java静态方法，将一个m*n矩阵转置成一个n*m矩阵。【作业3】输入一个数

7、字a，求S=a+aa+aaa+aaaa+aaaaa的和。例如，a=2，则S=2+22+222+2222+22222。（1）学会发现问题中的共性以分解问题。（2）理解解决同一问题的多种逻辑思维。【第11课】【作业1】编写一个Java程序，输出21000以内的全部完数。一个完数恰好等于其全部因子之和。例如6=1+2+3，故6是一个完数，28=1+2+4+7+14，故28也是一个完数。要求采用模块化程序设计解决此类问题。【作业2】编写函数完成下列每种数制转换：（1）十进制正整数à二进制正整数。（2）十进制正整数à十六进制正整数。（3）十进制正整数à八进制正整数。要求采用

8、模块化程序设计解决此类问题，发现数制转换中的共性规律。【作业3】从键盘输入一个棋盘的行数和列数，打印出棋盘的样子。（1） 分析打印棋盘的整个过程，发现其中的逻辑步骤。（2） 编写方法实现不同的逻辑步骤。【第12课】【作业1】汉诺塔问题：有n个盘子依其半径大小套在柱子A上，其中半径大的在底下，柱子B和C没套盘子。现要将A上的盘子全部搬运到C上（借助B），移动规则是每次只能移动一个盘子，并且不允许将大盘子压在小盘子的上面。（1）分析归纳出搬运n个盘子的递归规律，编写递归方法。（2）输出完整的搬运过程以及移动盘子的总次数。【作业2】编写一个Java程序，输入两个正整数m和n，输出m和n的最大公约数（

9、greatest common divisor）和最小公倍数（Least Common Multiple）。（1）最大公约数gcd是指m和n的全部公共因子之积，最小公倍数lcm为m和n之积除以最大公约数gcd。（2）掌握计算最大公约数的递推方法：辗转相除法。【作业3】天平称物：有四个砝码，总重量是40克，砝码的质量是整数，且各不相等。请确定它们的质量，使之能称出1到40克之间任何整数质量的物体。【作业4】一个整数除以3余2，除以5余3，除以7余2，求这个整数。【第13课】【作业1】将二分查找算法改写为递归形式。【作业2】编写一个Java程序，从一个字符串中S中删除所有和字符串T相同的子串，输出

10、删除后的结果。例如：S=“abcdabef”，T="ab"，则删除后的结果S="cdef"。【作业3】编写一个Java程序，求得所有包含在串S中而不包含在串T中的字符构成的新串R。例如：S=“aabcddef”，T="cf"，则R="aabdde"。【作业4】编写一个Java程序，求得串S和串T中的一个最长公共子串R。例如：S=“aabcddef”，T="bcbcdd"，则R="bcdd"。【第14课】【作业1】改进冒泡排序算法，只要在一趟冒泡排序过程中不发生相邻记录的交换，

11、则整个排序过程就可以立即结束。【作业2】荷兰国旗问题：设有一个仅由红、白、蓝三种颜色的条块组成的条块序列。请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。【作业3】烙饼排序问题（1）一次烙饼翻转过程：（2）将最大的烙饼调整到最底端：（两次翻转）（3）对于n块烙饼，最多翻转2(n-1)即可排好顺序。（4）假设一叠烙饼的半径分别为20,22,30,18,19,25,20，则要翻转多少次才能排好顺序？请编写出烙饼排序算法。【第15课】分治算法（任选一个作业）【作业1】给定由n个整数（可能有负整数）组成的序列(a1, a2, , an)，最大子段和问题要求

12、该序列形如 的最大值（1ijn），例如，序列(-20, 11, -4, 13, -5, -2)的最大子段和为 【作业2】在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。要求输出棋盘覆盖后的效果。【第16课】减治算法（任选一个作业）【作业1】应用堆排序方法对一个记录序列进行升序排列。其基本思想是：首先将待排序的记录序列构造成一个堆，此时，堆顶记录是堆中所有记录的最大者，将它从堆中移走（通常将堆顶记

13、录和堆中最后一个记录交换），然后将剩余记录再调整成堆，这样又找出了次大记录，以此类推，直到堆中只有一个记录为止。【作业2】在n枚外观相同的硬币中，有一枚是假币，并且已知假币较轻。通过一架来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些，假币问题要求设计一个高效的算法来检测出这枚假币。（1）一分为二想法：把n枚硬币分成两组，每组有n/2枚硬币，如果n为奇数，就留下一枚硬币，然后把两组硬币分别放到天平的两端。如果两组硬币的重量相同，那么留下的硬币就是假币；否则，用同样的方法对较轻的那组硬币进行同样的处理，因为假币一定在较轻的那组里。（2）一分为三想法：【作业3】将数字旋转方阵

14、的递归算法改为非递归算法。【第17课】动态规划算法（任选一个作业）【作业1】数塔问题：从数塔的顶层出发，在每一个结点可以选择向左走或向右走，一直走到最底层，要求找出一条路径，使得路径上的数值和最大。 【作业2】最长递增子序列问题：在数字序列A=a1, a2, , an中按递增下标序列(i1, i2, ik)（1i1< i2<< ikn）顺序选出一个子序列B，如果子序列B中的数字都是严格递增的，则子序列B称为序列A的递增子序列。最长递增子序列问题就是要找出序列A的一个最长的递增子序列。例如，对于序列A=5, 2, 8, 6, 3, 6, 9, 7，其最长递增子序列分别是2, 3

15、, 6, 9和2, 3, 6, 7。【作业3】0/1背包问题：给定n种物品和一个背包，物品i的重量是wi，其价值为vi，背包的容量为C。背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?如果在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或不装入背包，即不能将物品i装入背包多次，也不能只装入物品i的一部分，则称为0/1背包问题。例如，有5个物品，其重量分别是2, 2, 6, 5, 4，价值分别为6, 3, 5, 4, 6，背包的容量为10，则能装入到背包中的物品为第1,2,5三个物品，最大价值为15。【第18课】贪心算法（任选一个作业）【作业1】背包问题：给定n种物品

16、和一个容量为C的背包，物品i的重量是wi，其价值为vi，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大? （1）注意背包问题与0/1背包问题的区别。（2）贪心策略：优先选择单位重量价值最大的物品。【作业2】多机调度问题：设有n个独立的作业1, 2, , n，由m台相同的机器M1, M2, , Mm进行加工处理，作业i所需的处理时间为ti（1in），每个作业均可在任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。（1）贪心策略：按照最长处理时间作业优先。（2）例如，设7个独立作业1, 2, 3, 4, 5, 6, 7由3台机器M1, M2, M3加工处理，各作业所需的处理时间分别为2, 14, 4, 16, 6, 5, 3。则调度过程如下图：【第19课】回溯算法（任选一个作业）【作业1】素数环问题：把整数1, 2, , 20填写到一个环中，要求每个整数只填写一次，并且相邻的两个整数之和是一个素数。1234【作业2】批处理作业调度问题：n个作业1, 2, , n要在两台机器上处理，每个作业必须先由机器1处理，然后再由机器2