PAtS.Computainment

ตั้งหัวข้อได้อลังการงานสร้างมาก
จริงๆ ก็คือมีเพื่อนจะไปสอบต่อโทคอม แต่ไม่ได้เรียนคอมมา
ก็เลยจะมาให้ผมช่วยติวให้หน่อย (เอิ้กๆ เลือกคนผิดแล้ว..)
และแล้ว ผมก็เลยจัดการคิดถึงโปรแกรมสิบแบบ
ที่คนเรียนคอมส่วนใหญ่ต้องได้เขียนกัน อิอิ
(หมายเหตุ: ส่วนใหญ่จะเอามาจากโปรแกรมพื้นฐานการเขียนซีนะครับ)

มาเริ่มกันเลยดีกว่า...

อันดับที่หนึ่ง Hello World!
อันนี้ น่าจะ 99.99% คงจะเคยเขียนโปรแกรมนี้มากันแล้ว
คงไม่ต้องพูดอะไรมาก โปรแกรมก็ง่ายๆ แต่พิมพ์ Hello World ออกมาให้ได้

อันดับที่สอง Swap
ไม่มีไรมากครับ มีตัวแปร a กับ b ให้สลับค่ากัน
ง่ายๆ คือมีตัวแปร temp มาตัวนึง เก็บค่าไว้ก่อน
t = a; a=b; b=t;
ขั้นสูงหน่อยก็ไม่ต้องมี temp
a ^= b; b ^= a; a ^= b;
ดูงงๆ แต่นก็ใช้ได้นะ ไล่ตรรกะเอาครับ

อีกประเด็นสำหรับโปรแกรมนี้ก็คือ function ครับ
คือการ pass by reference นั่นเอง
จริงๆ แล้วซีไม่มีการ pass by reference
แต่ใช้การส่งตำแหน่งหน่วยความจำไปแทน ซึ่งเป็น pass by value
โดยโปรแกรมนี้ ก็จะเป็นโปรแกรมแรกๆ ที่สอนให้รู้จักกับ pointer
ที่ถือว่าเป็นสิ่งมหัศจรรย์ของซีเลยทีเดียว

อันดับที่สาม มาโคร
อันนี้จะเป็นการพูดถึงเรื่องของ precedence และการแทนที่มาโคร
เรื่อง precedence คือ 5+3*2+1 = 5 + (3*2) + 1
ซึ่งมันมีการลำดับเยอะมากครับ บางภาษาก็ต่างกันไปบ้าง ผมเองก็จำไม่ได้ แหะๆ

ส่วนเรื่องของมาโครก็คือ
ถ้า #define mul(a,b) a*b แล้ว mul(5+2,3) จะได้เป็น 5+2*3
ซึ่งตาม precedence rule มันจะเป็น 5 + (2*3)
ไม่ใช่ (5+2) * 3 ตามความหมายที่ควรเป็น

วิธีแก้ที่เค้าแนะนำก็คือ ใช้วงเล็บครอบตัวแปรไป
เป็น #define mul(a,b) (a)*(b)

อับดับที่สี่ The Loop
อันนี้ที่คลาสสิก เจอกันบ่อยๆ คือให้พิมพ์แบบนี้
*
**
***
****
แล้วก็จะมีลูกเล่นไปเรื่อยๆ
เช่นเป็นสามเหลี่ยมหน้าจั่วบ้าง สี่เหลี่ยมด้านขนาน
สามเหลี่ยมเอาหัวทิ่ม ฯลฯ สารพัดที่อ. และทีเอจะนึกออก
ซึ่งมันไม่มีอะไรมากครับ แค่อยากให้รู้ว่าวนลูปให้เป็น

ลูปหลักๆ มีสองประเภท คือ เช็คก่อน กะเช็คหลัง แค่นี้หล่ะครับ
เพราะฉะนั้น บางคนก็จะเจอโจทย์ให้เขียน while เป็น for หรือ for เป็น while
ส่วน do {} while เป็นลูปเช็คหลังนะครับ

อันดับที่ห้า Palindrome
(เหนื่อย)
อันนี้จะเกี่ยวกับการเล่นสตริง
และพูดถึงการมองสตริงเป็นอะเรย์ของตัวอักษร
(-- ซีไม่มีตัวแปรชนิดสตริงนะครับ!!! --)
รวมทั้งการรู้จักว่า null terminated มันเป็นยังไง
โปรแกรมอื่นๆ ในเครือนี่ก็จะมีพวก นับตัวอักษร
แปลตัวใหญ่เป็นตัวเล็ก นับคำ ฯลฯ ก็ไม่มีอะไรมากครับ
ทำเสร็จก็จะรู้จัก ASCII และ Special Char บางตัวไป

อันดับที่หก Factorial
เรื่องนี้จะเป็นตัวอย่างที่ดี และง่ายที่สุดสำหรับเรื่องของ recursive
เราสามารถเขียนฟังก์ชันบรรทัดเดียวหาค่าแฟคได้

int fac(i) {
return (i>0)?(i*fac(i-1)):1;
}

ง่ายมั๊ย...
เรื่องของ recursive นั้น มีประโยชน์หลายอย่างครับ
เช่นเอาไปทำ DFS (Depth-First Search)
แต่บางทีมันก็มีประเด็นในการหาเงื่อนไข (ที่บางทีหายาก)
และเรื่องของการเรียกซ้อนไปหลายๆ ชั้นจน Stack Overflow - -"

อันดับที่เจ็ด Fibonacci
1 1 2 3 5 8 -- หลายคนคงรู้จักเลขชุดนี้นะครับ
มันคือ F(n) = F(n-1) + F(n-2), n > 1; F(0) = F(1) = 1
การหาเลขนี้ก็ถือได้ว่าเป็นโจทย์ที่มันมีกันทุกปี ทุกคอร์ส

วิธีหาเลขชุดนี้ง่ายสุดอ่ะเหรอ ไม่ต้องคิดมากเลย
ใช้อะเรย์โลด เหอๆ ไล่ไปเรื่อยๆ
หรือจะขั้นสูงหน่อยก็ใช้ recursive ไป อิอิ

อันดับแปด Prime
เลขจำนวนเฉพาะนั้นเองครับ
วิธีหาที่ซิมเปิลที่สุด ไล่ไปตั้งแต่ 2 ถึง n -1
ถ้ามีตัวไหนมาหารได้จบ ไม่เป็น
ถ้าเอาเร็วขึ้นมาหน่อยก็ถึง n/2

แล้วถ้าเป็นหาเลขเรียง n ตัวเลขอะไรแบบนี้
เค้าว่ากันว่าใช้ตะแกรงร่อนจะเร็วสุด
มันคือ เริ่มจาก 2 เอาทุกตัวที่หารด้วย 2 ลงตัวออก
ถัดมา 3 เอาทุกตัวที่หารด้วย 3 ลงตัวออก
ถัดมา 5 (เพราะ 4 โดนเอาออกไปแล้ว) เอาทุกตัวที่หารด้วย 5 ลงตัวออก
ไปเรื่อยๆ เหมือนการร่อนทรายนั้นเองครับ

ส่วนวิธีเช็คว่าจำนวนนี้เป็นจำนวนเฉพาะหรือไม่
มันมีทฤษฎีที่ซับซ้อน (แปลว่า ผมลืมไปแล้ว) อยู่เหมือนกัน
ซึ่งเท่าที่จำได้บางวิธีจะบอกได้แค่ว่า มันน่าจะเป็นมากๆ นะ แต่ไม่ชัวร์

อับดับที่ 9 The Math
หลังจากหาเลขจำนวนเฉพาะแล้ว
มันก็มีการคำนวณอีกหลายอย่างรออยู่
ซึ่งพวกนี้ส่วนใหญ่จะเน้นให้ใช้อะเรย์และลูปเป็น
เช่นการหาค่ามากสุด น้อยสุด ค่าเฉลี่ย
การหาคำตอบของสมการ quadratic ด้วยสูตร -b +/- root ..... อะไรนั่นอ่ะ
หรือการหาคำตอบโดยใช้กฏของ Cramer
ยากหน่อยก็น่าจะเป็นการคูณเมตริกมั๊ง ลูปเยอะ
ยากกว่าก็การหาเดทของเมตริก ถ้า 2x2 ก็ง่ายหน่อย.. เจอ 4x4 ไปก็ตาย เหอๆ

อันดับที่ 10 Sort & Search
อืมม.. อันนี้น่าจะยากสุดในสิบอย่างพื้นฐานนี้
ยากจนตอนสอบมีคนคิด Binary Sort มาได้ (คือมันไม่มีง่ะ - -')

ว่าด้วยเรื่องของการเรียงลำดับเนี่ย
อัลกอง่ายสุดก็น่าจะเป็นบับเบิลมั๊ง ประมาณว่าเรียงดะ
ค่อยๆ กระดึบๆ เรียงทีละตัว.. ช้าโคตร

ที่เข้าใจง่ายๆ หน่อยถัดมาก็น่าจะเป็น Insertion กับ Selection
สองตัวนี้คล้ายๆ กัน เขียนไม่ยากเท่าไหร่ แต่ก็ช้าอยู่ดี

เร็วสุดก็น่าจะเป็น Quick Sort มั๊ง (มั๊งนะ จำไม่ได้แล้ว - เข้าใจยากด้วย)
ส่วนที่เอามาเรียงข้อมูลใหญ่ๆ ได้ก็ Merge Sort (ใช้หลักการแบ่งเรียงทีละนิด)
แต่ถ้าข้อมูลซ้ำๆ กัน ก็ Radix Sort หรือ Bucket Sort

โอ๊ยย.. เยอะแยะสารพัดวิธีมากครับ จำบ่ได้หมด เหอๆ

ส่วนเรื่องการค้นหา
ก็มีตั้งแต่ไล่หาไปเรื่อยๆ (Linear)
การทำเป็นทรีเพื่อหาให้เร็วขึ้น
การ hash เอาไว้ก่อน แล้วหาจาก hash เอา ฯลฯ

จากเรื่องสองเรื่องนี้.. จะนำไปสู่เรื่องของโอตัวใหญ่ (บิ๊กโอ)
ซึ่งจะใช้วัดว่าอัลกอแต่ละแบบนี้ใช้เวลาเท่าไหร่ (จริงๆ มันใช้ทุกเรื่องหล่ะ Big-O เนี่ย)
เช่น
การเรียงแบบบับเบิล ใช้เวลา O(n²) คือใช้เวลาแปรตามกำลังสองของข้อมูล
การเรียงแบบ Quick ใช้เวลา O(n log n )
การหาไปเรื่อยๆ เป็น O(n) คือใช้เวลาแปรตามจำนวนข้อมูล
การหาแบบ hash O(1) คือใช้เวลาคงที่ ไม่ขึ้นกับจำนวนข้อมูล

นอกจาก Big-O แล้วยังมี Big-Omega และ Big-Theta อีกนะครับ
จำได้ว่าอ. มะนาวสอนสนุกสนาน เอิ้กๆ



....
หลังๆ เริ่มเขียนน้อย.. แบบว่าเหนื่อยครับ เหอๆ
แค่นี้ก่อนหล่ะครับ หมดแรงแล้ววว อิอิ
ว่าแต่... เคยเขียนมากันหมดหรือเปล่าครับ อิอิ

ปล. อันนี้นั่งนึกๆ มาเองนะครับ แหะๆ
อาจจะมีอะไรผิดๆ ไปบ้างนะ อิอิ
ปล2. พยายามจะใส่ลิงค์ไปวิกิให้หมด.. แต่หมดแรงก่อน รอมีแรงจะมาใส่ต่อ