Home » Forums » Other Topics » Other Topics

ตอบ : ให้หา max sum ของ sub-array ด้วย ML

Submitted by jittat on 25 July, 2007 - 15:12

เขียนข้อแรกมาเป็น ML

การทำงานจะแตกต่างจากของพี่ป๊อกตรงที่ไม่ได้พยายามหาทุก ๆ sublist ออกมาก่อน แต่ว่าวิ่งคำนวณไปเลย

fun max(x,y) = if x>y then x else y;
 
fun maxsublist(l) =
    let
	fun itr([]) = (0,[],0,[])
	  | itr(x::xs) = let
		val (next_sum, next_list, best, bestlist) = itr(xs)
		val new_next_sum = max(next_sum + x,0)
		val new_next_list = if new_next_sum>0 then
					x::next_list
				    else
					[]
	    in
		if best>new_next_sum then
		    (new_next_sum, new_next_list, best, bestlist)
		else
		    (new_next_sum, new_next_list, new_next_sum, new_next_list)
	    end;
 
      val (_,_,best,bestlist) = itr(l);
    in
	(best,bestlist)
    end

จริง ๆ วิธีนี้ไม่ได้ดูซับซ้อนเท่ากับโค้ด ML ที่เขียน ดูอธิบายเป็นโค้ดลำลองได้ที่ Solution 4 (หน้า 7) ใน
http://www.cs.ucf.edu/~reinhard/classes/cop3503/mcss.pdf
ในนั้นมีวิธีทำแบบอื่น ๆ อีก 3 แบบ

สังเกตว่าที่เขียนนี่ ไม่ทราบว่าจะเรียกว่าคิดแบบ functional หรือเปล่า คือ ฟังก์ชันนี้จริง ๆ คือฟังก์ชัน itr (ใช้ชื่อนี้เพราะว่าคิดชื่ออื่นไม่ออก พยายามจะใช้เพื่อหมายถึงการ iterate ไปใน list) ซึ่งเป็นการเขียน solution 4 ข้างต้นแบบ recursion เท่านั้นเอง (สังเกตว่าในโปรแกรมมีการ "ส่งต่อ" คำตอบจากปัญหาก่อนเสียวุ่นวาย กล่าวคือ จะคืน ค่าผลรวมของตัวที่คิดมาถึงตัวก่อนหน้า, ลิสต์ของตัวเลขที่ทำให้ได้ผลรวมเหล่านั้น, ค่าผลรวมที่ดีที่สุด, และ ลิสต์ของตัวเลขที่ทำให้ได้ผลรวมที่ดีที่สุด)

‹ Cert: อยากจะสอบ RHCE จะต้องทำยังไงบ้าง LOAD DATA INFILE ของ mysql ›
»
Submitted by pphetra on 27 July, 2007 - 13:10.

o(n) เขียนเป็น pure functional ยากจริงๆ
ลองเขียนเองแล้วไม่รอด
ลอกของอาจารย์มะนาวดีกว่า

ลองเปลี่ยนไปใช้ พวก foldl มาช่วย

maxsublist (x:xs) = lst
    where (_,_,_,lst) = foldl aux (0,[],0,[]) xs
 
aux (next_sum, next_list, best, best_list) x
    | best > new_next_sum  = (new_next_sum, new_next_list, best, best_list)
    | otherwise            = (new_next_sum, new_next_list, new_next_sum, new_next_list)
    where new_next_sum  = max (next_sum + x) 0
          new_next_list = if new_next_sum > 0 then x:next_list else []
»
Submitted by xce1 on 27 September, 2007 - 15:23.
xce1's picture

ข้อนี้ผมใช้วิธีห่ามๆ เลยนะ แบบว่าไม่คำนึงถึงประสิทธิภาพ ใช้ ML เขียน

function result=maxsum(a)
startflag=1;
for i = 1:length(a)
    sum=0;
    for j = i:length(a)
        sum=sum+a(j);
        if (startflag=1)
            max_sum=sum;
            startflag=0;
            first=i;
            last=j;
        else
            if (sum > max_sum)
                max_sum = sum;
                first=i;
                last=j;
            end
        end
    end
end
result=[first last max_sum];

โดยที่ first คือ index ของ sublist ตัวต้น และ last คือ index ของ sublist ตัวสุดท้าย

»
Submitted by sugree on 27 September, 2007 - 15:33.
sugree's picture

ML ดูอ่านง่าย มองผ่านๆ นึกว่า python ถ้าตัด end ออกไปก็ยิ่งเหมือน

»
Submitted by xce1 on 27 September, 2007 - 17:15.
xce1's picture

ML ของผมหมายถึง Matlab นะครับ ไปดู code ข้างบนถึงรู้ว่าคนละ ML (เอ๊ะ หรือว่าอันเดียวกัน)

»
Submitted by sugree on 27 September, 2007 - 22:11.
sugree's picture

ถึงว่า คล้ายกันจัง คนละ ML นี่เอง

»

ย้าย Codenone

ประกาศย้าย Codenone ไปใช้ Forum ของ Blognone แทนครับ ตามไปตั้งกระทู้ต่อได้ที่ Codenone Forum (รายละเอียดอ่านจากกระทู้ ย้าย Codenone ไปรวมกับ Blognone)

กระทู้เก่าๆ จะย้ายตามไปในภายหลัง ตอนนี้ปิดการโพสต์กระทู้ไว้ เหลือไว้เฉพาะอ้างอิงเท่านั้น