MathCom_Algorithms_Exercise with Answer

แบบฝึกหัด

Algorithms

1. จงสร้าง algorithm เพื่อหาผลบวกของเลขจำนวนเต็มทุกตัวในรายการ(List)

-----------------------------------------------------------------

procedure Summation List(A1,A2,A3,.......,An : integers)

             sum := A1 {set sum equal the value of first element}

             for  i := 2 to n

                   sum := sum+Ai    {sum is the summation of all elements}

             return sum   {copy value of sum to function above}

-----------------------------------------------------------------

2.จงเขียน algorithm เพื่อเปลี่ยนค่าตัวแปร x และ y โดยใช้การกำหนดค่า (assignments) เพียงอย่างเดียว และตอบว่าต้องใช้การ

กำหนดค่ากี่ครั้ง

-----------------------------------------------------------------

procedure exchange value (x,y : integers)

             A := x     { 1times }

             x := y      { 1times }

             y := A     { 1times }

-----------------------------------------------------------------

     Answer : Time Complexity is 3 times

-----------------------------------------------------------------

3.จงเขียน algorithm เพื่อหาตำแหน่งของตัวเลขที่มีค่ามากที่สุดตัวเลขแรกในลิสต์ของจำนวนเต็ม โดยเลขจำนวนเต็มในลิสต์อาจซ้ำกันได้

-----------------------------------------------------------------

procedure location of max(A1,A2,A3,......,An : integers)

     max := A1 {set max equal the first element}

     for   i := 2  to  n   {do loop location of element from 2 to n}

           if   Ai > A1   then  max := Ai {consider to the value of max} 

     location := i   {copy location of max element}

     return location 

-----------------------------------------------------------------

4.จงเขียน algorithm ที่จะนับจำนวนเลข 1 ในบิตสตริงโดยพิจารณาแต่ละบิตของสตริงเพื่อตรวจสอบว่าเป็นเลข 1 หรือไม่       

-----------------------------------------------------------------

procedure Number of 1digit(A0,A1,A2,.....,An-1:character)
     {string array of An-1 = \o is NULL so we didn't count it}
     count := 0
     for i := 0 to n-2
           if Ai := 1 then count := count + 1 {add to count 1 if Ai = 1}
     return count

-----------------------------------------------------------------

5.จงแสดงว่าฟังก์ชั่นที่กำหนดให้ ข้อใดเป็น O(x²)

    a.f(x)=17x+11

-----------------------------------------------------------------

method of Big-O : |f(x)|<=c×|g(x)| ; x>=k

17x+11 <= c×x²  ;  x>=k

17x+11 <= 17x²+11x²   when x >=1

17x+11 <= 28x²  when  x >=1

=> c = 28 , k = 1

So : f(x) = 17x+11เป็น O(x²) #

-----------------------------------------------------------------

   b.f(x)= x²+1000

-----------------------------------------------------------------

method of Big-O : |f(x)|<=c×|g(x)| ; x>=k

x²+1000 <= c×x² when x >= k

x²+1000 <= x²+1000x² when x >= 1

x²+1000 <= 1001x² when x >= 1

=> c = 1001 , k = 1

So : f(x) = x²+1000เป็น O(x²) #

-----------------------------------------------------------------

   c.f(x)=x⁴/2

-----------------------------------------------------------------

we knew that f(x) is not big-o of x² so we use converse proof by 

proof x²=O(f(x)) if true mean that f(x) != O(x²) :

method of Big-O :

 x² <= c×x⁴/2 when x >= k

 x² <= 2×x⁴/2 when x >= 1

=> c = 2 , k = 1

So : f(x) = x⁴/2ไม่เป็น O(x²) #

-----------------------------------------------------------------

6.จงแสดงว่า 10n+8 เป็น O(n)

-----------------------------------------------------------------

method of Big-O :

10n+8 <= c×n when x >= k

10n+8 <= 10n+8n when x >= 1

10n+8 <= 18n when x >= 1

=> c = 18 , k = 1

So : 10n+8 เป็น O(n) #

-----------------------------------------------------------------

7.จงแสดงว่า n²+1 เป็น O(n²)

-----------------------------------------------------------------

method of Big-O :

n²+1 <= c×n² when x >= k

n²+1 <= n²+n² when x >= 1

n²+1 <= 2n² when x >= 1

=> c = 2 , k = 1

So : n²+1 เป็น O(n²) #

-----------------------------------------------------------------

8.จงแสดงว่า f(n) = n² + 2n + 1 เป็น O(n²)

-----------------------------------------------------------------

method of Big-O :

n²+2n+1 <= c×n² when x >= k

n²+2n+1 <= n²+2n²+n² when x >= 1

n²+2n+1 <= 4n² when x >= 1

=> c = 4 , k = 1

So : n²+2n+1 เป็น O(n²) #

-----------------------------------------------------------------

9.จงแสดงว่า f(n) = 4n³+2n²+n+5 คือ O(n³)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       

-----------------------------------------------------------------

method of Big-O :

4n³+2n²+n+5 <= c×n³ when x >= k

4n³+2n²+n+5 <= 4n³+2n³+n³+5n³ when x >= 1

4n³+2n²+n+5 <= 12n³ when x >= 1

=> c = 12 , k = 1

So : 4n³+2n²+n+5 เป็น O(n³) #

-----------------------------------------------------------------