รู้จัก สามเหลี่ยมปีธากอรัส (Pythagorean triple) มั้ยครับ?
สามเหลี่ยมปีธากอรัส คือ ตัวเลข 3 ตัว ที่สามารถนำมาสร้างสามเหลี่ยมมุมฉาก (Right Triangle) ได้พอดี
เมื่อแทนตัวเลข 3 ตัวด้วย (a, b, c)
a และ b คือ ขาของมุมฉาก (Legs)
c คือ ด้านตรงข้ามมุมฉาก (Hypotenuse) แล้ว
a² + b² = c² เสมอ

สามเหลี่ยมปีธากอรัส นอกจากจะถูกใช้เป็นสูตรในการคำนวนด้านของสามเหลี่ยมมุมฉากแล้ว
บางคนก็นำมาประยุกต์ใช้สำหรับวัดเส้นทะแยงมุม เช่น ความยาวของบันได ระยะห่างบนแผนที่ และแม้แต่การหารากที่สอง
ข้อมูลเพิ่มเติมเกี่ยวกับ สามเหลี่ยมปีธากอรัส อ่านได้ ที่นี่ ครับ

วิธีสร้าง สามเหลี่ยมปีธากอรัส ก็ง่าย ๆ เลือกตัวเลขมา 2 ตัว m กับ n
โดยที่ m > n และมีสูตรคำนวนต่าง ๆ ดังนี้

ด้าน a = m² - n²
ด้าน b = 2mn
ด้าน c = m² + n²

สมมติว่าเลือกตัวเลข 2 กับ 1.

ด้าน a = 2² - 1²   = 3
ด้าน b = 2 * 2 * 1 = 4
ด้าน c = 2² + 1²   = 5

แค่นี้เราก็ได้สามเหลี่ยม (3, 4, 5)

ข่าวร้ายคือ เราไม่สามารถสร้างสามเหลี่ยมปีธากอรัสทุกแบบได้จากสูตรนี้
แต่ไม่ต้องตกใจครับ ข่าวดีคือ เราสามารถสร้าง Primitive Pythagorean triple ได้จากสูตรนี้

Primitive Pythagorean triple คือ สามเหลี่ยมปีธากอรัสตัวต้นแบบ
เราสามารถนำด้านต่าง ๆ มาคูณตัวเลขเพื่อให้ได้สามเหลี่ยมปีธากอรัสแบบอื่น ๆ
เช่น สามเหลี่ยม (3, 4, 5) สามารถนำมาคูณ 3 เพื่อให้ได้ สามเหลี่ยม (9, 12, 15)
Primitive Pythagorean triple ลำดับแรก ๆ มีดังนี้

( 3,  4,  5) ( 5, 12, 13) ( 7, 24, 25)
( 8, 15, 17) ( 9, 40, 41) (11, 60, 61)
(12, 35, 37) (13, 84, 85) (16, 63, 65)

ถ้าคุณสังเกตุ เลขต่าง ๆ ของ Primitive Pythagorean triple เป็นจำนวนเฉพาะสัมพัทธ์ (coprime)
การสร้าง Primitive Pythagorean triple จาก m, n
m กับ n ต้องไม่เป็นเลขคี่พร้อมกัน
และ m กับ n ต้องจำนวนเฉพาะสัมพัทธ์กันด้วย
(จำนวนเฉพาะสัมพัทธ์ คือ ตัวเลขทั้งหมดในกลุ่ม มีตัว หารร่วมมาก คือ 1)

มาสร้าง Type ของสามเหลี่ยมปีธากอรัสกัน

public class PythagoreanTriple {
    int _seed1;
    int _seed2;
    int _size;
    int _sideA;
    int _sideB;
    int _sideC;

    public int Seed1 {
        get { return _seed1; }
    }
    public int Seed2 {
        get { return _seed2; }
    }
    public int Size {
        get { return _size; }
    }
    public int SideA {
        get { return _sideA; }
    }
    public int SideB {
        get { return _sideB; }
    }
    public int SideC {
        get { return _sideC; }
    }
    public int Perimeter {
        get { return _sideA + _sideB + _sideC; }
    }

    public PythagoreanTriple() : this(1, 1, 1) { }
    public PythagoreanTriple(int seed1, int seed2) : this(seed1, seed2, 1) { }
    public PythagoreanTriple(int seed1, int seed2, int size) {
        _seed1 = seed1;
        _seed2 = seed2;
        _size = size;
        calculateTriple();
    }

    void calculateTriple() {
        int seed1pow2 = _seed1 * _seed1 * _size;
        int seed2pow2 = _seed2 * _seed2 * _size;

        _sideA = seed1pow2 - seed2pow2;
        _sideB = 2 * _seed1 * _seed2 * _size;
        _sideC = seed1pow2 + seed2pow2;
    }
    public override bool Equals(object obj) {
        PythagoreanTriple p = obj as PythagoreanTriple;
        if (p == null)
            return false;
        return _seed1 == p._seed1 && _seed2 == p._seed2 && _size == p._size;
    }
    public override int GetHashCode() {
        return _sideA;
    }
    public override string ToString() {
        return string.Format("({0}, {1}, {2})", _sideA, _sideB, _sideC);
    }
}

SideA, SideB, SideC แทนด้านต่าง ๆ ของสามเหลี่ยม
Seed1 กับ Seed2 แทนค่าตัวเลข 2 ตัวสำหรับคำนวนสร้างสามเหลี่ยม
Size คือตัวคูณของ Primitive Pythagorean triple สำหรับสร้างสามเหลี่ยมปีธากอรัสแบบอื่น ๆ
Perimeter คือ เส้นรอบสามเหลี่ยมครับ

เราได้สามเหลี่ยมปีธากอรัสแล้ว แต่ยังไม่จบ
ต่อไปเราจะมาสร้างตัว Generate สามเหลี่ยมปีธากอรัสแบบต่าง ๆ
แต่ก่อนอื่นเราต้องมี Method สำหรับหาค่า หารร่วมมาก ก่อน

public static int Gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

เอา Method ด้านบนไปไว้ใน Static Class สำหรับรวม Static Method
(Static Class ของผมชื่อ Math2 เอาไว้เก็บสูตรเลขต่าง ๆ)

คราวนี้เรามาสร้างตัว Generate สามเหลี่ยมปีธากอรัสได้แล้วครับ
(BaseSequence เอามาจาก Post นี้ นะครับ) 

public class Pythagorean : BaseSequence<PythagoreanTriple> {
    protected override IEnumerable<PythagoreanTriple> Enumerate() {
        for (int m = 2; ; m++) {
            for (int n = (m % 2 == 0) ? 1 : 2; n < m; n += 2) {
                if (Math2.Gcd(m, n) == 1)
                    yield return new PythagoreanTriple(m, n);
            }
        }
    }
}

ไม่กี่บรรทัดก็เสร็จแล้ว ง่ายไหมครับ
ค่า m และ n จะเช็คการเป็นจำนวนเฉพาะสัมพัทธ์ก่อน
ดังนั้น สามเหลี่ยมปีธากอรัส ที่ถูก Generate มาทั้งหมด เป็น Primitive Pythagorean triple

ตัวอย่างจากคำถามจาก projecteuler.net
Find product abc of Pythagorean triplet, for which a + b + c = 1000.
"หาผลคูณของด้านต่าง ๆ ของสามเหลี่ยมปีธากอรัส โดยที่สามเหลี่ยมนั้นมีเส้นรอบวงเท่ากับ 1000"

var p = new Pythagorean().First(x => 1000 % x.Perimeter == 0);
p = new PythagoreanTriple(p.Seed1, p.Seed2, 1000 / p.Perimeter);
Console.WriteLine(p.SideA * p.SideB * p.SideC);
//31875000

บรรทัดแรกคือ หา Primitive Pythagorean triple ใด ๆ ที่มีเส้นรอบวงที่เป็นตัวหารของ 1000
บรรทัดที่ 2 คือ สร้างสามเหลี่ยมใหม่ โดยกำหนด Seed1 และ Seed2 เท่ากับสามเหลี่ยมเดิม
และกำหนด Size ใหม่
วิธีหา Size คือ เอาเส้นรอบสามเหลี่ยมที่ต้องการ / เส้นรอบสามเหลี่ยมปัจจุบัน
บรรทัดที่ 3 คือ การหาผลคูณของด้านต่าง ๆ

If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?
"เส้นรอบสามเหลี่ยมมุมฉากความยาวเท่าใดที่น้อยกว่า 1000 ที่เป็นเส้นรอบสามเหลี่ยม ของสามเหลี่ยมมุมฉากแบบต่าง ๆ มากที่สุด"

int[] list = new int[1000];
int maxSeed1 = (int)Math.Sqrt(500); //maxSeed1 = Sqrt(targetPerimeter/2)

new Pythagorean().TakeWhile(p => p.Seed1 <= maxSeed1).ForEach(p => {
    for (int i = p.Perimeter; i < 1000; i += p.Perimeter)
        list[i]++;
});
Console.WriteLine(0.To(999).OrderByDescending(x => list[x]).First());
//840

บรรทัดแรกสร้าง list สำหรับเก็บเส้นรอบสามเหลี่ยมความยาวต่าง ๆ 1000 แบบ
บรรทัดที่ 2 คือ หาจุดสิ้นสุดในการ Generate สามเหลี่ยมมุมฉาก
นั่นก็คือ การหาค่าของ Seed1 ที่ทำให้เส้นรอบสามเหลี่ยมไม่เกิน 1000
สูตรหาเส้นรอบสามเหลี่ยม คือ a + b + c = 1000
เมื่อนำค่า m และ n มาแทนจะได้ (m² - n²) + 2mn + (m² + n²) = 1000
ให้ n มีค่าเท่ากับ 1 เพื่อหา Maximum ของ m ที่จะทำให้เส้นรอบสามเหลี่ยมเป็น 1000
(m² - 1) + 2m + (m² + 1) = 1000
2m² + 2m = 1000
2m(m + 1) = 1000
คิดคร่าว ๆ จะได้ว่า Maximum ของ m คือ sqrt(500)

Code บรรทัดที่ 3 คือ การสร้าง Primitive Pythagorean triple
และบวกเพิ่มใน list สำหรับเส้นรอบสามเหลี่ยมที่ triple นั้นสามารถเป็นได้
Code บรรทัดสุดท้าย คือ การหาลำดับของ list ที่มีค่ามากที่สุด

จบแล้วครับสำหรับลำดับต่าง ๆ
Code ตัวอย่างอธิบายยากมากครับ ถ้าไม่เข้าใจก็ถามได้
คราวหน้ามาเปลี่ยนสไตล์การเขียน Program กันดีกว่าครับ
หัวข้อคราวหน้าคือ การเขียน Functional Programming ด้วย C#

* อ่านจบแล้ว กรุณา Comment ด้วยครับ เพื่อเป็น Feedback และเป็นกำลังใจ
* บทความนี้คัดลอกได้ แต่ต้องมี Link หรือ Url กลับมาที่หน้านี้ และเมื่อคัดลอกแล้วกรุณา Comment แจ้งด้วยครับ

Create Date : 26 กรกฎาคม 2551
Last Update : 9 สิงหาคม 2551 15:26:45 น.		5 comments
Counter : 4482 Pageviews.
Share Tweet