เราได้รับอาร์เรย์ของตัวเลขระหว่าง 1 ถึง n เป้าหมายที่นี่คือการค้นหาหมายเลข ของการดำเนินการ 'moveto front' ที่จำเป็นในการจัดเรียงอาร์เรย์ที่กำหนด อาร์เรย์ไม่มีการซ้ำซ้อน การดำเนินการ "ย้ายไปด้านหน้า" จะเลือกองค์ประกอบและวางไว้ที่ตำแหน่งแรก ที่นี่ที่ดัชนี 0
เราจะสำรวจอาร์เรย์จากจุดสิ้นสุด หากองค์ประกอบอยู่ในตำแหน่งที่ถูกต้อง ก็ไม่จำเป็นต้องย้ายอย่างอื่น สำหรับองค์ประกอบตั้งแต่ 1 ถึง n ตำแหน่งที่ถูกต้องในอาร์เรย์ขององค์ประกอบ arr[i] ควรอยู่เหนือดัชนี i+1 arr[0] ควรเป็น 1, arr[1] ควรเป็น 2 และ…….arr[n-1] ควรเป็น n.
อินพุต
Arr[]= { 4,3,2,1 } ผลลัพธ์
Minimum move-to-front operations: 3
คำอธิบาย
Pull 3, 3,4,2,1 count=1 Pull 2, 2,3,4,1 count=2 Pull 1, 1,2,3,4 count=3
อินพุต
Arr[]= { 6,1,2,5,4,3 } ผลลัพธ์
Minimum move-to-front operations: 5
คำอธิบาย
Pull 5, 5,6,1,2,4,3 count=1 Pull 4, 4,5,6,1,2,3 count=2 Pull 3, ,4,5,6,1,2 count=3 Pull 2, 2,3,4,5,6,1 count=4 Pull 1, 1,2,3,4,5,6 count=5
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
Integer array Arr[] เก็บตัวเลข 1 ถึง n
-
ขนาดตัวแปรจำนวนเต็มเก็บความยาวของอาร์เรย์ Arr[]
-
ฟังก์ชัน movetoFront(int arr[], int n) รับอาร์เรย์และความยาวเป็นอินพุตและส่งกลับจำนวนขั้นต่ำของการดำเนินการ "เลื่อนไปด้านหน้า" ที่จำเป็นในการจัดเรียงอาร์เรย์ที่กำหนด
-
ตัวแปร Count เริ่มต้นด้วยขนาดของอาร์เรย์ เนื่องจากองค์ประกอบทั้งหมดสามารถย้ายได้ในกรณีที่อาร์เรย์ลำดับลดลง
-
เริ่มสำรวจจากดัชนีสุดท้ายและเคลื่อนไปทางด้านหน้า หากค่าองค์ประกอบเหมือนกับการนับ (สำหรับองค์ประกอบที่เรียงลำดับระหว่าง 1 ถึง n n คือค่าสุดท้าย n-1 จะเป็นลำดับที่สองและต่อไปเรื่อยๆ) จากนั้นให้ลดจำนวนลงตามองค์ประกอบนั้น ในตำแหน่งที่ถูกต้อง
-
ด้วยวิธีนี้เมื่อสิ้นสุดการวนซ้ำ การนับ ได้ผลลัพธ์ที่ต้องการ
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
// Calculate minimum number of moves to arrange array
// in increasing order.
int movetoFront(int arr[], int n){
//take count as all elements are correctly placed
int count = n;
// Traverse array from end
for (int i=n-1; i >= 0; i--){
// If current item is at its correct position,
//decrement the count
//range is 1 to n so every arr[i] should have value i+1
//1 at 0 index, 2 at 1 index........
if (arr[i] == count)
count--;
}
return count;
}
int main(){
int Arr[] = {5, 3, 4, 7, 2, 6, 1};
int size = 7;
cout <<"Minimum 'move-to-front' to sort array:"<< movetoFront(Arr, size);
return 0;
} ผลลัพธ์
Minimum 'move-to-front' to sort array:6
