ในทางคณิตศาสตร์ จำนวนออยเลอร์ เป็นเลขผสมชนิดพิเศษ กำหนดจำนวนการเรียงสับเปลี่ยนที่องค์ประกอบถัดไปเป็นจำนวนเฉพาะที่มากกว่าองค์ประกอบก่อนหน้า
แสดงเป็น
A(n, m) เป็นการเรียงสับเปลี่ยนจาก 1 เป็น n โดยที่ตัวเลขสองตัวแปรผันตาม m.
คำชี้แจงปัญหา: ในปัญหานี้ เราได้รับตัวเลขสองตัว m และ n และเราต้องหาจำนวนการเรียงสับเปลี่ยนที่เป็นจำนวนออยเลอร์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: n =4, m =2
ผลลัพธ์: 11
คำอธิบาย:
การเรียงสับเปลี่ยนของตัวเลขตั้งแต่ 1 ถึง 4 คือ −
1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2
2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1
3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1
4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1
จากการเรียงสับเปลี่ยนทั้ง 11 แบบมีความแตกต่างระหว่างตัวเลขสองตัว m
วิธีการแก้ปัญหา -
ในการหาจำนวนการเรียงสับเปลี่ยน เราจะใช้สูตรหาจำนวนออยเลอร์
A(n, m) =0 ถ้า m> n หรือ n =0
A(n, m) =1 ถ้า m =0
A(n, m) =(n-m)A(n-1, m-1) + (m+1)A(n-1, m)
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
int countEulerianNumber(int n, int m)
{
if (m >= n || n == 0)
return 0;
if (m == 0)
return 1;
return ( ( (n - m) * countEulerianNumber(n - 1, m - 1) ) + ( (m + 1) * countEulerianNumber(n - 1, m) ) );
}
int main() {
int n = 5, m = 3;
cout<<"The number of Eulerian permutations is "<<countEulerianNumber(n, m);
return 0;
} ผลลัพธ์ -
The number of Eulerian permutations is 26
