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

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

2009-09-04T09:47:58Z

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

2009-08-19T08:43:37Z

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

2009-08-19T08:42:22Z

Aoy: หน้าที่ถูกสร้างด้วย 'อินพุต: ลำดับของจำนวนเต็ม $n \,$ จำนวน และช่วง $[p,q]…'$

2009-08-19T08:31:00Z

หน้าที่ถูกสร้างด้วย 'อินพุต: ลำดับของจำนวนเต็ม <math>n \,</math> จำนวน และช่วง<math>[p,q]…'

หน้าใหม่

อินพุต: ลำดับของจำนวนเต็ม <math>n \,</math> จำนวน และช่วง<math>[p,q]\,</math>

เอาพุต: จำนวนของลำดับย่อยที่มีพิสัยในช่วง<math>[p,q]\,</math>

แนวคิด ข้อนี้วัตถุที่เราสนใจคือ ช่วง เรามีวิธีในการหาช่วงแล้วในห้องเรียน เราจะใช้วิธีนั้นกัน ค่าของวัตถุที่เราสนใจก็คือ การนำค่ามากที่สุดในช่วง มาลบกับค่าที่น้อยที่สุดในช่วง ซึ่งวิธีในการหาค่ามากที่สุด กับน้อยที่สุดเราก็เรียนไปแล้วในห้องเรียน และเงื่อนไขในข้อนี้คือ พิสัยอยู่ในช่วง <math>[p,q]\,</math> ดังนั้นเมื่อได้พิสัยของแต่ละช่วงมาแล้ว เราก็ต้องนำมาตรวจสอบว่าอยู่ในช่วงดังกล่าวหรือไม่ ถ้าอยู่ที่เพิ่มตัวนับจำนวนขึ้นไปเรื่อย ๆ

เวลาการทำงานของอัลกอริทึม การหยิบลำดับย่อยแต่ละลำดับมาดู เราใช้ for loop สองชั้น และการคำนวณค่าพิสัยของแต่ละลำดับย่อยใช้เวลาอีก <math>O(n) \,</math> ดังนั้นเวลารวมของสองขั้นตอนนี้คือ<math>O(n^3) \,</math> ส่วนการตรวจสอบว่าค่าพิสัยของลำดับย่อยอยู่ในช่วง <math>[p,q] \,</math> หรือไม่ใช้เวลาอีก <math>q-p+1 \, </math> ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น <math>O(n^3) \,</math>

@@ แถว 7: / แถว 7: @@
 จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้
 FINDMAX(A,i,j)
-:max<-- -1000000
-:for k=i to i<=j
+    max<-- -1000000
-::if A[k] > max
+    for k=i to i<=j
-::: max= A[k]
-::: max_k=k
+        if A[k] > max
-: return max_k
 FINDMIN(A,i,j)
-:min<-- 1000000
-:for k=i to k<=j
+     min<-- 1000000
-::if A[k] < min
+     for k=i to k<=j
-::: min= A[k]
-::: min_k=k
+         if A[k] < min
-: return min_k
 COUNTINTERVAL(A,n)
-:count <-- 0
-:for i=0 to i<n
+     count <-- 0
-:: for j=i to j<n
+     for i=0 to i<n
-::: max=FINDMAX(A,i,j)
-::: min=FINDMIN(A,i,j)
+         for j=i to j<n
-::: r=max-min
-::: for k=p to k<=q
+            max=FINDMAX(A,i,j)
-:::: if r=k
+            min=FINDMIN(A,i,j)
-:::::   count <-- count + 1
+            r=max-min
-: return count
+            for k=p to k<=q
 เวลาการทำงานของอัลกอริทึม การหยิบลำดับย่อยแต่ละลำดับมาดู เราใช้ for loop สองชั้น และการคำนวณค่าพิสัยของแต่ละลำดับย่อยใช้เวลาอีก <math>O(n) \,</math> ดังนั้นเวลารวมของสองขั้นตอนนี้คือ<math>O(n^3) \,</math> ส่วนการตรวจสอบว่าค่าพิสัยของลำดับย่อยอยู่ในช่วง <math>[p,q] \,</math> หรือไม่ใช้เวลาอีก <math>q-p+1 \, </math> ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น <math>O(n^3) \,</math>

@@ แถว 33: / แถว 33: @@
 :::: if r=k
 :::::   count <-- count + 1
-::: return count
+: return count
 เวลาการทำงานของอัลกอริทึม การหยิบลำดับย่อยแต่ละลำดับมาดู เราใช้ for loop สองชั้น และการคำนวณค่าพิสัยของแต่ละลำดับย่อยใช้เวลาอีก <math>O(n) \,</math> ดังนั้นเวลารวมของสองขั้นตอนนี้คือ<math>O(n^3) \,</math> ส่วนการตรวจสอบว่าค่าพิสัยของลำดับย่อยอยู่ในช่วง <math>[p,q] \,</math> หรือไม่ใช้เวลาอีก <math>q-p+1 \, </math> ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น <math>O(n^3) \,</math>

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

	แนวคิด ข้อนี้วัตถุที่เราสนใจคือ ช่วง เรามีวิธีในการหาช่วงแล้วในห้องเรียน เราจะใช้วิธีนั้นกัน ค่าของวัตถุที่เราสนใจก็คือ การนำค่ามากที่สุดในช่วง มาลบกับค่าที่น้อยที่สุดในช่วง ซึ่งวิธีในการหาค่ามากที่สุด กับน้อยที่สุดเราก็เรียนไปแล้วในห้องเรียน และเงื่อนไขในข้อนี้คือ พิสัยอยู่ในช่วง <math>[p,q]\,</math> ดังนั้นเมื่อได้พิสัยของแต่ละช่วงมาแล้ว เราก็ต้องนำมาตรวจสอบว่าอยู่ในช่วงดังกล่าวหรือไม่ ถ้าอยู่ที่เพิ่มตัวนับจำนวนขึ้นไปเรื่อย ๆ		แนวคิด ข้อนี้วัตถุที่เราสนใจคือ ช่วง เรามีวิธีในการหาช่วงแล้วในห้องเรียน เราจะใช้วิธีนั้นกัน ค่าของวัตถุที่เราสนใจก็คือ การนำค่ามากที่สุดในช่วง มาลบกับค่าที่น้อยที่สุดในช่วง ซึ่งวิธีในการหาค่ามากที่สุด กับน้อยที่สุดเราก็เรียนไปแล้วในห้องเรียน และเงื่อนไขในข้อนี้คือ พิสัยอยู่ในช่วง <math>[p,q]\,</math> ดังนั้นเมื่อได้พิสัยของแต่ละช่วงมาแล้ว เราก็ต้องนำมาตรวจสอบว่าอยู่ในช่วงดังกล่าวหรือไม่ ถ้าอยู่ที่เพิ่มตัวนับจำนวนขึ้นไปเรื่อย ๆ
		+
		+	จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้
		+
		+	FINDMAX(A,i,j)
		+	:max<-- -1000000
		+	:for k=i to i<=j
		+	::if A[k] > max
		+	::: max= A[k]
		+	::: max_k=k
		+	: return max_k
		+
		+	FINDMIN(A,i,j)
		+	:min<-- 1000000
		+	:for k=i to k<=j
		+	::if A[k] < min
		+	::: min= A[k]
		+	::: min_k=k
		+	: return min_k
		+
		+	COUNTINTERVAL(A,n)
		+	:count <-- 0
		+	:for i=0 to i<n
		+	:: for j=i to j<n
		+	::: max=FINDMAX(A,i,j)
		+	::: min=FINDMIN(A,i,j)
		+	::: r=max-min
		+	::: for k=p to k<=q
		+	:::: if r=k
		+	::::: count <-- count + 1
		+	::: return count

	เวลาการทำงานของอัลกอริทึม การหยิบลำดับย่อยแต่ละลำดับมาดู เราใช้ for loop สองชั้น และการคำนวณค่าพิสัยของแต่ละลำดับย่อยใช้เวลาอีก <math>O(n) \,</math> ดังนั้นเวลารวมของสองขั้นตอนนี้คือ<math>O(n^3) \,</math> ส่วนการตรวจสอบว่าค่าพิสัยของลำดับย่อยอยู่ในช่วง <math>[p,q] \,</math> หรือไม่ใช้เวลาอีก <math>q-p+1 \, </math> ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น <math>O(n^3) \,</math>		เวลาการทำงานของอัลกอริทึม การหยิบลำดับย่อยแต่ละลำดับมาดู เราใช้ for loop สองชั้น และการคำนวณค่าพิสัยของแต่ละลำดับย่อยใช้เวลาอีก <math>O(n) \,</math> ดังนั้นเวลารวมของสองขั้นตอนนี้คือ<math>O(n^3) \,</math> ส่วนการตรวจสอบว่าค่าพิสัยของลำดับย่อยอยู่ในช่วง <math>[p,q] \,</math> หรือไม่ใช้เวลาอีก <math>q-p+1 \, </math> ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น <math>O(n^3) \,</math>

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

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

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

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

Aoy: หน้าที่ถูกสร้างด้วย 'อินพุต: ลำดับของจำนวนเต็ม n \, จำนวน และช่วง[p,q]…'

Aoy: หน้าที่ถูกสร้างด้วย 'อินพุต: ลำดับของจำนวนเต็ม $n \,$ จำนวน และช่วง $[p,q]…'$