Pancake çeşidlənməsi problemi

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon Facebook microsoft kvadrat Über
Geyim çeşidləyiciBaxılıb 426

Problem bəyanat

"Pancake Sorting Problem", pancake çeşidlənməsinə əsaslanır. Çeşidlənməmiş verilmişdir array, serialı sıralamaq üçün yalnız çevirmə əməliyyatından istifadə edən bir proqram yazmalıyıq. Flip, massivi tərsinə çevirən əməliyyatdır.

Giriş Formatı

Bir tam ədədi olan ilk sətir.

N boşluqla ayrılmış tam ədədi olan ikinci sətir.

Çıxış formatı

N boşluqla ayrılmış tam ədədi ehtiva edən ilk və tək sətir sıralanmış massivi bildirir.

Məhdudiyyətlər

  • 1 <= n <= 10 ^ 3
  • 1 <= a [i] <= 10 ^ 6

misal

9
40 35 12 30 35 20 6 90 80
6 12 20 30 35 35 40 80 90

Yanaşma

O (nlogn) zaman mürəkkəbliyinə malik bir alqoritm yazmalıyıq. Pancake çeşidləmə alqoritmindən istifadə etsək, alınan vaxt O (nlogn) olacaq, çünki bir döngədə O (n) vaxt alan maksimum elementi tapacağıq. Zamanın mürəkkəbliyini azaltmaq üçün daxil etmə növü, ikili axtarış və çevirmə əməliyyatından istifadə edəcəyik.

Əsas fikir, ikili axtarışdan istifadə edərək arr [0, .. i-1] içərisində arr [i] dən böyük olan arr [j] elementini tapmaqdır. İndi, flip əməliyyatını istifadə edərək arr [j] -dən əvvəl arr [i] əlavə etməliyik.

Pancake Sıralama Problemi üçün Alqoritm

1. Arr [i] -dən [array] -dən böyük olan ən kiçik elementin indeksini tapın [0..i-1] yəni, j = ceilSearch (arr, 0, i-1, arr [i]), burada 0 başlanğıc göstəricisidir , (i-1) bitən indeksdir

        Axtarış Alqoritmi:

Verilən saydan böyük olan ən kiçik rəqəm, həmin rəqəmin tavanı kimi tanınır

  • Verilmiş element (arr [i]) müəyyən bir ölçülü massivdəki ilk elementdən az və ya bərabərdirsə, onda birinci elementin indeksini qaytarın.
  • Əgər element son elementdən böyükdürsə, onda -1 qaytarın, yəni daha böyük element yoxdur.
  • Burada, element orta elementlə eynidirsə, orta indeksə qayıdın.
  • Element orta elementdən böyükdürsə, ya orta elementin növbəti elementi [i] arrın tavanıdır, ya da tavan [mid + 1… .high] arrında yerləşir.
  • Element orta elementdən azdırsa, ya orta elementə əvvəlki element arr [i] tavanıdır, ya da tavan arr [low… .mid-1] içindədir.

2. İndi flip əməliyyatları istifadə edərək arr [j] əvvəl arr [i] elementini daxil etməliyik

  • elementləri indeks 0-dan j-1 indeksinə çevirin.
  • İndi elementləri indeks 0-dan indeks i-1-ə çevirin.
  • elementləri indeks 0-dan indeksə çevir.
  • elementləri indeks 0-dan j-yə çevirin.

3. Sıralanmış massivi çap edin.

Həyata keçirilməsi

Pancake Sıralama Problemi üçün C ++ Proqramı

#include<bits/stdc++.h> 
using namespace std; 

int ceilSearch(int arr[], int low, int high, int x) 
{ 
  int mid; 
  if(x <= arr[low]) 
    return low; 
  if(x > arr[high]) 
    return -1; 
  mid = (low + high)/2;
  if(arr[mid] == x) 
    return mid; 
  if(arr[mid] < x) 
  { 
    if(mid + 1 <= high && x <= arr[mid+1]) 
      return mid + 1; 
    else
      return ceilSearch(arr, mid+1, high, x); 
  } 
  if(mid - 1 >= low && x > arr[mid-1]) 
  {
    return mid;
  }
  else
  {
      return ceilSearch(arr, low, mid - 1, x);
  }
} 

void flip(int arr[], int i) 
{ 
  int temp, start = 0; 
  while (start < i) 
  { 
    temp = arr[start]; 
    arr[start] = arr[i]; 
    arr[i] = temp; 
    start++; 
    i--; 
  } 
} 

void sorting(int arr[], int size) 
{ 
  int i, j; 
  for(i = 1; i < size; i++) 
  { 
    int j = ceilSearch(arr, 0, i-1, arr[i]);
    if (j != -1) 
    { 
      flip(arr, j-1); 
      flip(arr, i-1); 
      flip(arr, i); 
      flip(arr, j); 
    } 
  } 
} 

int main() 
{ 
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  sorting(a, n); 
  for(int i=0;i<n;i++) 
  {
      cout<<a[i]<<" ";
  }
  return 0; 
}

Pancake Sıralama Problemi üçün Java Proqramı

import java.util.Scanner;
class sum
{
    public static int ceilSearch(int arr[], int low, int high, int x) 
    { 
            int mid; 
            if(x <= arr[low]) 
                    return low; 
            if(x > arr[high]) 
                    return -1; 
            mid = (low + high)/2;
            if(arr[mid] == x) 
                    return mid; 
            if(arr[mid] < x) 
            { 
                    if(mid + 1 <= high && x <= arr[mid+1]) 
                            return mid + 1; 
                    else
                            return ceilSearch(arr, mid+1, high, x); 
            } 
            if(mid - 1 >= low && x > arr[mid-1]) 
            {
                    return mid;
            }
            else
            {
                return ceilSearch(arr, low, mid - 1, x);
            }
    } 

    public static void flip(int arr[], int i) 
    { 
            int temp, start = 0; 
            while (start < i) 
            { 
                    temp = arr[start]; 
                    arr[start] = arr[i]; 
                    arr[i] = temp; 
                    start++; 
                    i--; 
            } 
    } 

    public static void sorting(int arr[], int size) 
    { 
            int i; 
            for(i = 1; i < size; i++) 
            { 
                    int j = ceilSearch(arr, 0, i-1, arr[i]);
                    if (j != -1) 
                    { 
                            flip(arr, j-1); 
                            flip(arr, i-1); 
                            flip(arr, i); 
                            flip(arr, j); 
                    } 
            } 
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int [n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        sorting(a, n); 
  for(int i=0;i<n;i++) 
  {
      System.out.print(a[i]+" ");
  }
        System.out.println();
    }
}
5
67 2 43 13 87
2 13 43 67 87

Pancake Sıralama Problemi üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n ^ 2) hara n verilmiş massivin ölçüsüdür.

  • Alqoritmdə, ilə bir döngə işlədirik N təkrarlamalar.
  • Hər təkrarlamada siyahının müvafiq prefiksi ilə məşğul oluruq. Burada prefiksin uzunluğunu belə qeyd edirik məsələn birinci təkrarlamada prefiksin uzunluğu N-dir, ikinci təkrarlamada prefiksin uzunluğu N-1.

Kosmik Mürəkkəblik

O (n) hara n verilmiş massivin ölçüsüdür.

  • Alqoritm daxilində, son nəticələrin qorunması üçün pancake flips sayına mütənasib bir siyahı istifadə edirik.
  • Hər təkrarlama dövrü üçün ən çox iki pancake flipsi əlavə edərdik. Bu səbəbdən, lazım olan maksimum pancake flips sayının olması lazımdır .
  • Nəticədə, alqoritmin kosmik mürəkkəbliyi . Biri funksiyanın nəticəsini tutmaq üçün lazım olan yeri nəzərə almırsa, yuxarıdakı alqoritmi sabit bir məkan həlli kimi qəbul etmək olar.
Translate »