課堂作業(yè)(模塊1Java編程邏輯)

課堂作業(yè)

模塊1Java編程邏輯

【第1課】

【作業(yè)1】編寫一個Java程序，在控制臺上輸出如下兩行信息:

Hello,World!

Hello,Java!

考核點1：了解一個Java程序的啟動位置（即程序入口）。

考核點2：掌握基本輸出語句：System.out.printin（字符串）

【第2課】

【作業(yè)1】從鍵盤輸入3個整數a、b、c,計算a+b*c的結果后輸出，

驗證計算結果是否遵循運算符的優(yōu)先級順序。

考核點1：使用Scanner類獲取鍵盤輸入。

考核點2：基本運算符及其優(yōu)先級順序。

【作業(yè)2］從鍵盤輸入1個實數r,計算以r為半徑的圓的面積并輸

出結果，要求將花定義為符號常量。

考核點：符號常量的基本用法。

【第3課】

【作業(yè)1】從鍵盤輸入3個整數，比較大小后輸出最大者。

考核點：if-else語句的運用。

【作業(yè)2】從鍵盤輸入一個3位數，判斷其是否為水仙花數。所謂“水

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

153=13+53+33,所以153是一個水仙花數。

考核點：基本數學運算符和邏輯運算符的用法。

【第4課】

【作業(yè)1】從鍵盤輸入3個整數，比較大小后按由小到大的順序輸出。

考核點：if-else語句嵌套運用。

【作業(yè)2】從鍵盤輸入一個年份和一個月份，輸出此月份有多少天（考

慮閏二月的情況）。

考核點：使用switch-case多分支語句。

【第5課】

【作業(yè)1】從鍵盤輸入一個正整數，判斷其是否為素數。素數指只有

1和它本身兩個因子的整數。

考核點：基本循環(huán)語句的用法。

【作業(yè)2】輸出100-999之間的全部水仙花數。

考核點：基本循環(huán)語句的用法。

【作業(yè)3】從鍵盤輸入一個正整數，判斷并輸出該正整數是幾位數。

考核點L基本循環(huán)語句的用法。

考核點2：分離一個整數各個位數字的方法。

【第6課】

【作業(yè)1】編寫一個Java程序，輸出如下圖案，圖案的行數由鍵盤

輸入。

*****

*****東東

(1)觀察圖案中行、列及星星個數之間的關系。

(2)擴展練習，輸出如下圖案，圖案的行數由鍵盤輸入。

*******

。。0*

(3)擴展練習，輸出如下圖案，圖案的行數由鍵盤輸入。

**射

***務*

關*****

*****

***

*

考核點1:發(fā)現圖案中的變化規(guī)律（即邏輯）。

考核點2：循環(huán)嵌套的用法。

【作業(yè)2】從鍵盤輸入一個正整數n,利嗚-+求”的近

似值，n為求和的總項數。

考核點：發(fā)現公式中的計算規(guī)律（即計算邏輯）。

【作業(yè)3】百錢百雞問題：公雞每只5元、母雞每只3元、小雞3只

1元，用100元錢買100只雞，求公雞、母雞、小雞的只數。

考核點1：多重循環(huán)的使用。

考核點2：提煉和化簡計算邏輯，將多重循環(huán)改進為單重循環(huán)。

【第7課】

【作業(yè)11將輸入的一個偶數n（n>=6）分解為兩個素數之和。例如

8=5+3。

【作業(yè)2】有n個人圍成一圈，順序排號。從第一個人開始報數（從

1到3報數)，凡報到3的人退出圈子，請輸出這n個人退出圈子的

整個次序。

【第8課】

【作業(yè)1】將一個nXn方陣就地轉置，即行列元素互換。

(1)擴展成矩陣轉置，將一個矩陣a(mXn)轉置成一個新矩陣b(n

Xm)o

【作業(yè)2】建立如下的楊輝三角，行數n由鍵盤輸入。

1

11

121

1331

14641

15101051

1615201561

(1)分析出楊輝三角形中每個元素的計算邏輯。

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

【第9課】

【作業(yè)1】回文串：輸入一個字符串，判斷其是否為回文串并輸出結

果?；匚拇侵笍淖笙蛴易x與從右向左讀都相同的一個字符串，如

12a3a21就是一個回文串。

【作業(yè)2】超大整數求和：編寫一個Java程序，能對輸入的兩個超

大非負整數求和。例如:輸入“12345678”和“111”,其和為“12345789”。

(1)每個超大非負整數以字符串形式存儲。

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

【作業(yè)3】將一個正整數(萬以內的數字)的每一位數值轉換成中文

中的數值表示(如將5036轉換成“伍仟零叁拾陸

(1)使用數據表來簡化轉換邏輯。

(2)注意邏輯思維的嚴密性。

一組轉換數據樣例(萬以內的數字)

數字串漢字串

0零

100壹佰

90000玖萬

90001玖萬零壹

90500玖萬零伍佰

91002玖萬壹仟零貳

90070玖萬零柒拾

90055玖萬零伍拾伍

90909玖萬零玖佰零玖

90990玖萬零玖佰玖拾

【第10課】

【作業(yè)1】編寫一個Java程序，定義Java靜態(tài)方法實現下面數學分

段函數并進行驗證。

JC.(x<D

2之一1(1QV10)

31r—11(，10)

【作業(yè)2］編寫一個Java靜態(tài)方法，將一個m*n矩陣轉置成一個n*m

矩陣。

123147

456258

789369

【作業(yè)3］輸入一個數字a,求S=a+aa+aaa+aaaa+aaaaa的和。例如,

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

(1)學會發(fā)現問題中的共性以分解問題。

(2)理解解決同一問題的多種邏輯思維。

【第11課】

【作業(yè)11編寫一個Java程序，輸出2——1000以內的全部完數。

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

28=1+2+4+7+14,故28也是一個完數。要求采用模塊化程序設計解決

此類問題。

【作業(yè)2】編寫函數完成下列每種數制轉換:

(1)十進制正整數)二進制正整數。

(2)十進制正整數令十六進制正整數。

(3)十進制正整數今八進制正整數。

要求采用模塊化程序設計解決此類問題，發(fā)現數制轉換中的共性規(guī)

律。

【作業(yè)3】從鍵盤輸入一個棋盤的行數和列數，打印出棋盤的樣子。

(1)分析打印棋盤的整個過程，發(fā)現其中的邏輯步驟。

(2)編寫方法實現不同的邏輯步驟。

【第12課】

【作業(yè)1】漢諾塔問題：有n個盤子依其半徑大小套在柱子A上，其

中半徑大的在底下，柱子B和C沒套盤子。現要將A上的盤子全部搬

運到C上(借助B),移動規(guī)則是每次只能移動一個盤子，并且不允

許將大盤子壓在小盤子的上面。

(1)分析歸納出搬運n個盤子的遞歸規(guī)律，編寫遞歸方法。

(2)輸出完整的搬運過程以及移動盤子的總次數。

【作業(yè)2】編寫一個Java程序，輸入兩個正整數m和n,輸出m和n

的最大公約數(greatestcommondivisor)和最小公倍數(Least

CommonMultiple)o

(1)最大公約數是指m和n的全部公共因子之積，最小公倍數

1cm為m和n之積除以最大公約數。

(2)掌握計算最大公約數的遞推方法：輾轉相除法。

【作業(yè)3］天平稱物：有四個祛碼，總重量是40克，祛碼的質量是

整數，且各不相等。請確定它們的質量，使之能稱出1到40克之間

任何整數質量的物體。

【作業(yè)4】一個整數除以3余2,除以5余3,除以7余2,求這個整

數。

【第13課】

【作業(yè)1】將二分查找算法改寫為遞歸形式。

【作業(yè)2］編寫一個Java程序，從一個字符串中S中刪除所有和字

符串T相同的子串，輸出刪除后的結果。例如:SBabcdabef”,T=〃ab〃,

則刪除后的結果S^cdef-o

【作業(yè)3］編寫一個Java程序，求得所有包含在串S中而不包含在

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

R="aabdde”。

【作業(yè)4］編寫一個Java程序，求得串S和串T中的一個最長公共

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

【第14課】

【作業(yè)1】改進冒泡排序算法，只要在一趟冒泡排序過程中不發(fā)生相

鄰記錄的交換，則整個排序過程就可以立即結束。

【作業(yè)2】荷蘭國旗問題：設有一個僅由紅、白、藍三種顏色的條塊

組成的條塊序列。請編寫一個時間復雜度為0(n)的算法，使得這些

條塊按紅、白、藍的順序排好，即排成荷蘭國旗圖案。

【作業(yè)3】烙餅排序問題

星期五的晚上，一幫同事在希格瑪大廈附近的1■硬盤酒口巴"多喝了幾杯。程序員多

喝了幾杯之后談什么呢？自然是算法問題。有個同事說：

“我以前在餐館打工，顧客經常點非常多的烙餅。店里的餅大小不一，我習慣在到

達顧客飯桌前，把一摞餅按照大小次序擺好——小的在上面，大的在下面。由于我一只

手托著盤子，只好用另一只手，一次抓住最上面的幾塊餅，把它們上下顛倒個個兒，反

復幾次之后，這摞烙餅就排好序了。

我后來想，這實際上是個有趣的排序問題：假設有〃塊大小不一的烙餅，那最少要

翻幾次，才能達到最后大小有序的結果呢？

你能否寫出一個程序，對于〃塊大小不一的烙餅，輸出最優(yōu)化的翻餅過程呢？

(1)一次烙餅翻轉過程:

(2)將最大的烙餅調整到最底端：(兩次翻轉)

(3)對于n塊烙餅，最多翻轉2(n-1)即可排好順序。

(4)假設一疊烙餅的半徑分別為20,22,30,18,19,25,20,則要翻轉

多少次才能排好順序？請編寫出烙餅排序算法。

【第15課】分治算法

(任選一個作業(yè))

【作業(yè)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.....最大子段和橫跨兩個子序列

【作業(yè)2】在一個2kx2k個方格組成的棋盤中，恰有一個方格與其他

方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋

盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊

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

蓋。

要求輸出棋盤覆蓋后的效果。

初始棋盤：

0—100

0000

0000

0000

茬蓋后的模盤:

2—133

2213

5114

LX_544

【第16課】減治算法

（任選一個作業(yè)）

【作業(yè)1］應用堆排序方法對一個記錄序列進行升序排列。其基本思

想是：首先將待排序的記錄序列構造成一個堆，此時，堆頂記錄是堆

中所有記錄的最大者，將它從堆中移走（通常將堆頂記錄和堆中最后

一個記錄交換），然后將剩余記錄再調整成堆，這樣又找出了次大記

錄，以此類推，直到堆中只有一個記錄為止。

【作業(yè)2】在刀枚外觀相同的硬幣中，有一枚是假幣，并且已知假幣

較輕。通過一架來任意比較兩組硬幣，從而得知兩組硬幣的重量是否

相同，或者哪一組更輕一些，假幣問題要求設計一個高效的算法來檢

測出這枚假幣。

(1)一分為二想法：把Z7枚硬幣分成兩組，每組有W2枚硬幣，如

果〃為奇數，就留下一枚硬幣,然后把兩組硬幣分別放到天平的兩端0

如果兩組硬幣的重量相同，那么留下的硬幣就是假幣；否則，用同樣

的方法對較輕的那組硬幣進行同樣的處理，因為假幣一定在較輕的那

組里。

(2)一分為三想法：

1.如果n等于1,貝！(該硬布即為假幣,輸由對應的序

號，算法結束；

2.計算3組的硬幣個數numl、num2和num3；

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

的重量和；

4.根據情況執(zhí)行下述三種操作之一：

4.1如果addl小于add2,則在第1組硬幣中查找；

4.2如果addl大于add2,則在第2組硬幣中查找；

4.3如果addl等于add2,則在第3組硬幣中查找；

【作業(yè)3】將數字旋轉方陣的遞歸算法改為非遞歸算法。

【第17課】動態(tài)規(guī)劃算法

（任選一個作業(yè)）

【作業(yè)1】數塔問題：從數塔的頂層出發(fā)，在每一個結點可以選擇向

左走或向右走，一直走到最底層，要求找出一條路徑，使得路徑上的

數值和最大。

【作業(yè)2］最長遞增子序列問題：在數字序列走｛可，如，…，

中按遞增下標序列（與，功，…，〃）72<-<順序

選出一個子序列氏如果子序列3中的數字都是嚴格遞增的，則子序

列§稱為序列A的遞增子序列。最長遞增子序列問題就是要找出序列

4的一個最長的遞增子序列。

例如，對于序列A=｛5,2,8,6,3,6,9,7）,其最長遞增子序列

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

【作業(yè)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課】貪心算法

(任選一個作業(yè))

【作業(yè)1】背包問題：給定〃種物品和一個容量為。的背包，物品/

的重量是吟，其價值為勺，背包問題是如何選擇裝入背包的物品，

使得裝入背包中物品的總價值最大？

(1)注意背包問題與0/1背包問題的區(qū)別。

(2)貪心策略：優(yōu)先選擇單位重量價值最大的物品。

【作業(yè)2】多機調度問題：設有〃個獨立的作業(yè)｛1,2,加，由卬

臺相同的機器｛跖，的，…，峭進行加工處理，作業(yè)，所需的處理時

間為門(100),每個作業(yè)均可在任何一臺機器上加工處理，但

不可間斷、拆分。多機調度問題要求給出一種作業(yè)調度方案，使所給

的〃個作業(yè)在盡可能短的時間內由卬臺機器加工處理完成。

(1)貪心策略：按照最長處理時間作業(yè)優(yōu)先。

(2)例如，設7個獨立作業(yè)｛1,2,3,4,5,6,7｝由3臺機器｛幽，

畋，為｝加工處理，各作業(yè)所需的處理時間分別為｛2,14,4,16,6,

5,3｝o則調度過程如下圖：

M2

的

時間

分配

【第19課】回溯算法

(任選一個作業(yè))

【作業(yè)1】素數環(huán)問題：把整數口，2,…，20｝填寫到一個環(huán)中，要

求每個整數只填寫一次，并且相鄰的兩個整數之和是一個素數。

1

w

【作業(yè)21批處理作業(yè)調度問題：〃個作業(yè)｛1,2,加要在兩臺機

器上處理，每個作業(yè)必須先由機器1處理，然后再由機器2處理，機

器1處理作業(yè)i所需時間為a?機器2處理作業(yè)z.所需時間為為(1

WZWA),批處理作業(yè)調度問題要求確定這刀個作業(yè)的最優(yōu)處理順序,

使得從第1個作業(yè)在機器1上處理開始，到最后一個作業(yè)在機器2

上處理結束所需時間最少。

例如，有三個作業(yè)｛1,2,3),這三個作業(yè)在機器1上所需的處理時

間為(2,3,2),在機器2上所需的處理時間為(1,1,3),則這三個

作業(yè)存在6種可能的調度方案:(1,2,3)、(1,3,2)、(2,1,3)、

(2,3,1)、(3,1,2)、(3,2,1),組成完整的解空間樹。

機器1I-I--------域至---------1——域圖——I

機器2卜郅?一一(一作業(yè)卜3_h-------------■(作業(yè)22卜---