จำนวนวิธีวางสิ่งของในตำแหน่ง n² ให้แถว/คอลัมน์ไม่มีมากกว่าหนึ่งใน C++

ในโจทย์นี้ เราได้รับจำนวนเต็ม n ซึ่งมีเส้นแนวตั้ง n เส้น และเส้นแนวนอน n เส้น วางไว้จนมีจุดตัด n² จุดระหว่างเส้นเหล่านี้ งานของเราคือหาจำนวนวิธีทั้งหมดที่จะวางสิ่งของ 4 ชิ้นบนจุดตัดเหล่านี้ โดยที่ไม่มีแถวและคอลัมน์ไหนมีสิ่งของมากกว่าหนึ่งชิ้น

ตัวอย่าง

อินพุต

n = 4

เอาต์พุต

24

คำอธิบาย

เพื่อแก้ปัญหานี้ เราจะต้องเลือก 4 เส้นแนวนอนจาก n เส้นที่จะมีสิ่งของ ซึ่งจะเป็น nC4 ตอนนี้ ทุกเส้นแนวนอนมีเส้นแนวตั้ง n เส้น ดังนั้นจะมี n วิธีในการวางสิ่งของในเส้นแนวนอนแรกที่เลือก ต่อไป เราจะไปยังเส้นแนวนอนที่เลือกต่อไป ซึ่งจะมี n-1 ตำแหน่งที่เป็นไปได้ และเช่นเดียวกัน ตัวที่สามวางได้ n-2 วิธี และตัวที่สี่วางได้ n-3 วิธี ดังนั้น จำนวนวิธีทั้งหมดจะเป็น:

ⁿC₄ * 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 ways in which 4 items can be placed in the intersection of " << n;
    cout << " lines vertically and horizontally are " << placeItems(n);
    return 0;
}

ผลลัพธ์

The number of ways in which 4 items can be placed in the intersection of 4 lines vertically and horizontally are 24