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

1、課堂作業(yè)模塊1 Java編程邏輯【第1課】【作業(yè)1】編寫一個Java程序，在控制臺上輸出如下兩行信息：Hello，World！Hello，Java！考核點1：了解一個Java程序的啟動位置（即程序入口）?？己它c2：掌握基本輸出語句：System.out.println(字符串)【第2課】【作業(yè)1】從鍵盤輸入3個整數(shù)a、b、c，計算a+b*c的結果后輸出，驗證計算結果是否遵循運算符的優(yōu)先級順序?？己它c1：使用Scanner類獲取鍵盤輸入?？己它c2：基本運算符及其優(yōu)先級順序?！咀鳂I(yè)2】從鍵盤輸入1個實數(shù)r，計算以r為半徑的圓的面積并輸出結果，要求將定義為符號常量?？己它c：符號常量的基本用法?！镜?

2、課】【作業(yè)1】從鍵盤輸入3個整數(shù)，比較大小后輸出最大者?？己它c：if-else語句的運用?！咀鳂I(yè)2】從鍵盤輸入一個3位數(shù)，判斷其是否為水仙花數(shù)。所謂“水仙花數(shù)”是指一個三位整數(shù)，其各位數(shù)字立方和等于該數(shù)本身。例如：153=13+53+33,所以153是一個水仙花數(shù)?？己它c：基本數(shù)學運算符和邏輯運算符的用法?！镜?課】【作業(yè)1】從鍵盤輸入3個整數(shù)，比較大小后按由小到大的順序輸出。考核點：if-else語句嵌套運用?！咀鳂I(yè)2】從鍵盤輸入一個年份和一個月份，輸出此月份有多少天（考慮閏二月的情況）?？己它c：使用switch-case多分支語句?！镜?課】【作業(yè)1】從鍵盤輸入一個正整數(shù)，判斷其是否為素數(shù)

3、。素數(shù)指只有1和它本身兩個因子的整數(shù)?？己它c：基本循環(huán)語句的用法?！咀鳂I(yè)2】輸出100-999之間的全部水仙花數(shù)?？己它c：基本循環(huán)語句的用法?！咀鳂I(yè)3】從鍵盤輸入一個正整數(shù)，判斷并輸出該正整數(shù)是幾位數(shù)。考核點1：基本循環(huán)語句的用法。考核點2：分離一個整數(shù)各個位數(shù)字的方法?！镜?課】【作業(yè)1】編寫一個Java程序，輸出如下圖案，圖案的行數(shù)由鍵盤輸入。（1）觀察圖案中行、列及星星個數(shù)之間的關系。（2）擴展練習，輸出如下圖案，圖案的行數(shù)由鍵盤輸入。（3）擴展練習，輸出如下圖案，圖案的行數(shù)由鍵盤輸入。考核點1：發(fā)現(xiàn)圖案中的變化規(guī)律(即邏輯）?？己它c2：循環(huán)嵌套的用法?！咀鳂I(yè)2】從鍵盤輸入一個正整數(shù)n，

4、利用求的近似值，n為求和的總項數(shù)。考核點：發(fā)現(xiàn)公式中的計算規(guī)律（即計算邏輯）?！咀鳂I(yè)3】百錢百雞問題：公雞每只5元、母雞每只3元、小雞3只1元，用100元錢買100只雞，求公雞、母雞、小雞的只數(shù)?？己它c1：多重循環(huán)的使用?？己它c2：提煉和化簡計算邏輯，將多重循環(huán)改進為單重循環(huán)?！镜?課】【作業(yè)1】將輸入的一個偶數(shù)n(n>=6)分解為兩個素數(shù)之和。例如8=5+3?！咀鳂I(yè)2】有n個人圍成一圈，順序排號。從第一個人開始報數(shù)（從1到3報數(shù)），凡報到3的人退出圈子，請輸出這n個人退出圈子的整個次序?！镜?課】【作業(yè)1】將一個n×n方陣就地轉置，即行列元素互換。（1）擴展成矩陣轉置，將一個

5、矩陣a(m×n)轉置成一個新矩陣b(n×m)?！咀鳂I(yè)2】建立如下的楊輝三角，行數(shù)n由鍵盤輸入。（1）分析出楊輝三角形中每個元素的計算邏輯。（2）使用System.out.printf()方法進行格式化輸出。【第9課】【作業(yè)1】回文串：輸入一個字符串，判斷其是否為回文串并輸出結果。回文串是指從左向右讀與從右向左讀都相同的一個字符串，如12a3a21就是一個回文串?！咀鳂I(yè)2】超大整數(shù)求和：編寫一個Java程序，能對輸入的兩個超大非負整數(shù)求和。例如：輸入“12345678”和“111”，其和為“12345789”。（1）每個超大非負整數(shù)以字符串形式存儲。（2）求和的結果也以字符串

6、形式存儲?！咀鳂I(yè)3】將一個正整數(shù)（萬以內的數(shù)字）的每一位數(shù)值轉換成中文中的數(shù)值表示（如將 5036 轉換成“伍仟零叁拾陸”）。（1）使用數(shù)據(jù)表來簡化轉換邏輯。（2）注意邏輯思維的嚴密性。一組轉換數(shù)據(jù)樣例（萬以內的數(shù)字）數(shù)字串漢字串0零100壹佰90000玖萬90001玖萬零壹90500玖萬零伍佰91002玖萬壹仟零貳90070玖萬零柒拾90055玖萬零伍拾伍90909玖萬零玖佰零玖90990玖萬零玖佰玖拾【第10課】【作業(yè)1】編寫一個Java程序，定義Java靜態(tài)方法實現(xiàn)下面數(shù)學分段函數(shù)并進行驗證?！咀鳂I(yè)2】編寫一個Java靜態(tài)方法，將一個m*n矩陣轉置成一個n*m矩陣?！咀鳂I(yè)3】輸入一個數(shù)字

7、a，求S=a+aa+aaa+aaaa+aaaaa的和。例如，a=2，則S=2+22+222+2222+22222。（1）學會發(fā)現(xiàn)問題中的共性以分解問題。（2）理解解決同一問題的多種邏輯思維?！镜?1課】【作業(yè)1】編寫一個Java程序，輸出21000以內的全部完數(shù)。一個完數(shù)恰好等于其全部因子之和。例如6=1+2+3，故6是一個完數(shù)，28=1+2+4+7+14，故28也是一個完數(shù)。要求采用模塊化程序設計解決此類問題。【作業(yè)2】編寫函數(shù)完成下列每種數(shù)制轉換：（1）十進制正整數(shù)à二進制正整數(shù)。（2）十進制正整數(shù)à十六進制正整數(shù)。（3）十進制正整數(shù)à八進制正整數(shù)。要求采用模

8、塊化程序設計解決此類問題，發(fā)現(xiàn)數(shù)制轉換中的共性規(guī)律?！咀鳂I(yè)3】從鍵盤輸入一個棋盤的行數(shù)和列數(shù)，打印出棋盤的樣子。（1） 分析打印棋盤的整個過程，發(fā)現(xiàn)其中的邏輯步驟。（2） 編寫方法實現(xiàn)不同的邏輯步驟?！镜?2課】【作業(yè)1】漢諾塔問題：有n個盤子依其半徑大小套在柱子A上，其中半徑大的在底下，柱子B和C沒套盤子?，F(xiàn)要將A上的盤子全部搬運到C上（借助B），移動規(guī)則是每次只能移動一個盤子，并且不允許將大盤子壓在小盤子的上面。（1）分析歸納出搬運n個盤子的遞歸規(guī)律，編寫遞歸方法。（2）輸出完整的搬運過程以及移動盤子的總次數(shù)。【作業(yè)2】編寫一個Java程序，輸入兩個正整數(shù)m和n，輸出m和n的最大公約數(shù)（g

9、reatest common divisor）和最小公倍數(shù)（Least Common Multiple）。（1）最大公約數(shù)gcd是指m和n的全部公共因子之積，最小公倍數(shù)lcm為m和n之積除以最大公約數(shù)gcd。（2）掌握計算最大公約數(shù)的遞推方法：輾轉相除法?！咀鳂I(yè)3】天平稱物：有四個砝碼，總重量是40克，砝碼的質量是整數(shù)，且各不相等。請確定它們的質量，使之能稱出1到40克之間任何整數(shù)質量的物體?！咀鳂I(yè)4】一個整數(shù)除以3余2，除以5余3，除以7余2，求這個整數(shù)?！镜?3課】【作業(yè)1】將二分查找算法改寫為遞歸形式?！咀鳂I(yè)2】編寫一個Java程序，從一個字符串中S中刪除所有和字符串T相同的子串，輸出刪

10、除后的結果。例如：S=“abcdabef”，T="ab"，則刪除后的結果S="cdef"?！咀鳂I(yè)3】編寫一個Java程序，求得所有包含在串S中而不包含在串T中的字符構成的新串R。例如：S=“aabcddef”，T="cf"，則R="aabdde"?！咀鳂I(yè)4】編寫一個Java程序，求得串S和串T中的一個最長公共子串R。例如：S=“aabcddef”，T="bcbcdd"，則R="bcdd"?！镜?4課】【作業(yè)1】改進冒泡排序算法，只要在一趟冒泡排序過程中不發(fā)生相鄰記錄的交換，則

11、整個排序過程就可以立即結束。【作業(yè)2】荷蘭國旗問題：設有一個僅由紅、白、藍三種顏色的條塊組成的條塊序列。請編寫一個時間復雜度為O(n)的算法，使得這些條塊按紅、白、藍的順序排好，即排成荷蘭國旗圖案?！咀鳂I(yè)3】烙餅排序問題（1）一次烙餅翻轉過程：（2）將最大的烙餅調整到最底端：（兩次翻轉）（3）對于n塊烙餅，最多翻轉2(n-1)即可排好順序。（4）假設一疊烙餅的半徑分別為20,22,30,18,19,25,20，則要翻轉多少次才能排好順序？請編寫出烙餅排序算法?！镜?5課】分治算法（任選一個作業(yè)）【作業(yè)1】給定由n個整數(shù)（可能有負整數(shù)）組成的序列(a1, a2, , an)，最大子段和問題要求該

12、序列形如 的最大值（1ijn），例如，序列(-20, 11, -4, 13, -5, -2)的最大子段和為 【作業(yè)2】在一個2k×2k 個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。要求輸出棋盤覆蓋后的效果?！镜?6課】減治算法（任選一個作業(yè)）【作業(yè)1】應用堆排序方法對一個記錄序列進行升序排列。其基本思想是：首先將待排序的記錄序列構造成一個堆，此時，堆頂記錄是堆中所有記錄的最大者，將它從堆中移走（通常將堆頂記錄

13、和堆中最后一個記錄交換），然后將剩余記錄再調整成堆，這樣又找出了次大記錄，以此類推，直到堆中只有一個記錄為止。【作業(yè)2】在n枚外觀相同的硬幣中，有一枚是假幣，并且已知假幣較輕。通過一架來任意比較兩組硬幣，從而得知兩組硬幣的重量是否相同，或者哪一組更輕一些，假幣問題要求設計一個高效的算法來檢測出這枚假幣。（1）一分為二想法：把n枚硬幣分成兩組，每組有n/2枚硬幣，如果n為奇數(shù)，就留下一枚硬幣，然后把兩組硬幣分別放到天平的兩端。如果兩組硬幣的重量相同，那么留下的硬幣就是假幣；否則，用同樣的方法對較輕的那組硬幣進行同樣的處理，因為假幣一定在較輕的那組里。（2）一分為三想法：【作業(yè)3】將數(shù)字旋轉方陣的

14、遞歸算法改為非遞歸算法?！镜?7課】動態(tài)規(guī)劃算法（任選一個作業(yè)）【作業(yè)1】數(shù)塔問題：從數(shù)塔的頂層出發(fā)，在每一個結點可以選擇向左走或向右走，一直走到最底層，要求找出一條路徑，使得路徑上的數(shù)值和最大。 【作業(yè)2】最長遞增子序列問題：在數(shù)字序列A=a1, a2, , an中按遞增下標序列(i1, i2, ik)（1i1< i2<< ikn）順序選出一個子序列B，如果子序列B中的數(shù)字都是嚴格遞增的，則子序列B稱為序列A的遞增子序列。最長遞增子序列問題就是要找出序列A的一個最長的遞增子序列。例如，對于序列A=5, 2, 8, 6, 3, 6, 9, 7，其最長遞增子序列分別是2, 3,

15、 6, 9和2, 3, 6, 7?！咀鳂I(yè)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課】貪心算法（任選一個作業(yè)）【作業(yè)1】背包問題：給定n種物品和

16、一個容量為C的背包，物品i的重量是wi，其價值為vi，背包問題是如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大? （1）注意背包問題與0/1背包問題的區(qū)別。（2）貪心策略：優(yōu)先選擇單位重量價值最大的物品。【作業(yè)2】多機調度問題：設有n個獨立的作業(yè)1, 2, , n，由m臺相同的機器M1, M2, , Mm進行加工處理，作業(yè)i所需的處理時間為ti（1in），每個作業(yè)均可在任何一臺機器上加工處理，但不可間斷、拆分。多機調度問題要求給出一種作業(yè)調度方案，使所給的n個作業(yè)在盡可能短的時間內由m臺機器加工處理完成。（1）貪心策略：按照最長處理時間作業(yè)優(yōu)先。（2）例如，設7個獨立作業(yè)1, 2, 3, 4, 5, 6, 7由3臺機器M1, M2, M3加工處理，各作業(yè)所需的處理時間分別為2, 14, 4, 16, 6, 5, 3。則調度過程如下圖：【第19課】回溯算法（任選一個作業(yè)）【作業(yè)1】素數(shù)環(huán)問題：把整數(shù)1, 2, , 20填寫到一個環(huán)中，要求每個整數(shù)只填寫一次，并且相鄰的兩個整數(shù)之和是一個素數(shù)。1234【作業(yè)2】批處理作業(yè)調度問題：n個作業(yè)1, 2, , n要在兩臺機器上處理，每個作業(yè)必須先由機器1處理，然后再由機