2110427 : การบ้านครั้งที่ 3

จุดประสงค์

• ออกแบบขั้นตอนวิธีการแบ่งข้อความในหนึ่งย่อหน้าให้เป็นบรรทัดต่างๆ เพื่อแลดูสวยงาม โดยใช้กำหนดการพลวัต โดยผลของการบ้านดูได้จาก applet ข้างล่างนี้

สามารถเปลี่ยนแปลงข้อความได้โดยตรงในช่องด้านบน จะปรากฎการจัดบรรทัดใหม่โดยทันทีที่ช่องด้านล่าง หรือถ้าอยากลองปรับความกว้างของเนื้อที่ที่แสดง ก็ให้นำ mouse ไปวางไว้ในกรอบสี่เหลี่ยมน้ำเงิน กดแล้วลากดู

ความเป็นมา

หน้าที่พื้นฐานอย่างหนึ่งของโปรแกรมประมวลจัดพิมพ์เอกสารในปัจจุบันที่ต้องทำก็คือ การแบ่งข้อความในย่อหน้าหนึ่งๆ ออกเป็นบรรทัดๆ โดยการแบ่งนี้มีจุดประสงค์เพื่อให้ที่ว่างทางขวามือปลายบรรทัดในแต่ละบรรทัดของย่อหน้า (ยกเว้นบรรทัดสุดท้าย) แลดูสวยงาม

กำหนดให้บรรทัดหนึ่งมีความกว้างของบริเวณที่แสดงข้อความวัดได้ M จุดภาพ (pixels) ถ้าบรรทัดหนึ่งประกอบด้วยคำที่ i ถึง j ของย่อหน้า บรรทัดนั้นจะกินที่ไป (พจน์ j–i ก็คือช่องว่างที่ต้องคั่นระหว่างคำในภาษาอังกฤษ) ดังนั้นที่ว่างที่เหลือปลายบรรทัดก็คือ

โดยที่ SPACE คือจำนวนจุดภาพตามแนวกว้างของช่องว่างหนึ่งช่อง และ เป็นฟังก์ชันคำนวณจำนวนจุดภาพของความกว้างในการแสดง ซึ่งคือคำที่ k ของข้อความ กำหนดให้ย่อหน้าหนึ่งถูกแบ่งเป็น m บรรทัด บรรทัดที่ i ของย่อหน้า เริ่มด้วยคำที่ ของย่อหน้า ดังนั้นบรรทัดที่ i ก็ย่อมมีที่ว่างปลายบรรทัดเป็น

แล้วเราจะนิยามความสวยของการพิมพ์ได้อย่างไร แน่นอนว่าความสวยที่ว่านี้คงต้องขึ้นกับ (ยกเว้นบรรทัดสุดท้ายของย่อหน้า เพราะถึงแม้มีที่ว่างเยอะก็แลดูไม่น่าเกลียด) ก็ต้องลองดูว่าเราจะแปลงความสวยมาเป็นฟังก์ชันจุดประสงค์กันอย่างไรดี จึงจะสะท้อนว่าถ้ามีค่าน้อยแสดงว่าสวยมาก (0 แสดงว่าสวยสุด) มีค่ามากก็สวยน้อย ถ้าให้เป็น ก็อาจจะไม่ค่อยดีเพราะถ้าบรรทัดหนึ่งว่าง 10 อีกบรรทัดว่าง 0 จะสวยเหมือนบรรทัดหนึ่งว่าง 5 อีกบรรทัดก็ว่าง 5 (ซึ่งแบบหลังน่าจะสวยกว่า) ก็แสดงว่าเราไม่ชอบที่ว่างเยอะ อันนี้ทำได้เช่น ให้ทำโทษเป็นยกกำลังสองของที่ว่าง ได้ฟังก์ชันจุดประสงค์เป็น หรือแม้กระทั่งให้เป็น ก็จะสะใจมากขึ้น

สำหรับการบ้านครั้งนี้ขอเป็นยกกำลังสามก็แล้วกัน (ไม่มีเห็นผลใดนอกจากความสะใจ แต่ถ้าจะทดลองเปรียบเทียบดูก็ดีเหมือนกัน)

ฺเขียน method wordWrap ในแฟ้ม Hw3.java ซึ่งมีหัวดังนี้

public static Vector wordWrap( String text, int width, FontMetrics fm ){ ... }

• wordWrap เป็น static method หมายความว่าสามารถเรียกใช้ได้โดยไม่ต้องสร้าง object ของ class ทีมี method นี้ (นั่นคือสามารถเรียกใช้ Hw3.wordWrap(s,w,f) ได้เลย) 
• text คือ string ที่เก็บตัวอักษรต่างๆของทั้งย่อหน้า
• width คือ จำนวนจุดภาพ (pixel) ของความกว้างของเนื้อที่แสดงในหนึ่งบรรทัด
• fm คือ ตัวที่ใช้ช่วยหาขนาดต่างๆที่เกี่ยวกับ font เช่นเราสามารถใช้หาจำนวนจุดภาพตามแนวกว้างของ blank หนึ่งตัว ได้โดยเรียกใช้ space = fm.charWidth( ' ' );  หรือใช้หาจำนวนจุดภาพตามแนวกว้างของ string x ได้โดยเรียกใช้ w = fm.stringWidth( x ); อ่านรายละเอียดต่างๆ ได้จาก help ของ JDK เรื่อง class FontMetrics (อาจใช้ method อื่นๆ แทน charwidth หรือ stringWidth ก็ได้)
• สิ่งที่ wordWrap คืนกลับมาคือ Vector ที่เก็บ string ต่างๆ ที่แทนข้อความในแต่ละบรรทัด ซึ่จะถูกนำไปแสดงบนจอภาพ ด้วย code ข้างล่างนี้ (นักเรียนไม่ต้องเขียน code ข้างล่างนี้ ที่แสดงให้ดูจะได้รู้ว่าตัว applet ใช้ wordWrap อย่างไร)

public void paint( Graphics g ) {
  g.setFont( new Font("Serif", Font.PLAIN, 12));
  FontMetrics fm = g.getFontMetrics();
  int         fontHeight = fm.getAscent() - fm.getDescent();
  Vector      lines = Hw3.wordWrap( text, lineWidth, fm );

  int curY = 20;
  g.setColor( Color.black );
  Enumeration enum = lines.elements();
  while( enum.hasMoreElements() ) {
    g.drawString((String)enum.nextElement(), 5, curY);
    curY += fontHeight * 1.5;
  }
}

• unzip แฟ้ม 427hw3.zip ลงใน directory ที่เก็บเฉพาะการบ้านนี้ จะพบแฟ้มต่างๆ ดังนี้
  • Hw3.java (แฟ้มที่ต้องเขียน method wordWrap ของการบ้าครั้งนี้)
  • hw3.jar   (แฟ้มเก็บ class สำคัญอื่นๆ ของ applet)
  • hw3.htm (แฟ้มเอาไว้ดูผลการทำงานของ applet)
  • hw3.pdf (เอกสารที่กำลังอ่านอยู่นี้แบบ pdf)

• แก้ไขแฟ้ม Hw3.java ด้วย editor อะไรก็ได้ (เช่น notepad, edit plus, ...)
• compile ด้วย  javac -classpath .;hw3.jar Hw3.java
• สั่งทำงานด้วย  appletviewer hw3.htm
  (หรือจะเปิด hw3.htm ด้วย web browser ก็ได้)

• เปิด hw3.htm ด้วย Internet Explorer เพื่อดูการทำงานของ applet 

กำหนดส่ง

• วันที่ 30 กรกฎาคม 2544  (แต่แนะนำว่าให้ทำให้เสร็จก่อนวันสอบกลางภาค)

สมชาย ประสิทธิ์จูตระกูล 
2110427 : การวิเคราะห์และออกแบบอัลกอริทึม