หาจำนวนความสัมพันธ์รีเฟลกซีฟ (Reflexive Relations) บนเซตด้วย C++

ในบทความนี้ เราจะอธิบายวิธีการหาจำนวนความสัมพันธ์รีเฟลกซีฟ (Reflexive Relations) บนเซต ในโจทย์นี้ เราได้รับตัวเลข n และบนเซตของจำนวนธรรมชาติ n ตัว เราต้องหาจำนวนความสัมพันธ์รีเฟลกซีฟ

Reflexive Relation (ความสัมพันธ์รีเฟลกซีฟ) - ความสัมพันธ์ในเซต A เรียกว่ารีเฟลกซีฟ หาก (a, a) อยู่ใน R สำหรับทุก 'a' ที่อยู่ในเซต A ตัวอย่าง:

Input : x = 1 Output : 1 Explanation : set = { 1 }, reflexive relations on A * A : { { 1 } }
Input : x = 2 Output : 4 Explanation : set = { 1,2 }, reflexive relations on A * A : { (1,1),(2,2) }, { (1,1),(2,2),(1,2) }, { (1,1),(2,2),(1,2),(2,1) }, { (1,1),(2,2),(2,1) }

ดังนั้น ความสัมพันธ์จะเป็นรีเฟลกซีฟ หาก: (a, a) ∈ R ∀ a ∈ A

วิธีการหาคำตอบ

จำนวนความสัมพันธ์รีเฟลกซีฟบนเซต n องค์ประกอบ สามารถแก้ได้โดยสูตร 2^(n²-n) สูตรทั่วไปนี้ได้มาจากการคำนวณจำนวนความสัมพันธ์รีเฟลกซีฟของจำนวนเต็ม

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

int countReflexive(int n) {
    int ans = 1 << (n*n - n);
    return ans;
}

int main() {
    int n;
    cin >> n; // รับอินพุต n จากผู้ใช้ผ่าน std cin
    int result = countReflexive(n); // เรียกฟังก์ชันคำนวณจำนวนความสัมพันธ์รีเฟลกซีฟ
    cout << "Number of reflexive relations on set: " << result; // พิมพ์คำตอบ
    return 0;
}

ผลลัพธ์

Number of reflexive relations on set: 1

คำอธิบายโปรแกรม

โปรแกรมนี้เข้าใจง่าย เพราะเราแค่รับอินพุตจากผู้ใช้ และนำไปแทนในสูตร 2^(n²-n) และเราใช้ตัวดำเนินการเลื่อนซ้าย "<<" สำหรับคำนวณสูตร ความซับซ้อนด้านเวลาของโค้ดนี้คือ O(1) ซึ่งจะช้าลงเมื่อขนาดของ n เพิ่มขึ้น

สรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวนความสัมพันธ์รีเฟลกซีฟบนเซต เราอภิปรายวิธีการง่ายๆ ในการแก้ปัญหาที่กำหนด โดยมีสูตรสำหรับคำนวณจำนวนความสัมพันธ์รีเฟลกซีฟที่นักคณิตศาสตร์ได้สรุปไว้

เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้ ซึ่งเราหาคำตอบด้วยความซับซ้อนด้านเวลา O(1) สามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python ได้เช่นกัน