Դասավորել դասը ՝ օգտագործելով ռեկուրսիան


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Goldman Sachs-ը IBM Կուլիզա Անտաշ անասուն նողկալի արարած
Ռեկուրսիա Գրապահոց

Խնդիրի հայտարարություն

«Դասավորել կույտը ՝ օգտագործելով ռեկուրսիան» խնդիրը ասում է, որ ձեզ տրվում է ա բուրգ տվյալների կառուցվածքը: Տեսակ ռեկուրսիան օգտագործող դրա տարրերը: Դեղի միայն ստորև թվարկված գործառույթները կարող են օգտագործվել -

  • հրում (տարր) - տարրը բուրգում տեղադրելու համար:
  • pop () - pop () - տվյալ բուրգի վերին մասում գտնվող տարրը հեռացնելու / ջնջելու համար:
  • isEmpty () - ստուգելու համար, թե դեղի մեջ կա՞ որևէ տարր, թե ոչ:
  • top () - զննել / տեսնել տվյալ դեղի վերին մասում գտնվող տարրը:

Դասավորել դասը ՝ օգտագործելով ռեկուրսիան

Օրինակ

9 4 2 -1 6 20
20 9 6 4 2 -1

Բացատրություն. Քանի որ դեղը դասավորված է աճման կարգով: Առավելագույն տարրը գալիս է վերևում: Քանի որ բուրգը LIFO տվյալների կառուցվածք է, արդյունքը կարծես թե նվազման կարգով է:

2 1 4 3 6 5
6 5 4 3 2 1

Ալգորիթմ

  1. Նախաձեռնել ա բուրգ և դրանում տարրեր մղել:
  2. Ստեղծեք ֆունկցիա ՝ տարրերը դասավորված կարգով ներդիրի շարքում, որն ընդունում է տողը և տարրը որպես պարամետր: Ստուգեք, թե դեղը դատարկ է, թե տվյալ տարրը ավելի մեծ է, քան դեղի վերևում գտնվող տարրը, հրեք տարրը դեղի մեջ և վերադարձեք:
  3. Ստեղծեք ժամանակավոր փոփոխական և պահեստի վերին մասը պահեք դրանում: Փոփի վերին մասում գտնվող տարրը և հետադարձ զանգը կատարեք հենց գործառույթի վրա: Ushամանակավոր փոփոխականը մղեք դեղի մեջ:
  4. Նմանապես, ստեղծեք գործառույթի տեսակավորումը (), որն ընդունում է տողը որպես պարամետր: Ստուգեք, արդյոք տուփը դատարկ չէ, ստեղծեք x փոփոխական և պահեստի վերին մասը պահեք դրա մեջ: Պատի վերևում գտնվող տարրը փչեք: Կատարեք ռեկուրսիվ զանգ դեպի գործառույթը: Callանգահարեք ֆունկցիան ՝ տարրերը դասավորված կարգով ներս մտցնելու համար:
  5. Callանգահարեք տեսակավորման գործառույթը հիմնականում ():
  6. Ստեղծեք գործառույթ ՝ տեսակավորված բույրը տպելու համար, որն ընդունում է դեղը որպես պարամետր: Դեպի մինչ դատարկը դատարկվելն անցնելն է, տպեք տուփի տվյալները և անցեք հաջորդ տարրին:

Կոդ

C ++ ծրագիր ՝ դասը հետքի միջոցով օգտագործելու համար

#include <iostream> 
using namespace std; 
  
struct stack{  
    int data;  
    struct stack *next;  
};  
  
void initStack(struct stack **s){  
    *s = NULL;  
}  
  
int isEmpty(struct stack *s){  
    if(s == NULL){  
        return 1;  
    }    
    return 0;  
}  
  
void push(struct stack **s, int x){
    
    struct stack *p = (struct stack *)malloc(sizeof(*p));  
  
    if(p == NULL){  
        return;  
    }  
  
    p->data = x;  
    p->next = *s;  
    *s = p;  
}  
  
int pop(struct stack **s){  
    int x;  
    struct stack *temp;  
  
    x = (*s)->data;  
    temp = *s;  
    (*s) = (*s)->next;  
    free(temp);  
  
    return x;  
}  
  
int top(struct stack *s){  
    return (s->data);  
}  
  
void InsertWithSort(struct stack **s, int x){  
    
    if(isEmpty(*s) or x > top(*s)){  
        push(s, x);  
        return;  
    }  
  
    int temp = pop(s);  
    InsertWithSort(s, x);  
  
    push(s, temp);  
}  
  
void sort(struct stack **s){  
    
    if(!isEmpty(*s)){  
        int x = pop(s);  
  
        sort(s);  
  
        InsertWithSort(s, x);  
    }  
}  
  
void print(struct stack *s){  
    while(s){  
        cout<<s->data<<" "; 
        s = s->next;  
    }  
}  
  
int main(){  
    struct stack *top;  
  
    initStack(&top);
    
    push(&top, 9);  
    push(&top, 4);  
    push(&top, 2);  
    push(&top, -1);  
    push(&top, 6);
    push(&top, 20);
  
    sort(&top);  
    
    print(top);  
  
    return 0;  
}
20 9 6 4 2 -1

Java ծրագիր ՝ բուրգը դասավորելու համար օգտագործելով ռեկուրսիան

import java.util.ListIterator; 
import java.util.Stack; 
  
class SortStack{ 
    
    static void InsertWithSort(Stack<Integer> s, int x){ 
        if (s.isEmpty() || x > s.peek()){ 
            s.push(x); 
            return; 
        } 
       
        int temp = s.pop(); 
        InsertWithSort(s, x); 
       
        s.push(temp); 
    } 
       
    static void sort(Stack<Integer> s){ 
        if(!s.isEmpty()){ 
            int x = s.pop(); 
       
            sort(s); 
       
            InsertWithSort(s, x); 
        } 
    } 
      
    static void print(Stack<Integer> s){ 
       ListIterator<Integer> lt = s.listIterator(); 
         
        while(lt.hasNext()){ 
            lt.next(); 
        }       
         
        while(lt.hasPrevious()){ 
           System.out.print(lt.previous()+" ");
        }   
    } 
    
    public static void main(String[] args){
        Stack<Integer> s = new Stack<>(); 
        
        s.push(9);  
        s.push(4);  
        s.push(2);  
        s.push(-1);  
        s.push(6);
        s.push(20); 
       
        sort(s); 
       
        print(s); 
       
    } 
}
20 9 6 4 2 -1

Բարդության վերլուծություն

Timeամանակի բարդություն

Ո (N ^ 2) որտեղ n - կույտի տարրերի քանակը: Քանի որ, երբ մենք տարրը մղում ենք դեղի մեջ, մենք կարող ենք վերջապես հեռացնել բոլոր այն տարրերը, որոնք ներկայումս առկա են բուրգում և այնուհետև տեղադրել այն: Այս դեպքը տեղի է ունենում, եթե մուտքագրումը նվազման կարգով է:

Տիեզերական բարդություն

ՎՐԱ) քանի որ մենք օգտագործել ենք stack space n տարրերի համար: Միևնույն ժամանակ, տարրերը հեռացնելիս տեղադրեք մեր ներկա տարրը: Մենք ստիպված էինք պահպանել հեռացված տարրերը, ինչը մեզ գծային տիեզերական բարդություն է հաղորդում: