დალაგებული მიმდევრობიდან c-ს ტოლი ელემენტის წაშლის რეკურსიული ალგორითმი

ამოცანის პირობაა , რომ დავწეროთ რეკურსიული ალგორითმი , რომელიც დალაგებულ A მიმდევრტობიდან წაშლის c-ს ტოლ ელემენტს და დააბრუნებს შეცვლილ მიმდევრობას, თუ ასეთი ელემენტი მიმდევრობაში არ არის დააბრუნებს ამ მიმდევრობას უცვლელად . შემდეგ დავთვალოთ ოპერაციების რაოდენობა და დავამტკიცოთ სისწორე .

Erase (A, c )

{
თუ A ცარიელია   დააბრუნე  A;   // ანუ ცარიელი  

a = A სიმრავლის შუა ელემენტი ;

if (a = c )  { წაშალე a ელემენტი მიმდევრობიდან და დააბრუნე A ; }

if (a > c ) { A = A სიმრავლის მარცხენა ნახევარი ; დააბრუნე Erase (A,c); }

if (a < c ) { A = A სიმრავლის მარჯვენა ნახევარი ; დააბრუნე Erase (A,c); }

}

 

ოპერაციების რაოდენობა :

T(Erase(A(n),c)) = 4 + T(A(n/2),c) = . . . 4*logn + T(0) = 4*logn + 1 = O(logn)

სისწორის დამტკიცება :

თუ მიმდევრობა ცარიელია , შემოწმდება პირველი პირობა და დაბრუნდება ისევ ეს მიმდევრობა ანუ ცარიელი მიმდევრობა. ახლა დავუშვათ რომ ალგორითმი სწორად მუშაობს n -ზე ნაკლები ელემენტის შემთხვევაში . როცა შემოწმდება A მიმდევრობის სიცარიელე , ეს მცდარი იქნება და გადავა შემდეგ ბიჯზე , ანუ a -ს მიენიჭება მიმდევრობის შუა ელემენტი , თუ ეს ელემენტი არ არის წასაშლელი ელემენტის ტოლი გადავა შემდეგ ბიჯზე იმის მიხედვით მიმდევრობის შუა ელემენტი ნაკლებია თუ მეტია წასაშლელ რიცხვზე , ამის შემდეგ მოხდება მონაცემთა განახევრება და გამოიძახება ისევ Erase(A,c) ალგორითმი უფრო ნაკლები მონაცემისთვის, როლის შემთხვევაშიც დაშვებით ვიცით რომ ალგორითმი სწორად მუშაობს.

Leave a Reply / უპასუხე

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / შეცვლა )

Twitter picture

You are commenting using your Twitter account. Log Out / შეცვლა )

Facebook photo

You are commenting using your Facebook account. Log Out / შეცვლა )

Google+ photo

You are commenting using your Google+ account. Log Out / შეცვლა )

Connecting to %s