[VB.NET] การหาชุดของความยาวด้านของสามเหลี่ยมมุมฉาก (Pythagoras) ที่เป็นจำนวนเต็มทั้งหมดที่จะเป็นไปได้

thongkorn

ทฤษฎีบทพีทาโกรัส คือ ทฤษฎีความสัมพันธ์ระหว่างด้านทั้งสามของสามเหลี่ยมมุมฉาก สามเหลี่ยมที่มีมุมใดมุมหนึ่งตั้งฉาก 90 องศา เป็นทฤษฎีที่คิดค้นโดยพีทาโกรัส นักคณิตศาสตร์ชาวกรีก ซึ่งกล่าวถึงทฤษฎีนี้ไว้ว่า

"ในสามเหลี่ยมมุมฉากใด ๆ พื้นที่ของสี่เหลี่ยมจัตุรัสที่มีด้านเป็นด้านตรงข้ามมุมฉาก เท่ากับผลรวมพื้นที่ของสี่เหลี่ยมจัตุรัสที่มีด้านเป็นด้านประชิดมุมฉากของสามเหลี่ยมมุมฉากนั้น"

จากทฤษฎีบทพีทาโกรัส ทำให้เราสามารถเขียนสูตรพีทาโกรัสเพื่อหาความยาวของด้านต่างๆของสามเหลี่ยมมุมฉากได้ดังนี้

a² + b² = c²

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

ในการทดสอบค่าความถูกต้องของสมการ Pythagoras ซึ่งเป็น a^2 + b^2 = c^2 เราจะทดสอบค่า a, b, และ c ทุกคู่ที่เป็นไปได้ ซึ่งค่า a, b, และ c จะต้องเป็นจำนวนเต็มบวก และค่า c ต้องมากกว่าค่า a และมากกว่าค่า b ด้วย ดังนั้นเราสามารถใช้ Nested Loop สามชั้นเพื่อทดสอบทุกคู่ของค่า a และ b แล้วคำนวณหาค่า c เพื่อเปรียบเทียบค่าของ a^2 + b^2 ว่าเท่ากับ c^2 หรือไม่?
ข้อสังเกต:

การใช้ Nested Loop ซ้อนกันถึง 3 ลูป โดยให้ลูป B และ ลูป C ทำการอ่านค่าเริ่มต้นจาก 1 ทำให้จำนวนรอบวงในสุดจะต้องอ่านค่าและเปรียบเทียบกันถึง 100 x 100 x 100 = 1,000,000 รอบ ซึ่งจะต้องใช้เวลามาก แต่คำตอบที่ได้จะเกิดจากการย้ายข้างของ a กับ b เช่น a = 3, b = 4 คำตอบ c = 5 พอให้ a = 4, b = 3 (การเริ่มนับจาก 1) แต่คำตอบ c = 5 เหมือนเดิม ดังนั้นเราจะใช้การลดจำนวนการนับลงไป โดยให้ลูปในมีค่าเริ่มต้นจากลูปนอกแทน ...


เมื่อกำหนดค่าเริ่มต้นใหม่โดยให้ลูปในมีค่าเริ่มต้นจากลูปนอกแทน ... เราให้ลูปในมีค่าเริ่มต้นจากค่าของลูปนอกแทน คือ b เริ่มจากค่า a ส่วน c จะเริ่มจากค่า b (b จะนับค่าต่ำกว่า a ไม่ได้ และ c จะนับค่าต่ำกว่า b ไม่ได้นั่นเอง) ...

1.             For b As Integer = a To Val(txtMaxValue.Text)
   
2.                 For c As Integer = b To Val(txtMaxValue.Text)

คัดลอกไปที่คลิปบอร์ด

จากลูป b จะวนรอบเพียง 50% ส่วนลูป c จะวนรอบเหลือไม่เกิน 20% คำตอบที่ได้ก็จะเหลือเพียง 52 รายการ แต่อีก 52 รายการที่ไม่ได้นำมาคิดคำนวณ ก็คือการสลับค่ากันระหว่างค่า a และ b นั่นเอง ...


การนำ LINQ (Language Integrated Query) มาช่วยในการแก้ปัญหาของความช้าในการวนลูปแบบ Nested Loop ... LINQ (ปกติจะอ่านว่าลิ้ง แต่บางคนก็อ่านว่าลิน หรือลินคิว ก็เอาตามที่สะดวกล่ะกันครับ) เจ้าตัวนี้จัดว่าเป็นความสามารถอันทรงพลังของ WinForm หรือ .Net Framework เลยก็ว่าได้ เพราะ LINQ คือชุดคำสั่งที่ทำงานกับกลุ่มของข้อมูล คล้ายๆกับการ Query ในฐานข้อมูลยังไงยังงั้นแหละครับทั่นผู้ชม

1.         ' / LINQ
   
2.         Dim PythagoreanTriple =
   
3.             From a In Enumerable.Range(1, MaxValue)
   
4.             From b In Enumerable.Range(a, MaxValue)
   
5.             Let c = Math.Sqrt(a * a + b * b)
   
6.             Where (c = Math.Floor(c) AndAlso c <= MaxValue)
   
7.             Select New With {a, b, c}

คัดลอกไปที่คลิปบอร์ด

ตัวอย่างที่แอดมินทำการทดสอบโดยให้ค่าสูงสุดที่ 100 อาจจะมองไม่เห็นผลสักเท่าไหร่ ลองใช้สัก 1,000 หรือ 10,000 รอบดู ทุกๆท่านจะได้เห็นผลลัพธ์ของการทำงานที่แตกต่างกันมากเลยทีเดียว ...

เพิ่มเติม: นอกจากจะเอา LINQ มาแก้ปัญหาแล้ว โจทย์ข้อนี้ยังนำทางให้เราไปฝึกเขียนโค้ดเพื่อแยกการทำงานของ Thread ได้ด้วย รวมไปถึงการเรียนรู้ใช้งาน  Parallel programming in .NET ... เอาไว้แอดมินจะนำมาเสนอให้ทุกๆท่านได้รับชมกันอีกทีครับ

แอดมินนำผลลัพธ์ที่ได้ไปใส่ไว้ TextBox, ListView และ DataGridView Control เพื่อสำหรับมือใหม่ๆจะได้ฝึกเรียนรู้ในการใช้งาน Control พื้นฐานต่างๆเหล่านี้ไปด้วยครับผม ...

มาดูโค้ดฉบับเต็มกันเถอะ ...

1. Imports System.Text
   
2. 
   
3. Public Class frmPythagoras
   
4. 
   
5.     '/ Start-Stop Timer
   
6.     Private mTimeDouble As Double
   
7.     Private sWatch As New Stopwatch()
   
8. 
   
9.     Private Sub frmPythagoras_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load
   
10.         lblCount.Text = ""
    
11.         lblTimer.Text = ""
    
12.         lblLoop.Text = ""
    
13.         txtMaxValue.MaxLength = 6
    
14.         '// ฝากเป็นโจทย์ไปคิดในกรณีที่เราคิดกลับ เมื่อใช้สูตร a=2n, b=n²-1, c=n²+1
    
15.     End Sub
    
16. 
    
17.     ' / -------------------------------------------------------------------------------------------------
    
18.     ' / เริ่มต้นในการประมวลผลแบบพื้นฐานด้วยการใช้ Nested Loop
    
19.     ' / -------------------------------------------------------------------------------------------------
    
20.     Private Sub btnNestedLoop_Click(sender As System.Object, e As System.EventArgs) Handles btnNestedLoop.Click
    
21.         TextBox1.Clear()
    
22.         Call InitializeListView()
    
23.         Call InitializeDataGridView()
    
24.         '// สร้าง String Builder สำหรับเก็บค่าไปแสดงผลใน TextBox Control (System.Text)
    
25.         Dim strBuilder As New StringBuilder()
    
26.         '// สร้าง ListViewItem เพื่อเก็บข้อมูล
    
27.         Dim items As New List(Of ListViewItem)
    
28.         '// สร้าง DataTable เพื่อเก็บข้อมูลให้กับ DataGridView
    
29.         Dim DT As New DataTable
    
30.         With DT.Columns
    
31.             .Add("A", GetType(Integer))
    
32.             .Add("B", GetType(Integer))
    
33.             .Add("C", GetType(Integer))
    
34.         End With
    
35.         lblTimer.Text = "Timer Nested Loop : "
    
36.         sWatch.Reset()
    
37.         sWatch.Start()
    
38.         Cursor = Cursors.WaitCursor
    
39.         '// ไว้นับจำนวนลูป
    
40.         Dim CountLoopA As Integer = 0 : Dim CountLoopB As Integer = 0 : Dim CountLoopC As Integer = 0
    
41.         '// ใช้ Nested Loop โดยกำหนดให้ลูปในใช้ค่าเริ่มต้นจากลูปนอก
    
42.         '// เพราะค่าตัวแปรของ a สลับกันกับ b ก็จะไม่มีผลอะไร เช่น a = 3, b = 4 หากกลับค่า a = 4, b = 3 ก็จะทำให้ได้ค่า c = 5 เท่ากัน
    
43.         '// และจะทำให้ลดจำนวนการวนรอบของลูปลงไป
    
44.         For a As Integer = 1 To Val(txtMaxValue.Text)
    
45.             CountLoopA += 1
    
46.             For b As Integer = a To Val(txtMaxValue.Text)
    
47.                 CountLoopB += 1
    
48.                 For c As Integer = b To Val(txtMaxValue.Text)
    
49.                     CountLoopC += 1
    
50.                     ' / --------------------------------------------------------
    
51.                     ' / เงื่อนไขที่ต้องการทดสอบ คือ a^2 + b^2 = c^2
    
52.                     ' / --------------------------------------------------------
    
53.                     If a * a + b * b = c * c Then
    
54.                         '// สำหรับ TextBox Control
    
55.                         strBuilder.AppendLine("a = " & a & vbTab & "b = " & b & vbTab & "c = " & c)
    
56.                         '// สำหรับ ListView Control
    
57.                         Dim NewItem As New ListViewItem(a) '// กำหนดค่าให้กับคอลัมน์แรก
    
58.                         NewItem.SubItems.Add(b) ' เพิ่มค่าในคอลัมน์ที่สอง
    
59.                         NewItem.SubItems.Add(c) ' เพิ่มค่าในคอลัมน์ที่สาม
    
60.                         items.Add(NewItem)
    
61.                         '// สำหรับ DataGridView Control
    
62.                         Dim row As String() = New String() {"", "", ""}
    
63.                         DT.Rows.Add(a, b, c)
    
64.                         '// หากใช้ Exit For ก็จะช่วยให้ลดจำนวนการวนรอบลงไปได้อีก
    
65.                         'Exit For
    
66.                     End If
    
67.                 Next
    
68.             Next
    
69.         Next
    
70.         '// แสดงผลลัพธ์ใน TextBox Control
    
71.         TextBox1.Text = strBuilder.ToString()
    
72.         '// แสดงผลลัพธ์ใน ListView Control
    
73.         ListView1.Items.AddRange(items.ToArray())
    
74.         '// แสดงผลลัพธ์ใน DataGridView Control
    
75.         DataGridView1.DataSource = DT
    
76.         lblCount.Text = "จำนวน: " & DataGridView1.RowCount & " รายการ"
    
77.         DT.Dispose()
    
78.         txtMaxValue.Focus()
    
79.         Cursor = Cursors.Default
    
80.         sWatch.Stop()
    
81.         mTimeDouble = sWatch.ElapsedMilliseconds * 0.001
    
82.         lblTimer.Text = lblTimer.Text & mTimeDouble.ToString & " sec."
    
83.         lblLoop.Text = "a = " & Format(CountLoopA, "#,##") & vbCrLf & "b = " & Format(CountLoopB, "#,##") & vbCrLf & "c = " & Format(CountLoopC, "#,##")
    
84.     End Sub
    
85. 
    
86.     ' / -------------------------------------------------------------------------------------------------
    
87.     ' / สามารถใช้ LINQ ใน VB.NET เพื่อหาชุดของความยาวด้านของสามเหลี่ยมมุมฉาก
    
88.     ' / Pythagorean Triplets ที่เป็นเลขจำนวนเต็มทั้งหมดที่จะเป็นไปได้ดังนี้
    
89.     ' / -------------------------------------------------------------------------------------------------
    
90.     Private Sub btnLinQ_Click(sender As System.Object, e As System.EventArgs) Handles btnLinQ.Click
    
91.         TextBox1.Clear()
    
92.         Call InitializeListView()
    
93.         Call InitializeDataGridView()
    
94.         '//
    
95.         Dim MaxValue As Integer = Val(txtMaxValue.Text) '// กำหนดความยาวด้านสูงสุดที่ต้องการทดสอบ
    
96.         '// สร้าง String Builder สำหรับเก็บค่าไปแสดงผลใน TextBox Control (System.Text)
    
97.         Dim strBuilder As New StringBuilder()
    
98.         '// สร้าง ListViewItem เพื่อเก็บข้อมูล
    
99.         Dim items As New List(Of ListViewItem)
    
100.         '// สร้าง DataTable เพื่อเก็บข้อมูลให้กับ DataGridView
     
101.         Dim DT As New DataTable
     
102.         With DT.Columns
     
103.             .Add("A", GetType(Integer))
     
104.             .Add("B", GetType(Integer))
     
105.             .Add("C", GetType(Integer))
     
106.         End With
     
107.         lblTimer.Text = "Timer LINQ : "
     
108.         sWatch.Reset()
     
109.         sWatch.Start()
     
110.         Cursor = Cursors.WaitCursor
     
111.         ' / -------------------------------------------------------------------------------------------------
     
112.         ' / LINQ
     
113.         Dim PythagoreanTriple =
     
114.             From a In Enumerable.Range(1, MaxValue)
     
115.             From b In Enumerable.Range(a, MaxValue)
     
116.             Let c = Math.Sqrt(a * a + b * b)
     
117.             Where (c = Math.Floor(c) AndAlso c <= MaxValue)
     
118.             Select New With {a, b, c}
     
119.         ' / -------------------------------------------------------------------------------------------------
     
120. 
     
121.         For Each triplet In PythagoreanTriple
     
122.             strBuilder.AppendLine("a = " & triplet.a & vbTab & "b = " & triplet.b & vbTab & "c = " & triplet.c)
     
123.             '// สำหรับ ListView Control
     
124.             Dim NewItem As New ListViewItem(triplet.a) '// กำหนดค่าให้กับคอลัมน์แรก
     
125.             NewItem.SubItems.Add(triplet.b) ' เพิ่มค่าในคอลัมน์ที่สอง
     
126.             NewItem.SubItems.Add(triplet.c) ' เพิ่มค่าในคอลัมน์ที่สาม
     
127.             items.Add(NewItem)
     
128.             '// สำหรับ DataGridView Control
     
129.             Dim row As String() = New String() {"", "", ""}
     
130.             DT.Rows.Add(triplet.a, triplet.b, triplet.c)
     
131.         Next
     
132.         '// แสดงผลลัพธ์ใน TextBox Control
     
133.         TextBox1.Text = strBuilder.ToString()
     
134.         '// แสดงผลลัพธ์ใน ListView Control
     
135.         ListView1.Items.AddRange(items.ToArray())
     
136.         '// แสดงผลลัพธ์ใน DataGridView Control
     
137.         DataGridView1.DataSource = DT
     
138.         lblCount.Text = "จำนวน: " & DataGridView1.RowCount & " รายการ"
     
139.         DT.Dispose()
     
140.         Cursor = Cursors.Default
     
141.         sWatch.Stop()
     
142.         mTimeDouble = sWatch.ElapsedMilliseconds * 0.001
     
143.         lblTimer.Text = lblTimer.Text & mTimeDouble.ToString & " sec."
     
144.         lblLoop.Text = ""
     
145.     End Sub
     
146. 
     
147.     ' / -------------------------------------------------------------------------------------------------
     
148.     Private Sub txtMaxValue_KeyPress(sender As Object, e As System.Windows.Forms.KeyPressEventArgs) Handles txtMaxValue.KeyPress
     
149.         '// เมื่อมีการกด Enter
     
150.         If Asc(e.KeyChar) = 13 Then
     
151.             If String.IsNullOrWhiteSpace(txtMaxValue.Text) AndAlso Not Char.IsControl(e.KeyChar) Then
     
152.                 e.Handled = True
     
153.             Else
     
154.                 '// ไปประมวลผล
     
155.                 Call btnNestedLoop_Click(sender, e)
     
156.                 e.Handled = True
     
157.             End If
     
158.         ElseIf Not Char.IsDigit(e.KeyChar) AndAlso Not Char.IsControl(e.KeyChar) Then
     
159.             e.Handled = True '// ไม่อนุญาตให้ป้อนค่าที่ไม่ใช่ตัวเลข
     
160.         End If
     
161.     End Sub
     
162. 
     
163.     Private Sub TextBox1_KeyPress(sender As Object, e As System.Windows.Forms.KeyPressEventArgs) Handles TextBox1.KeyPress
     
164.         '// ป้องกันไม่ให้กดคีย์อะไรลงไปใน TextBox Control.
     
165.         e.Handled = True
     
166.     End Sub
     
167. 
     
168.     ' / -------------------------------------------------------------------------------------------------
     
169.     ' / Initialized DataGridView Control.
     
170.     ' / -------------------------------------------------------------------------------------------------
     
171.     Private Sub InitializeDataGridView()
     
172.         With DataGridView1
     
173.             .RowHeadersVisible = False ' True
     
174.             .AllowUserToAddRows = False
     
175.             .AllowUserToDeleteRows = False
     
176.             .AllowUserToResizeRows = False
     
177.             .MultiSelect = True ' False
     
178.             .SelectionMode = DataGridViewSelectionMode.FullRowSelect
     
179.             .ReadOnly = True
     
180.             '// Data rows
     
181.             .Font = New Font("Tahoma", 10)
     
182.             .RowTemplate.MinimumHeight = 27
     
183.             .RowTemplate.Height = 27
     
184.             '// Autosize Column
     
185.             .AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.Fill
     
186.             '// Header
     
187.             With .ColumnHeadersDefaultCellStyle
     
188.                 .BackColor = Color.RoyalBlue
     
189.                 .ForeColor = Color.White
     
190.                 .Font = New Font(DataGridView1.Font, FontStyle.Bold)
     
191.             End With
     
192.         End With
     
193.     End Sub
     
194. 
     
195.     ' / -------------------------------------------------------------------------------------------------
     
196.     ' / Initialized ListView Control.
     
197.     ' / -------------------------------------------------------------------------------------------------
     
198.     Private Sub InitializeListView()
     
199.         With ListView1
     
200.             .Columns.Clear() '// make sure columns collection is empty.
     
201.             .Items.Clear()
     
202.             .View = View.Details
     
203.             .HeaderStyle = ColumnHeaderStyle.Nonclickable '// set to whatever you need.
     
204.             .GridLines = True
     
205.             .FullRowSelect = True
     
206.             .HideSelection = False
     
207.             .MultiSelect = True 'False
     
208.             '// Add 3 columns
     
209.             .Columns.Add("A")
     
210.             .Columns.Add("B")
     
211.             .Columns.Add("C")
     
212.         End With
     
213.         With ListView1
     
214.             .Columns(0).Width = ListView1.Width \ 3 - 10
     
215.             .Columns(1).Width = ListView1.Width \ 3 - 10
     
216.             .Columns(2).Width = ListView1.Width \ 3 - 5
     
217.         End With
     
218.     End Sub
     
219. 
     
220.     Private Sub frmPythagoras_FormClosed(sender As Object, e As System.Windows.Forms.FormClosedEventArgs) Handles Me.FormClosed
     
221.         Me.Dispose()
     
222.         GC.SuppressFinalize(Me)
     
223.         Application.Exit()
     
224.     End Sub
     
225. 
     
226.     Private Sub btnExit_Click(sender As System.Object, e As System.EventArgs) Handles btnExit.Click
     
227.         Me.Close()
     
228.     End Sub
     
229. 
     
230. End Class

คัดลอกไปที่คลิปบอร์ด

ดาวน์โหลดโค้ดต้นฉบับ VB.NET (2010) ได้ที่นี่ ...