จำนวนการเคลื่อนไหวขั้นต่ำที่จำเป็นในการทำให้ N หารด้วย 25 ลงตัวโดยใช้ C++

คำชี้แจงปัญหา

กำหนดจำนวน N โดยไม่มีศูนย์นำหน้า ภารกิจคือการหาจำนวนการเคลื่อนไหวขั้นต่ำที่จำเป็นในการทำให้ N หารด้วย 25 ลงตัว ในแต่ละการเคลื่อนไหว เราสามารถสลับตัวเลขสองหลักที่อยู่ติดกัน และตรวจดูให้แน่ใจว่าตัวเลขจะต้องไม่มีเลขศูนย์นำหน้าตลอดเวลา หากไม่สามารถทำให้ N หารด้วย 25 ลงตัว ให้พิมพ์ -1

ถ้า N =5071 ต้องใช้ 4 การเคลื่อนไหวเพื่อให้หารด้วย 25 ลงตัว

5071 → 5701 → 7501 → 7510 → 7150

อัลกอริทึม

<ก่อน>1. วนซ้ำทุกคู่ของหลักในตัวเลข ให้ตัวเลขตัวแรกในคู่อยู่ที่ตำแหน่ง 'i' และตัวที่สองอยู่ที่ตำแหน่ง 'j'.2 วางตัวเลขเหล่านี้ลงในสองตำแหน่งสุดท้ายในตัวเลข 3 หากตัวเลขมีศูนย์นำหน้า ค้นหาตัวเลขที่ไม่ใช่ศูนย์ทางซ้ายสุดและย้ายไปยังตำแหน่งแรก4. หากตัวเลขปัจจุบันหารด้วย 25 ลงตัว ให้อัปเดตคำตอบด้วยจำนวนสวอป

ตัวอย่าง

#include #include #include #include using namespace std;int requiredMoves(long long n){ string str =to_string(n); int ans =INT_MAX; int len =str.size(); สำหรับ (int i =0; i  i); k  0; --k) { swap(temp[k], temp[k - 1]); ++cnt; } ยาว num =atoll(temp.c_str()); ถ้า (num % 25 ==0) ans =min(ans, cnt); } } if (ans ==INT_MAX) คืนค่า -1; ส่งคืน ans;}int main(){ int n =5071; cout <<"การเคลื่อนไหวที่จำเป็นขั้นต่ำ:" < ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 ย้ายขั้นต่ำที่ต้องการ:4