418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 5 - ประวัติรุ่นแก้ไข

Aoy เมื่อ 09:41, 4 กันยายน 2552

2009-09-04T09:41:00Z

Aoy: /* ข้อย่อย 1 */

2009-08-18T09:16:04Z

ข้อย่อย 1

Aoy: /* ข้อย่อย 1 */

2009-08-18T09:15:09Z

ข้อย่อย 1

Aoy เมื่อ 09:14, 18 สิงหาคม 2552

2009-08-18T09:14:13Z

Aoy: /* ข้อย่อย 1 */

2009-08-18T09:13:25Z

ข้อย่อย 1

Aoy: /* ข้อย่อย 2 */

2009-08-18T09:11:38Z

ข้อย่อย 2

Aoy: /* ข้อย่อย 2 */

2009-08-18T09:09:36Z

ข้อย่อย 2

Aoy: /* ข้อย่อย 2 */

2009-08-18T08:54:06Z

ข้อย่อย 2

Aoy: /* ข้อย่อย 1 */

2009-08-18T08:43:39Z

ข้อย่อย 1

Aoy เมื่อ 08:31, 18 สิงหาคม 2552

2009-08-18T08:31:55Z

@@ แถว 8: / แถว 8: @@
 จากแนวคิดข้างต้น เขียนเป็น pseudocode ได้ดังนี้
 ABS(x,y) // เป็น subroutine ที่ใช้ในการหาผลต่างระหว่างเลขสองตัว
-:if (x-y < 0)
-:: return ((-1).(x-y))
+    if (x-y < 0)
-: return(x-y)
+        return ((-1).(x-y))
 CHECK_ARITH(A,i,j) // เป็น subroutine ที่ใช้ในการตรวจสอบว่าลำดับย่อยในช่วง i ถึง j เป็นลำดับเลขคณิตหรือไม่
 LONGESTINTERVAL(A,n,maxi,maxj)
-:max = -10000000
-:for i=o to i=n
+     max = -10000000
-:: for j=i to j = n
+     for i=o to i=n
-:::   flag=CHECK_ARITH(A,i,j) // ตรวจสอบว่าลำดับย่อยที่กำลังพิจารณาเป็นลำดับเลขคณิตหรือไม่
-:::   if (flag) // ถ้าเป็นลำดับเลขคณิต
+          for j=i to j = n
-::::     if ((j-i+1)> max) // ตรวจสอบดูว่าความยาวของลำดับเลขคณิตนี้ยาวกว่าลำดับเลขคณิตก่อนหน้าที่เคยเจอหรือไม่
-::::     maxi = i  // ถ้าใช่ก็เปลี่ยนไปจำลำดับเลขคณิตที่ยาวกว่าลำดับก่อนหน้านี้
+               flag=CHECK_ARITH(A,i,j) // ตรวจสอบว่าลำดับย่อยที่กำลังพิจารณาเป็นลำดับเลขคณิตหรือไม่
-::::     maxj = j
+                              if (flag) // ถ้าเป็นลำดับเลขคณิต
 == ข้อย่อย 2 ==
@@ แถว 35: / แถว 57: @@
 จากแนวคิดข้างต้นสามารถ เขียนเป็น pseudocode ได้ดังนี้
 GENERATE(A,D,n,maxi,maxj)
-: l = 0, count = o
-:for k=o to k<n // ทำการหาค่าผลต่างของสมาชิกในลำดับย่อยเก็บไว้ในอะเรย์ D
+     l = 0, count = 0
-:: D[l] = ABS(A[k],A[k+1])
+     for k=0 to k<n // ทำการหาค่าผลต่างของสมาชิกในลำดับย่อยเก็บไว้ในอะเรย์ D
-:: l <-- l + 1
-:for k=o to k<n
+          D[l] = ABS(A[k],A[k+1])
-:: if (D[k] = D[k+1]) // ถ้าผลต่างของ A[k] กับ A[k+1] เท่ากับผลต่างของ A[k+1] กับ A[k+2]
+          l <-- l + 1
-::: count = count + 1
-::: maxi = k
+     for k=0 to k<n
-::: maxj = k+2
-:: count = 0
+          if (D[k] = D[k+1]) // ถ้าผลต่างของ A[k] กับ A[k+1] เท่ากับผลต่างของ A[k+1] กับ A[k+2]

@@ แถว 9: / แถว 9: @@
 ABS(x,y) // เป็น subroutine ที่ใช้ในการหาผลต่างระหว่างเลขสองตัว
-:1:if (x-y < 0)
+:if (x-y < 0)
-:2:: return ((-1).(x-y))
+:: return ((-1).(x-y))
-:3: return(x-y)
+: return(x-y)
 CHECK_ARITH(A,i,j) // เป็น subroutine ที่ใช้ในการตรวจสอบว่าลำดับย่อยในช่วง i ถึง j เป็นลำดับเลขคณิตหรือไม่

@@ แถว 9: / แถว 9: @@
 ABS(x,y) // เป็น subroutine ที่ใช้ในการหาผลต่างระหว่างเลขสองตัว
-:1if (x-y < 0)
+:1:if (x-y < 0)
-::2 return ((-1).(x-y))
+:2:: return ((-1).(x-y))
-:3 return(x-y)
+:3: return(x-y)
 CHECK_ARITH(A,i,j) // เป็น subroutine ที่ใช้ในการตรวจสอบว่าลำดับย่อยในช่วง i ถึง j เป็นลำดับเลขคณิตหรือไม่
-:1 k = ABS(A[i],A[i+1]) // กำหนดค่า k เป็นผลต่างระหว่างเลขตัวแรกกับตัวที่สองในลำดับย่อย
+: k = ABS(A[i],A[i+1]) // กำหนดค่า k เป็นผลต่างระหว่างเลขตัวแรกกับตัวที่สองในลำดับย่อย
-:2 for k=i+1 to k<j
+: for k=i+1 to k<j
-::3 if(ABS(A[k],A[k+1] != k)) // ถ้ามีตัวเลขของตัวในลำดับย่อยมีผลต่างไม่เท่ากับ k ก็บอกว่าลำดับย่อยในช่วง i ถึง j นี้ไม่เป็นลำดับเลขคณิต
+:: if(ABS(A[k],A[k+1] != k)) // ถ้ามีตัวเลขของตัวในลำดับย่อยมีผลต่างไม่เท่ากับ k ก็บอกว่าลำดับย่อยในช่วง i ถึง j นี้ไม่เป็นลำดับเลขคณิต
-:::4 retrun (0)
+::: retrun (0)
-::5 return(1)
+:: return(1)
 LONGESTINTERVAL(A,n,maxi,maxj)
 :max = -10000000
 :for i=o to i=n
 :: for j=i to j = n
 :::   flag=CHECK_ARITH(A,i,j) // ตรวจสอบว่าลำดับย่อยที่กำลังพิจารณาเป็นลำดับเลขคณิตหรือไม่
 :::   if (flag) // ถ้าเป็นลำดับเลขคณิต
 ::::     if ((j-i+1)> max) // ตรวจสอบดูว่าความยาวของลำดับเลขคณิตนี้ยาวกว่าลำดับเลขคณิตก่อนหน้าที่เคยเจอหรือไม่
 ::::     maxi = i  // ถ้าใช่ก็เปลี่ยนไปจำลำดับเลขคณิตที่ยาวกว่าลำดับก่อนหน้านี้
 ::::     maxj = j
 == ข้อย่อย 2 ==

@@ แถว 9: / แถว 9: @@
 ABS(x,y) // เป็น subroutine ที่ใช้ในการหาผลต่างระหว่างเลขสองตัว
-:if (x-y < 0)
+:1if (x-y < 0)
-:: return ((-1).(x-y))
+::2 return ((-1).(x-y))
-: return(x-y)
+:3 return(x-y)
 CHECK_ARITH(A,i,j) // เป็น subroutine ที่ใช้ในการตรวจสอบว่าลำดับย่อยในช่วง i ถึง j เป็นลำดับเลขคณิตหรือไม่
-: k = ABS(A[i],A[i+1]) // กำหนดค่า k เป็นผลต่างระหว่างเลขตัวแรกกับตัวที่สองในลำดับย่อย
+:1 k = ABS(A[i],A[i+1]) // กำหนดค่า k เป็นผลต่างระหว่างเลขตัวแรกกับตัวที่สองในลำดับย่อย
-: for k=i+1 to k<j
+:2 for k=i+1 to k<j
-:: if(ABS(A[k],A[k+1] != k)) // ถ้ามีตัวเลขของตัวในลำดับย่อยมีผลต่างไม่เท่ากับ k ก็บอกว่าลำดับย่อยในช่วง i ถึง j นี้ไม่เป็นลำดับเลขคณิต
+::3 if(ABS(A[k],A[k+1] != k)) // ถ้ามีตัวเลขของตัวในลำดับย่อยมีผลต่างไม่เท่ากับ k ก็บอกว่าลำดับย่อยในช่วง i ถึง j นี้ไม่เป็นลำดับเลขคณิต
-::: retrun (0)
+:::4 retrun (0)
-:: return(1)
+::5 return(1)
 LONGESTINTERVAL(A,n,maxi,maxj)

@@ แถว 9: / แถว 9: @@
 ABS(x,y) // เป็น subroutine ที่ใช้ในการหาผลต่างระหว่างเลขสองตัว
 :if (x-y < 0)
 :: return ((-1).(x-y))
 : return(x-y)
 CHECK_ARITH(A,i,j) // เป็น subroutine ที่ใช้ในการตรวจสอบว่าลำดับย่อยในช่วง i ถึง j เป็นลำดับเลขคณิตหรือไม่
 : k = ABS(A[i],A[i+1]) // กำหนดค่า k เป็นผลต่างระหว่างเลขตัวแรกกับตัวที่สองในลำดับย่อย
 : for k=i+1 to k<j
 :: if(ABS(A[k],A[k+1] != k)) // ถ้ามีตัวเลขของตัวในลำดับย่อยมีผลต่างไม่เท่ากับ k ก็บอกว่าลำดับย่อยในช่วง i ถึง j นี้ไม่เป็นลำดับเลขคณิต
 ::: retrun (0)
 :: return(1)
 LONGESTINTERVAL(A,n,maxi,maxj)
 :max = -10000000
 :for i=o to i=n
 :: for j=i to j = n
 :::   flag=CHECK_ARITH(A,i,j) // ตรวจสอบว่าลำดับย่อยที่กำลังพิจารณาเป็นลำดับเลขคณิตหรือไม่
 :::   if (flag) // ถ้าเป็นลำดับเลขคณิต
 ::::     if ((j-i+1)> max) // ตรวจสอบดูว่าความยาวของลำดับเลขคณิตนี้ยาวกว่าลำดับเลขคณิตก่อนหน้าที่เคยเจอหรือไม่
 ::::     maxi = i  // ถ้าใช่ก็เปลี่ยนไปจำลำดับเลขคณิตที่ยาวกว่าลำดับก่อนหน้านี้
 ::::     maxj = j
 == ข้อย่อย 2 ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:09, 18 สิงหาคม 2552
แถว 34:		แถว 34:

	จากแนวคิดข้างต้นสามารถ เขียนเป็น pseudocode ได้ดังนี้		จากแนวคิดข้างต้นสามารถ เขียนเป็น pseudocode ได้ดังนี้
		+
		+	GENERATE(A,D,n,maxi,maxj)
		+	: l = 0, count = o
		+	:for k=o to k<n // ทำการหาค่าผลต่างของสมาชิกในลำดับย่อยเก็บไว้ในอะเรย์ D
		+	:: D[l] = ABS(A[k],A[k+1])
		+	:: l <-- l + 1
		+	:for k=o to k<n
		+	:: if (D[k] = D[k+1])
		+	::: count = count + 1
		+	::: maxi = k
		+	::: maxj = k+1
		+	:: count = 0

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:54, 18 สิงหาคม 2552
แถว 31:		แถว 31:

	== ข้อย่อย 2 ==		== ข้อย่อย 2 ==
		+	โจทย์ต้องการให้อัลกอริทึมทำงานได้ในเวลา<math>O(n) \,</math> นั่นคือ พออ่านอินพุตเสร็จแล้วต้องทำการตรวจสอบได้ด้วยว่าเป็นลำดับเลขคณิตหรือไม่ พร้อมทั้งต้องหาช่วง(ลำดับย่อย)ที่เป็นลำดับเลขคณิตที่ยาวที่สุดได้ด้วย ซึ่งการทำงานดังกล่าวจะทำได้ เมื่อเราทำการคำนวณผลต่างระหว่างสมาชิกในลำดับไปพร้อม ๆ กับการหยิบสมาชิกแต่ละตัวมาดูนั่นเอง นั่นคือ เมื่อเราพิจารณาสมาชิกตัวที่หนึ่ง เราก็หาผลต่างของมันกับสมาชิกตัวที่สอง เมื่อพิจารณาสมาชิกตัวที่สอง เราก็หาผลต่างของมันกับสมาชิกตัวที่สาม ทำแบบนี้ไปเรื่อย ๆ เมื่อพิจารณาครบทุกตัว ตอนนี้เราก็จะมีผลต่างระหว่างสมาชิกทุกตัวในลำดับอินพุตแล้ว จากนั้นวิธีการตรวจสอบว่าเป็นลำดับเลขคณิตที่ยาวที่สุดหรือไม่ก็ทำได้โดยดูว่าค่าผลต่างพวกนี้เปลี่ยนหรือไม่ ถ้ายังไม่เปลี่ยนก็นับว่าเป็นลำดับเลขคณิตไปเรื่อย ๆ แต่ถ้าเปลี่ยนก็แสดงว่าไม่เป็นลำดับเลขคณิตแล้ว ตัวแปรที่ใช้ในการจำว่าตำแหน่งเริ่มของลำดับย่อยก็ต้องเปลี่ยนไป แล้วเริ่มนับความยาวใหม่นั่นเอง
		+
		+	จากแนวคิดข้างต้นสามารถ เขียนเป็น pseudocode ได้ดังนี้