實作輔導 本周5/5(六)安排實作輔導 二時段: 周六 11:00~12:30 周六13:30~15:30.

Presentation on theme: "實作輔導 本周5/5(六)安排實作輔導 二時段: 周六 11:00~12:30 周六13:30~15:30."— Presentation transcript:

1 實作輔導 本周5/5(六)安排實作輔導 二時段: 周六 11:00~12:30 周六13:30~15:30

2 搶答!!

3 Q1 : 印出結果? int x=10, y=15; int s=0; while (x>y) { x--; while (x%2==1 && s<3) s++; } System.out.println("x="+x+"s="+s);

4 Q2 : 印出結果? x=10; y=15; s=20; for(;x>=5;x--) for(;y<=20;y++) s--; System.out.println("x="+x+"y="+y+"s="+s);

5 Self-regulated learning
import java.util.Scanner; public class nested_looptest1 { static Scanner input = new Scanner(System.in); public static void main(String[] args) { int x=10, y=15; int s=0; while (x>y) { x--; while (x%2==1 && s<3) s++; } System.out.println("x="+x+"s="+s); x=10; y=15; s=20; for(;x>=5;x--) for(;y<=20;y++) s--; System.out.println("x="+x+"y="+y+"s="+s); }//main //x=10s=0 //x=4y=21s=14 }//class_loop1

6 迴圈LOOP應用 II 輾轉相除法 輾轉相減法 判斷迴文(palindrome): 複習
求兩個整數的最大公因數(greatest common divisor, GCD): II 輾轉相除法 輾轉相減法 字元金字塔 : Nested for loop

7 複習 palindrome迴文 2017/1/2 line

8 palindrome迴文 str1.length()==5 輸入字串 str1.length() :字串長度
輸入字串，判斷是否為迴文? 迴文 ABCBA ABBA 不是迴文 ABCBB 輸入字串 Scanner input = new Scanner(System.in); String str1 = input.nextLine(); str1.length() :字串長度 str1.charAt(i):取得字串第i個字元(character) i: 0~ str1.length()-1 A B C str1 str1.length()==5 i=0 i=1 i=2 i=3 i=4 str1.charAt(4) str1.charAt(0)

9 取得字串第i個字元(character)

10 輸入字串，判斷是否為迴文?奇數個字元為例 str1 A B C
left=0;right=str1.length()-1; boolean palindrome=true; while (left<right) { if (str1.charAt(left)!=str1.charAt(right)) {palindrome=false; break;} left++; right--; }//while if (palindrome) dif="是迴文!“; else dif="不是迴文!"; System.out.println(+dif); // != 不等於 奇數個字元 Left=0; right=4:比較str1.charAt(0)、 str1.charAt(4) Left=1; right=3:比較str1.charAt(1)、 str1.charAt(3) Left=2; right=2:比較str1.charAt(2)、 str1.charAt(2) Left=3; right=1;  left >right  離開loop left right A B C str1

11 輸入字串，判斷是否為迴文?偶數個字元為例 str1 A B C
left=0;right=str1.length()-1; boolean palindrome=true; while (left<right) { if (str1.charAt(left)!=str1.charAt(right)) {palindrome=false; break;} left++; right--; }//while if (palindrome) dif="是迴文!“; else dif="不是迴文!"; System.out.println(+dif); // != 不等於 偶數個字元 Left=0; right=5: 比較str1.charAt(0)、 str1.charAt(5) Left=1; right=4:比較str1.charAt(1)、 str1.charAt(4) Left=2; right=3:比較str1.charAt(2)、 str1.charAt(3) Left=3; right=2;  left >right  離開loop left right A B C str1

12 求兩個整數的最大公因數(greatest common divisor, GCD) :II
從2開始找， 直到能整除兩個整數的最大正整數 何時結束 (不會超過兩個整數的最小整數) 200, 40的GCD 輾轉相除法 (本回) 輾轉相減法 (本回) 最小公倍數(LCM): n1*n2/gcd

13 求兩個整數GCD的方法2: 輾轉相除法 輾轉相除法，又稱歐幾里得算法（Euclidean algorithm）
兩個整數的最大公因數(greatest common divisor)是能夠同時整除 它們的最大的正整數

14 求GCD(52,240) 52/240=0 ………………52 240/52=4………………..32 1 2 52 240 32 20 12 8 240 208 32 20 12 8 4 4 1 ①　 ②52x4　 ③　 ④　 ⑤　 ⑥ 4*2 gcd

15 求兩個整數GCD的方法2: 輾轉相除法 gcd=m; 輾轉相除法，又稱歐幾里得算法（Euclidean algorithm）
兩個整數的最大公因數(greatest common divisor)是能夠同時整除它們的最大的正整數 int t,m,n; m=n1; n=n2; do { t=m%n; m=n; //除數變被除數 n=t; //餘數變除數 } while (n!=0); //除數不可為0 gcd=m; System.out.println("輾轉相除法: GCD("+n1+","+n2+")="+gcd); System.out.println("輾轉相除法: LCM("+n1+","+n2+")="+n1*n2/gcd);

16 求GCD(52,240) do { t=m%n; m=n; n=t; gcd } while (n!=0); gcd=m; 52 240
輾轉相除法 步驟 M (被除數) N (除數) t=m%n (取餘數) m=n(除數變成被除數) n=t(餘數變成除數) 條件 (n!=0) (1) 52 240 n=240 n=52 true (2) 32 (3) 20 (4) 12 (5) 8 (6) 4 (7) t=8%4 ==0 m=4 n=0 False 結束loop GCD=4 52 240 32 20 12 8 208 4 1 2 ①　 ②52x4　 ③　 ④　 ⑤　 ⑥ 4*2 gcd do { t=m%n; m=n; n=t; } while (n!=0); gcd=m;

17 步驟 m (被減數) n (減數) m=m-n n(減數不變) 條件 (m!=n) (1) 240 52 188 m>n true (2) 136 (3) 84 (4) 32 n=n-m m(減數不變) (5) 20 m<n (6) 12 (7) (8) 8 (9) 4 (10) False 求兩個整數GCD的方法3: 輾轉相減法 m=n1; n=n2; while (m!=n) { while (m>n) m=m-n; while (m<n) n=n-m; } gcd=m; // gcd=n; GCD=4

18 求兩個整數GCD的方法3: 輾轉相減法 m=n1; n=n2; while (m!=n) { while (m>n) m=m-n; while (m<n) n=n-m; } gcd=m; System.out.println("輾轉相減法: GCD("+n1+","+n2+")="+gcd); System.out.println("輾轉相減法: LCM("+n1+","+n2+")="+n1*n2/gcd+"\n");

19 檢討GCD方法 求兩個整數GCD的方法: 從2開始找， 直到能整除兩個整數的最大正整數 輾轉相除法 輾轉相減法
2~min(n1,n2)==min(n1-1, n2-1) 輾轉相除法 輾轉相減法 那些較好?那些暴力法(brute force)? 速度快

20 Demo: GCD的方法2

21 字元金字塔 Nested for loop

22 主題：字元金字塔 - 斜金字塔 利用迴圈印出 「 * 」，逐行增 加印出個數，直到印出7層斜 金字塔。 本題利用到巢狀迴圈的概念
巢狀迴圈為迴圈範圍內又有迴 圈，從外層來看，內層迴圈只 屬與外層迴圈內的動作。因此 外層迴作用，內層迴圈開始運 作到執行結束後，又回到外層 迴圈。 執行結果

23 主題：字元金字塔 - 斜金字塔 追蹤nested for loop程式 外層 i 內層 j 初值 條件 j<=i 執行次數 結果
內迴圈執行1次 印1顆*、換行 i=2 j<=2 內迴圈執行2次 印2顆*、換行 i=3 j<=3 內迴圈執行3次 印3顆*、換行 i=4 j<=4 內迴圈執行4次 印4顆*、換行 i=5 j<=5 內迴圈執行5次 印5顆*、換行 i=6 j<=6 內迴圈執行6次 印6顆*、換行 i=7 j<=7 內迴圈執行7次 印7顆*、換行 i=8,外迴圈結束 執行結果

24 輸入n層， 印出n層三角形 (3層loop)

25 第11周習題: 輸入n1, n2, n3，求三整數之GCD 須能重複執行 繳交”設計歷程”檔及.java