home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

นับพีชคณิตที่ลดลงครั้งแรกแล้วเพิ่มขึ้นใน C++

เราเป็นตัวแปรจำนวน เป้าหมายคือการหาจำนวนการเรียงสับเปลี่ยนของตัวเลขระหว่าง [1,num] ซึ่งตัวเลขจะลดลงก่อนแล้วค่อยเพิ่มขึ้น ตัวอย่างเช่น ถ้า num=3 ตัวเลขก็คือ 1,2,3 การเรียงสับเปลี่ยนจะเป็น [ 3,1,2 ] และ [2,1,3] และนับเป็น 2

เราทราบดีว่าในการเรียงสับเปลี่ยนแต่ละครั้ง การเปลี่ยนแปลงจากการลดจำนวนเป็นการเพิ่มจำนวนจะตัดสินตามตำแหน่งของ 1 ซึ่งน้อยที่สุด หลังจากแต่ละ 1 ตัวเลขจะเริ่มเพิ่มขึ้น เพื่อให้การเรียงสับเปลี่ยนลดลงแล้วเพิ่มขึ้น 1 ควรอยู่ระหว่างตำแหน่ง 2 และ num-1 [ → ...1…. → ].

หาก 1 อยู่ที่จุดเริ่มต้น ซีรีส์จะเพิ่มขึ้นเต็มที่ [ 1.. → ] หากอยู่ท้ายสุด ซีรีส์จะลดลงเต็มที่ [ … → 1 ]

สมมุติว่าเรามี num=4 แล้ว

วาง 1 ตำแหน่ง 2 [ - , 1, - , - ] สำหรับอันดับที่ 1 เราสามารถเลือกจาก ( 2,3,4) สมมติว่าเราเลือก 2 จากนั้นลำดับจะเป็น [ 2,1,3,4] ดังนั้นการเรียงสับเปลี่ยน 3C1 จึงเป็นไปได้ในกรณีนี้

วาง 1 ตำแหน่งที่ 3 [ -, -, 1, - ] สำหรับตำแหน่งที่ 1 และ 2 ให้เลือกสองในสาม (2,3,4) การเรียงสับเปลี่ยนทั้งหมดจะเป็น 3 C2 .

ดังนั้นการเรียงสับเปลี่ยนทั้งหมดจะเป็น = 3 C1 + 3 C2 สำหรับ num=4

สำหรับ num x ใดๆ การนับจะเป็น = x-1 C1 + x-1 C2 +.....+ x-1 Cc-2 =2x-1 - 2 จากทฤษฎีบททวินาม

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − num=4

ผลผลิต − จำนวนการเรียงสับเปลี่ยนที่ลดลงครั้งแรกแล้วเพิ่มขึ้นคือ:6

คำอธิบาย − การเรียงสับเปลี่ยนจะเป็น -

<ก่อนหน้า>[ 2, 1, 3, 4 ], [3, 1, 2, 4 ], [4, 1, 2, 3 ] → 1 ที่ตำแหน่งที่ 2[ 2, 3, 1, 4 ], [2, 4, 1, 3 ], [ 3, 4, 1, 2 ] → 1 ที่ตำแหน่งที่ 3

ป้อนข้อมูล − num=6

ผลผลิต − จำนวนการเรียงสับเปลี่ยนที่ลดลงครั้งแรกแล้วเพิ่มขึ้นคือ − 30

คำอธิบาย − การเรียงสับเปลี่ยนบางอย่างจะเป็น -

<ก่อนหน้า>[ 2, 1, 3, 4, 5, 6 ], [3, 1, 2, 4, 5, 6 ], [4, 1, 2, 3, 5, 6], [ 5, 1, 2, 3, 4, 6 ], [ 6, 1, 2, 3, 4, 5 ]……[ 6, 5, 4, 3, 1, 2].

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

ในแนวทางนี้ เราจะใช้ทฤษฎีบททวินามเพื่อคำนวณพีชคณิตโดยตรงจากสูตรข้างต้น นอกจากนี้ เราจะสร้างค่าฟังก์ชัน (long long i, long long num) ซึ่งจะคืนค่า i num

  • รับตัวแปร num เป็นอินพุต

  • ฟังก์ชัน permutations_increase_decrease(int num) ใช้ num และส่งกลับจำนวนการเรียงสับเปลี่ยนที่ลดลงในครั้งแรก แล้วเพิ่มจากตัวเลข 1 เป็น num

  • ค่าฟังก์ชัน (long long i, long long num) ใช้ในการคำนวณ (inum) % temp โดยที่ temp=1000000007.

  • ภายในพีชคณิต_increase_decrease(int num) ใช้ temp=1000000007

  • ถ้า num เป็น 1 จะไม่สามารถเปลี่ยนได้ ให้คืนค่า 0

  • ชุดอื่นนับ =(value(2, num - 1) - 2) % temp ); โดยใช้สูตร

  • ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง

#include ใช้เนมสเปซ std;ค่ายาวแบบยาว (แบบยาว i แบบยาว num){ int temp =1000000007; ถ้า (num ==0){ ส่งคืน 1; } ยาว ยาว j =ค่า (i, num / 2) % temp; j =(j * j) % อุณหภูมิ; if(num &1){ j =(j * i) % อุณหภูมิ; } ส่งคืน j;} int permutations_increase_decrease (int num) { int temp =1000000007; ถ้า (num ==1){ คืนค่า 0; } int count =(value(2, num - 1) - 2) % temp; นับกลับ;}int main(){ int num =4; cout<<"จำนวนการเรียงสับเปลี่ยนที่ลดลงครั้งแรกแล้วเพิ่มขึ้นคือ:"< 
ผลลัพธ์
 

 หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
 
จำนวนการเรียงสับเปลี่ยนที่ลดลงครั้งแรกแล้วเพิ่มขึ้นคือ:6