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

ข้อย่อย 1

อินพุต: ลำดับของจำนวนเต็มที่มีความยาว $n\,$

เอาพุต: ลำดับย่อยของลำดับที่เป็นอินพุตที่มีความยาวมากที่สุด และเป็นลำดับเลขคณิต

แนวคิด ข้อนี้วัตถุที่เราต้องการหาคือลำดับย่อย ตำแหน่งเริ่มต้น $i\,$และตำแหน่งสุดท้าย $j\,$ในลำดับที่ให้มา โดยที่ $i\leq j\,$หรือคือช่วงที่เราเรียนกันไปแล้วในห้องเรียนนั่นเอง และเงื่อนไข คือต้องเป็นลำดับเลขคณิต(ที่มีความยาวมากที่สุด) ดังนั้นสิ่งที่อัลกอริทึมของเราต้องทำ คือหยิบช่วงแต่ละช่วง (ลำดับย่อยแต่ละลำดับ) มาดู แล้วดูว่ามันเป็นลำดับเลขคณิตหรือไม่ ถ้าใช่ก็ตรวจสอบอีกว่า มันเป็นลำดับเลขคณิตที่เราเคยรู้จักและยาวกว่าหรือไม่ ถ้ายาวกว่าก็เปลี่ยนมาจำลำดับย่อยใหม่นี้

จากแนวคิดข้างต้น เขียนเป็น pseudocode ได้ดังนี้

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