วิธีวางรายการในตำแหน่ง n^2 โดยที่ไม่มีแถว/คอลัมน์ใดมีมากกว่าหนึ่งรายการใน C++

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

ในลักษณะที่ไม่มีแถวและคอลัมน์ใดมีมากกว่าหนึ่งรายการ

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

n=4

ผลลัพธ์

24

คำอธิบาย

ในการแก้ปัญหานี้ เราจะต้องเลือกเส้นแนวนอน 4 เส้นจาก n เส้น ซึ่งจะมีรายการที่จะเป็น nC4 ตอนนี้ เส้นแนวนอนทุกเส้นมี n เส้นแนวตั้ง ดังนั้นจะมี n วิธีที่จะวางรายการในเส้นแนวนอนที่เลือกเส้นแรก จากนั้น เราจะย้ายไปยังเส้นแนวนอนถัดไปที่เลือก ซึ่งจะมีตำแหน่งที่เป็นไปได้ n-1 และมันก็เหมือนกับวิธีที่สาม ที่จะใส่ใน n-2 และออกมาใน n-3 วิธี ดังนั้นจำนวนวัตต์ทั้งหมดจะเป็น ⁿ C4*n*(n-1)*(n-2)*(n-3)

โปรแกรมแสดงการใช้งานอัลกอริทึม

ตัวอย่าง

#include <iostream>
using namespace std;
long long placeItems(int n) {
   return (1LL * (1LL *
   ((n) * (n - 1) * (n - 2) * (n - 3)) / (4 * 3 * 2 * 1)) *
   ((1LL * (n) * (n - 1) * (n - 2) * (n - 3))));
}
int main() {
   int n = 4;
   cout<<"The number of way is which 4 items can be placed in the intersection of "<<n;
   cout<<" lines vertically and horizotally are "<<placeItems(n);
   return 0;
}

ผลลัพธ์

The number of way is which 4 items can be placed in the intersection of 4 lines vertically and horizotally are 24