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

课堂作业

模块1Java编程逻辑

【第1课】

【作业1】编写一个Java程序，在控制台上输出如下两行信息:

Hello,World!

Hello,Java!

考核点1：了解一个Java程序的启动位置（即程序入口）。

考核点2：掌握基本输出语句：System.out.printin（字符串）

【第2课】

【作业1】从键盘输入3个整数a、b、c,计算a+b*c的结果后输出，

验证计算结果是否遵循运算符的优先级顺序。

考核点1：使用Scanner类获取键盘输入。

考核点2：基本运算符及其优先级顺序。

【作业2］从键盘输入1个实数r,计算以r为半径的圆的面积并输

出结果，要求将花定义为符号常量。

考核点：符号常量的基本用法。

【第3课】

【作业1】从键盘输入3个整数，比较大小后输出最大者。

考核点：if-else语句的运用。

【作业2】从键盘输入一个3位数，判断其是否为水仙花数。所谓“水

仙花数”是指一个三位整数，其各位数字立方和等于该数本身。例如:

153=13+53+33,所以153是一个水仙花数。

考核点：基本数学运算符和逻辑运算符的用法。

【第4课】

【作业1】从键盘输入3个整数，比较大小后按由小到大的顺序输出。

考核点：if-else语句嵌套运用。

【作业2】从键盘输入一个年份和一个月份，输出此月份有多少天（考

虑闰二月的情况）。

考核点：使用switch-case多分支语句。

【第5课】

【作业1】从键盘输入一个正整数，判断其是否为素数。素数指只有

1和它本身两个因子的整数。

考核点：基本循环语句的用法。

【作业2】输出100-999之间的全部水仙花数。

考核点：基本循环语句的用法。

【作业3】从键盘输入一个正整数，判断并输出该正整数是几位数。

考核点L基本循环语句的用法。

考核点2：分离一个整数各个位数字的方法。

【第6课】

【作业1】编写一个Java程序，输出如下图案，图案的行数由键盘

输入。

*****

*****东东

(1)观察图案中行、列及星星个数之间的关系。

(2)扩展练习，输出如下图案，图案的行数由键盘输入。

*******

。。0*

(3)扩展练习，输出如下图案，图案的行数由键盘输入。

**射

***务*

关*****

*****

***

*

考核点1:发现图案中的变化规律（即逻辑）。

考核点2：循环嵌套的用法。

【作业2】从键盘输入一个正整数n,利呜-+求”的近

似值，n为求和的总项数。

考核点：发现公式中的计算规律（即计算逻辑）。

【作业3】百钱百鸡问题：公鸡每只5元、母鸡每只3元、小鸡3只

1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数。

考核点1：多重循环的使用。

考核点2：提炼和化简计算逻辑，将多重循环改进为单重循环。

【第7课】

【作业11将输入的一个偶数n（n>=6）分解为两个素数之和。例如

8=5+3。

【作业2】有n个人围成一圈，顺序排号。从第一个人开始报数（从

1到3报数)，凡报到3的人退出圈子，请输出这n个人退出圈子的

整个次序。

【第8课】

【作业1】将一个nXn方阵就地转置，即行列元素互换。

(1)扩展成矩阵转置，将一个矩阵a(mXn)转置成一个新矩阵b(n

Xm)o

【作业2】建立如下的杨辉三角，行数n由键盘输入。

1

11

121

1331

14641

15101051

1615201561

(1)分析出杨辉三角形中每个元素的计算逻辑。

(2)使用System.out.printf()方法进行格式化输出。

【第9课】

【作业1】回文串：输入一个字符串，判断其是否为回文串并输出结

果。回文串是指从左向右读与从右向左读都相同的一个字符串，如

12a3a21就是一个回文串。

【作业2】超大整数求和：编写一个Java程序，能对输入的两个超

大非负整数求和。例如:输入“12345678”和“111”,其和为“12345789”。

(1)每个超大非负整数以字符串形式存储。

(2)求和的结果也以字符串形式存储。

【作业3】将一个正整数(万以内的数字)的每一位数值转换成中文

中的数值表示(如将5036转换成“伍仟零叁拾陆

(1)使用数据表来简化转换逻辑。

(2)注意逻辑思维的严密性。

一组转换数据样例(万以内的数字)

数字串汉字串

0零

100壹佰

90000玖万

90001玖万零壹

90500玖万零伍佰

91002玖万壹仟零贰

90070玖万零柒拾

90055玖万零伍拾伍

90909玖万零玖佰零玖

90990玖万零玖佰玖拾

【第10课】

【作业1】编写一个Java程序，定义Java静态方法实现下面数学分

段函数并进行验证。

JC.(x<D

2之一1(1QV10)

31r—11(，10)

【作业2］编写一个Java静态方法，将一个m*n矩阵转置成一个n*m

矩阵。

123147

456258

789369

【作业3］输入一个数字a,求S=a+aa+aaa+aaaa+aaaaa的和。例如,

a=2,则S=2+22+222+2222+22222o

(1)学会发现问题中的共性以分解问题。

(2)理解解决同一问题的多种逻辑思维。

【第11课】

【作业11编写一个Java程序，输出2——1000以内的全部完数。

一个完数恰好等于其全部因子之和。例如6=1+2+3,故6是一个完数,

28=1+2+4+7+14,故28也是一个完数。要求采用模块化程序设计解决

此类问题。

【作业2】编写函数完成下列每种数制转换:

(1)十进制正整数)二进制正整数。

(2)十进制正整数令十六进制正整数。

(3)十进制正整数今八进制正整数。

要求采用模块化程序设计解决此类问题，发现数制转换中的共性规

律。

【作业3】从键盘输入一个棋盘的行数和列数，打印出棋盘的样子。

(1)分析打印棋盘的整个过程，发现其中的逻辑步骤。

(2)编写方法实现不同的逻辑步骤。

【第12课】

【作业1】汉诺塔问题：有n个盘子依其半径大小套在柱子A上，其

中半径大的在底下，柱子B和C没套盘子。现要将A上的盘子全部搬

运到C上(借助B),移动规则是每次只能移动一个盘子，并且不允

许将大盘子压在小盘子的上面。

(1)分析归纳出搬运n个盘子的递归规律，编写递归方法。

(2)输出完整的搬运过程以及移动盘子的总次数。

【作业2】编写一个Java程序，输入两个正整数m和n,输出m和n

的最大公约数(greatestcommondivisor)和最小公倍数(Least

CommonMultiple)o

(1)最大公约数是指m和n的全部公共因子之积，最小公倍数

1cm为m和n之积除以最大公约数。

(2)掌握计算最大公约数的递推方法：辗转相除法。

【作业3］天平称物：有四个祛码，总重量是40克，祛码的质量是

整数，且各不相等。请确定它们的质量，使之能称出1到40克之间

任何整数质量的物体。

【作业4】一个整数除以3余2,除以5余3,除以7余2,求这个整

数。

【第13课】

【作业1】将二分查找算法改写为递归形式。

【作业2］编写一个Java程序，从一个字符串中S中删除所有和字

符串T相同的子串，输出删除后的结果。例如:SBabcdabef”,T=〃ab〃,

则删除后的结果S^cdef-o

【作业3］编写一个Java程序，求得所有包含在串S中而不包含在

串T中的字符构成的新串Ro例如:S="aabeddef"，T=〃cf〃,则

R="aabdde”。

【作业4］编写一个Java程序，求得串S和串T中的一个最长公共

子串R。例如:S="aabeddef",T="bcbcdd”,则1?="n(1(1”。

【第14课】

【作业1】改进冒泡排序算法，只要在一趟冒泡排序过程中不发生相

邻记录的交换，则整个排序过程就可以立即结束。

【作业2】荷兰国旗问题：设有一个仅由红、白、蓝三种颜色的条块

组成的条块序列。请编写一个时间复杂度为0(n)的算法，使得这些

条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

【作业3】烙饼排序问题

星期五的晚上，一帮同事在希格玛大厦附近的1■硬盘酒口巴"多喝了几杯。程序员多

喝了几杯之后谈什么呢？自然是算法问题。有个同事说：

“我以前在餐馆打工，顾客经常点非常多的烙饼。店里的饼大小不一，我习惯在到

达顾客饭桌前，把一摞饼按照大小次序摆好——小的在上面，大的在下面。由于我一只

手托着盘子，只好用另一只手，一次抓住最上面的几块饼，把它们上下颠倒个个儿，反

复几次之后，这摞烙饼就排好序了。

我后来想，这实际上是个有趣的排序问题：假设有〃块大小不一的烙饼，那最少要

翻几次，才能达到最后大小有序的结果呢？

你能否写出一个程序，对于〃块大小不一的烙饼，输出最优化的翻饼过程呢？

(1)一次烙饼翻转过程:

(2)将最大的烙饼调整到最底端：(两次翻转)

(3)对于n块烙饼，最多翻转2(n-1)即可排好顺序。

(4)假设一叠烙饼的半径分别为20,22,30,18,19,25,20,则要翻转

多少次才能排好顺序？请编写出烙饼排序算法。

【第15课】分治算法

(任选一个作业)

【作业1】给定由A个整数(可能有负整数)组成的序列(丐，为，…，

a),最大子段和问题要求该序列形如£「的最大值(IWiWjW

〃)，例如，序列(-20,11,-4,13,-5,-2)的最大子段和为E耿=20

%.....…〃加4k加4+1…勺........%.....划分

丫V

leftsumrightsum递归处理

ma，X{leftsum,sum,rightsum}..........合并解

sum.....-不能递归处理

/加］。加衣1…勺)……an.....最大子段和横跨两个子序列

【作业2】在一个2kx2k个方格组成的棋盘中，恰有一个方格与其他

方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋

盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊

棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆

盖。

要求输出棋盘覆盖后的效果。

初始棋盘：

0—100

0000

0000

0000

茬盖后的模盘:

2—133

2213

5114

LX_544

【第16课】减治算法

（任选一个作业）

【作业1］应用堆排序方法对一个记录序列进行升序排列。其基本思

想是：首先将待排序的记录序列构造成一个堆，此时，堆顶记录是堆

中所有记录的最大者，将它从堆中移走（通常将堆顶记录和堆中最后

一个记录交换），然后将剩余记录再调整成堆，这样又找出了次大记

录，以此类推，直到堆中只有一个记录为止。

【作业2】在刀枚外观相同的硬币中，有一枚是假币，并且已知假币

较轻。通过一架来任意比较两组硬币，从而得知两组硬币的重量是否

相同，或者哪一组更轻一些，假币问题要求设计一个高效的算法来检

测出这枚假币。

(1)一分为二想法：把Z7枚硬币分成两组，每组有W2枚硬币，如

果〃为奇数，就留下一枚硬币,然后把两组硬币分别放到天平的两端0

如果两组硬币的重量相同，那么留下的硬币就是假币；否则，用同样

的方法对较轻的那组硬币进行同样的处理，因为假币一定在较轻的那

组里。

(2)一分为三想法：

1.如果n等于1,贝！(该硬布即为假币,输由对应的序

号，算法结束；

2.计算3组的硬币个数numl、num2和num3；

3.addl=第1组硬币的重量和；ad<12=第2组硬币

的重量和；

4.根据情况执行下述三种操作之一：

4.1如果addl小于add2,则在第1组硬币中查找；

4.2如果addl大于add2,则在第2组硬币中查找；

4.3如果addl等于add2,则在第3组硬币中查找；

【作业3】将数字旋转方阵的递归算法改为非递归算法。

【第17课】动态规划算法

（任选一个作业）

【作业1】数塔问题：从数塔的顶层出发，在每一个结点可以选择向

左走或向右走，一直走到最底层，要求找出一条路径，使得路径上的

数值和最大。

【作业2］最长递增子序列问题：在数字序列走｛可，如，…，

中按递增下标序列（与，功，…，〃）72<-<顺序

选出一个子序列氏如果子序列3中的数字都是严格递增的，则子序

列§称为序列A的递增子序列。最长递增子序列问题就是要找出序列

4的一个最长的递增子序列。

例如，对于序列A=｛5,2,8,6,3,6,9,7）,其最长递增子序列

分别是｛2,3,6,9｝和｛2,3,6,7｝。

【作业3】0/1背包问题：给定〃种物品和一个背包，物品z•的重量

是叼,其价值为”，背包的容量为a背包问题是如何选择装入背

包的物品，使得装入背包中物品的总价值最大?如果在选择装入背包

的物品时，对每种物品/只有两种选择：装入背包或不装入背包，即

不能将物品z.装入背包多次，也不能只装入物品了的一部分，则称为

0/1背包问题。

例如，有5个物品，其重量分别是｛2,2,6,5,4｝,价值分别为｛6,

3,5,4,6｝,背包的容量为10,则能装入到背包中的物品为第1,2,5

三个物品，最大价值为15。

【第18课】贪心算法

(任选一个作业)

【作业1】背包问题：给定〃种物品和一个容量为。的背包，物品/

的重量是吟，其价值为勺，背包问题是如何选择装入背包的物品，

使得装入背包中物品的总价值最大？

(1)注意背包问题与0/1背包问题的区别。

(2)贪心策略：优先选择单位重量价值最大的物品。

【作业2】多机调度问题：设有〃个独立的作业｛1,2,加，由卬

台相同的机器｛跖，的，…，峭进行加工处理，作业，所需的处理时

间为门(100),每个作业均可在任何一台机器上加工处理，但

不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给

的〃个作业在尽可能短的时间内由卬台机器加工处理完成。

(1)贪心策略：按照最长处理时间作业优先。

(2)例如，设7个独立作业｛1,2,3,4,5,6,7｝由3台机器｛幽，

畋，为｝加工处理，各作业所需的处理时间分别为｛2,14,4,16,6,

5,3｝o则调度过程如下图：

M2

的

时间

分配

【第19课】回溯算法

(任选一个作业)

【作业1】素数环问题：把整数口，2,…，20｝填写到一个环中，要

求每个整数只填写一次，并且相邻的两个整数之和是一个素数。

1

w

【作业21批处理作业调度问题：〃个作业｛1,2,加要在两台机

器上处理，每个作业必须先由机器1处理，然后再由机器2处理，机

器1处理作业i所需时间为a?机器2处理作业z.所需时间为为(1

WZWA),批处理作业调度问题要求确定这刀个作业的最优处理顺序,

使得从第1个作业在机器1上处理开始，到最后一个作业在机器2

上处理结束所需时间最少。

例如，有三个作业｛1,2,3),这三个作业在机器1上所需的处理时

间为(2,3,2),在机器2上所需的处理时间为(1,1,3),则这三个

作业存在6种可能的调度方案:(1,2,3)、(1,3,2)、(2,1,3)、

(2,3,1)、(3,1,2)、(3,2,1),组成完整的解空间树。

机器1I-I--------域至---------1——域图——I

机器2卜郅?一一(一作业卜3_h-------------■(作业22卜---