ในบทความนี้ เราจะอธิบายวิธีการหาจำนวนความสัมพันธ์แบบสะท้อนกลับในชุด ในปัญหานี้ เราได้รับหมายเลข n และชุดของ n จำนวนธรรมชาติ เราต้องกำหนดจำนวนของความสัมพันธ์สะท้อนกลับ
ความสัมพันธ์แบบสะท้อนกลับ − ความสัมพันธ์ในชุด 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.
แนวทางในการหาแนวทางแก้ไข
จำนวนความสัมพันธ์แบบสะท้อนกลับบนชุดองค์ประกอบสามารถแก้ไขได้โดยสูตร 2n2−n สูตรทั่วไปนี้สร้างขึ้นโดยการคำนวณจำนวนความสัมพันธ์แบบสะท้อนกลับของจำนวนเต็ม
ตัวอย่าง
#include <iostream>
using namespace std;
int countReflexive(int n){
int ans = 1 << (n*n - n);
return ans;
}
int main(){
int n ;
cin >> n ; // taking input n from the user using std cin.
int result = countReflexive(n); // calling function to calculate number of reflexive relations
cout << "Number of reflexive relations on set: " << result ; // printing the answer
return 0;
} ผลลัพธ์
Number of reflexive relations on set: 1
คำอธิบายของโปรแกรมข้างต้น
โปรแกรมนี้เข้าใจง่าย เนื่องจากเราเพียงแค่รับข้อมูลจากผู้ใช้และใส่ลงในสูตร 2n2−n และเรากำลังใช้ตัวดำเนินการ "<<" กะด้านซ้ายในการคำนวณสูตร ความซับซ้อนของเวลาของรหัสนี้คือ O(1) ซึ่งจะช้าลงเมื่อขนาด n เพิ่มขึ้น
บทสรุป
ในบทความนี้ เราแก้ปัญหาเพื่อค้นหาจำนวนความสัมพันธ์สะท้อนกลับในชุด เราได้พูดคุยถึงแนวทางง่ายๆ ในการแก้ปัญหาที่กำหนด โดยเป็นสูตรในการคำนวณจำนวนความสัมพันธ์แบบสะท้อนกลับโดยนักคณิตศาสตร์
นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้โดยที่เราพบวิธีแก้ปัญหาด้วยความซับซ้อนของเวลาของ O(1) เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ
