อย่างตอนแรกเรามี abc เราก็จะทำ 3 รอบใช่ไหมครับ ก็คือรอบที่ a นำ รอบที่ b นำ และรอบที่ c นำ
ในรอบที่ a นำนั้นเราก็มีทางเลือกอีก ดังนั้นเราก็ต้องทำกับตัวที่เหลือก็คือ b นำและ c นำ และก็ทำแบบเดียวกันกับข้างบนด้วย
ดังนั้นเราได้ว่า
{syntaxhighlighter x}
หลัก -> เลือก a เหลือ bc
รอบรอง -> เลือก b ได้ ab เหลือ c
รอบรองรอง -> เลือก c ได้ abc ไม่เหลือแล้ว
รอบรอง -> เลือก c ได้ ac เหลือ b
รอบรองรอง -> เลือก b ได้ acb ไม่เหลือแล้ว
หลัก -> เลือก b เหลือ ac
รอบรอง -> เลือก a ได้ ba เหลือ c
รอบรองรอง -> เลือก c ได้ bac ไม่เหลือแล้ว
รอบรอง -> เลือก c ได้ bc เหลือ a
รอบรองรอง -> เลือก a ได้ bca ไม่เหลือแล้ว
หลัก -> เลือก c เหลือ ab
รอบรอง -> เลือก a ได้ ca เหลือ b
รอบรองรอง -> เลือก b ได้ cab ไม่เหลือแล้ว
รอบรอง -> เลือก b ได้ cb เหลือ a
รอบรองรอง -> เลือก a ได้ cba ไม่เหลือแล้ว
{/syntaxhighlighter}
ทีนี้เราไม่รู้ว่าเราจะทำกี่รอบ ดังนั้นจึงใช้วิธีสร้าง function ขึ้นมาและให้เรียกซ้ำไปเรื่อยๆ ถ้าความยาวเป็น 1 เมื่อไหร่ก็ไม่ต้องเรียกตัวเองต่อ
รหัสเทียมที่ได้ก็จะเป็นประมาณว่า
{syntaxhighlighter x}
function combi( ก่อนหน้า, ตัวที่เหลือ) :
if ตัวที่เหลือ ยาว 1:
print ก่อนหน้า + ตัวที่เหลือ
else
ความยาว = ตัวที่เหลือ ยาวเท่าไหร่
for i = 0 ถึง ความยาว - 1:
ตัวปัจจุบัน = ตัวที่เหลือ เอาเฉพาะตัวที่ i
ตัวที่เหลือใหม่ = ตัวที่เหลือ ไม่เอาเฉพาะตัวที่ i
// ตัดข้างหน้ากับข้างหลังมาต่อกัน แล้วเอาตรงกลางทิ้ง
combi( ก่อนหน้า+ตัวปัจจุบัน, ตัวที่เหลือใหม่);
endfor;
endfunction;
{/syntaxhighlighter}
แนะนำให้ทำเป็น recursive ครับ แบบเดียวกับที่เขียน prob tree อ่ะครับ ตัวไหนใช้แล้วก็ตัดออกโดยเอา substring ก่อนกับหลังมาต่อกัน
{syntaxhighlighter PHP}
ab - abc
/
a
\
ac - acb
ba - bac
/
b
\
bc - bca
ca - cab
/
c
\
cb - cba
{/syntaxhighlighter}
ใช้ LinkList แก้ปัญหาได้มั้ยครับ
Linked List ไม่น่าใช่ที่ต้องการนะครับ
ชี้ทางให้ผมอีกนิดได้มั้ยครับ
[ ผมเป็นคนค่อนข้างเข้าใจยากครับ อาศัยลูกดันทุรังล้วนๆ ครับ ]
อันนี้ขอเพิ่มนะครับ ไม่อยากตั้งกระทู้ใหม่
คือผมเขียน javascript ด้วย jQuery ใช้ในการเปลี่ยนเมนู
พอกดสลับเมนูไปมาเรื่อยๆ พบว่า เบราเซอร์ เกิดอาการซิงเกิ้ลแรกของ room39 (หน่วง)
ปล. ทำไมผมถึงไม่พิมพ์หน่วงไปเลยเนอะ - -"
ไม่รู้จะอธิบายยังไงดี กลัว spoil หน่ะครับ 555+
อย่างตอนแรกเรามี abc เราก็จะทำ 3 รอบใช่ไหมครับ ก็คือรอบที่ a นำ รอบที่ b นำ และรอบที่ c นำ
ในรอบที่ a นำนั้นเราก็มีทางเลือกอีก ดังนั้นเราก็ต้องทำกับตัวที่เหลือก็คือ b นำและ c นำ และก็ทำแบบเดียวกันกับข้างบนด้วย
ดังนั้นเราได้ว่า
{syntaxhighlighter x}
หลัก -> เลือก a เหลือ bc
รอบรอง -> เลือก b ได้ ab เหลือ c
รอบรองรอง -> เลือก c ได้ abc ไม่เหลือแล้ว
รอบรอง -> เลือก c ได้ ac เหลือ b
รอบรองรอง -> เลือก b ได้ acb ไม่เหลือแล้ว
หลัก -> เลือก b เหลือ ac
รอบรอง -> เลือก a ได้ ba เหลือ c
รอบรองรอง -> เลือก c ได้ bac ไม่เหลือแล้ว
รอบรอง -> เลือก c ได้ bc เหลือ a
รอบรองรอง -> เลือก a ได้ bca ไม่เหลือแล้ว
หลัก -> เลือก c เหลือ ab
รอบรอง -> เลือก a ได้ ca เหลือ b
รอบรองรอง -> เลือก b ได้ cab ไม่เหลือแล้ว
รอบรอง -> เลือก b ได้ cb เหลือ a
รอบรองรอง -> เลือก a ได้ cba ไม่เหลือแล้ว
{/syntaxhighlighter}
ทีนี้เราไม่รู้ว่าเราจะทำกี่รอบ ดังนั้นจึงใช้วิธีสร้าง function ขึ้นมาและให้เรียกซ้ำไปเรื่อยๆ ถ้าความยาวเป็น 1 เมื่อไหร่ก็ไม่ต้องเรียกตัวเองต่อ
รหัสเทียมที่ได้ก็จะเป็นประมาณว่า
{syntaxhighlighter x}
function combi( ก่อนหน้า, ตัวที่เหลือ) :
if ตัวที่เหลือ ยาว 1:
print ก่อนหน้า + ตัวที่เหลือ
else
ความยาว = ตัวที่เหลือ ยาวเท่าไหร่
for i = 0 ถึง ความยาว - 1:
ตัวปัจจุบัน = ตัวที่เหลือ เอาเฉพาะตัวที่ i
ตัวที่เหลือใหม่ = ตัวที่เหลือ ไม่เอาเฉพาะตัวที่ i
// ตัดข้างหน้ากับข้างหลังมาต่อกัน แล้วเอาตรงกลางทิ้ง
combi( ก่อนหน้า+ตัวปัจจุบัน, ตัวที่เหลือใหม่);
endfor;
endfunction;
{/syntaxhighlighter}
ส่วน jQuery คงต้องดูโค้ดครับว่ามันมีส่วนไหนที่ทำ animation มากไป หรือใส่ element ลงในหน้ามากไป หรือเปล่าหน่ะครับ
พอกดสลับเมนูไปมาเรื่อยๆ >>
ฟังก์ชั่นอะไร browser อะำไร
ปัญหาเป็น browser เดียวหรือเปล่า
{$user} was not an Imposter
ทำเป็น recursive ครับ
ว่าแต่เรียนชั้นไหนครับจะได้ช่วยถูกระดับ
{$user} was not an Imposter
ปี 4 คร้าบบบบบบบบบบ
เต็มที่เลยครับ ขอเพียงแค่ไอเดีย แนวความคิด คอนเซ็ป อะไรประมาณนี้
ที่เหลือขอฝึกเองคร้าบบบ
ประมาณนี้ ลองดูครับ, เป็นกึ่ง concept กับ code ปนกันนะครับ
//Functions
function comBi(a){
comBiRecursive(a,"");
}
function comBiRecursive(a,b){
if(a.length==1) {
print b & a; //ผมใช้วิธี print ออกมาเลยนะครับ ง่ายดี
}
for(i=0;i<a.length;i++){
comBiRecursive(a without a[i],b & a[i]);
}
}
//การเรียกใช้
comBi("abc")
work ครับ ^^
เห็นแนะนำกันเยอะ แปลกใจนิดนึงว่าไม่มีใครพูดถึงกรณีเจอตัวอักษรซ้ำ (เช่น aaabbc) เลย
recursive ที่ไม่มี memory จะแก้ปัญหานี้กันยังไงครับ :D
ก็ต้องเก็บ output และเช็คซ้ำตัดออก (การ optimize อัลกอลิธึม เริ่มจะทวีความซับซ้อนขึ้นมากแระ)
(ที่ไม่อยากเก็บนั้น, ก็เป็นเพราะว่ารู้กันหรือป่าวว่า Factorial มันโตเร็วแค่ไหน .. แค่ทำสลับเพิ่มจาก 5 ตัวเป็น 10 ตัว ลองกดเครื่องคิดเลข 5!, 10! และ 20! ดูสิครับ)
ลืมไป ว่าจะ hint ไว้ให้ อันที่จริงไม่ต้องเก็บ output ที่เคย gen ก็ได้ครับ ใช้เทคนิคของ bucket sort (implement ด้วย linked list ก็ได้ ถ้าคุณจขกท.สนใจ) นิดหน่อย จะใช้พื้นที่น้อยกว่ามาก (กรณีข้อมูลขนาดใหญ่)
เก็บ parameters: b & sort(a) เร็วกว่าเก็บ output ครับ (แล้วเช็คและตัดออก)
ขออภัยที่ทำให้สับสนครับ
ตั้งใจจะหมายถึงกรณีที่มีอักษรซ้ำอ่ะครับ
โดยเพียงแค่แก้ 1 line กับ เพิ่มอีก 1 line น่ะครับ
ถ้าอักษรไม่ซ้ำ วิธีที่เสนอมาผมว่าดีแล้วครับ
ใช้ hashed table คิดว่าน่าจะดีที่สุดนะครับ แต่ต้องคิด hash function เนียนๆ หน่อยจะได้กินที่น้อยๆ
จริงจะไม่ให้มันซ้ำ ก่อน print ก็เก็บมันเข้า set ก่อน แล้วตัวต่อไปก็ check ว่า ตัวที่กำลังจะพิมพ์มีใน set หรือไม่
print(a){
if( !set.contains(a)){
set.add(a)
print(a)
}
}
555 .. จริงๆ มันก็เป็นแค่ one challenge problem ในวัยเรียนเท่านั้นเนอะ
+1 สนุกดีนะนั่งแก้ Algor เนี้ย ^^
พวกแข่ง ACM น่าจะเจอกันบ่อยครับ