تمرين طراحي الگوريتم

---

شرح پروژه

1- آرايه A که عناصر آن به ترتيب از چپ به راست برابر است. a. آرايه فوق پس از ساختن buildheap_Max به چه صورت است؟ b. آرايه فوق پس از فراخوانيpartition(A,1,9)به چه صورت است؟(اولين عنصر محور است. c. با داشتن آرايه به صورت maxheap تابع heapsort را به صورت بازگشتي بنويسيد. Recursive_heapsort(A[],n) {A is maxheap, n is size heap){ { 2- برنامه زير را درنظر بگيريد a. عملکرد تابع فوق را توضيح دهيد. b. زمان اجراي آن را در بدترين حالت تحليل کنيد. (تابع آن را بنويسيد و آن را حل کنيد.) 3- فردي براي مرتب¬سازي يک آرايه الگوريتم زير را ارائه داده است a. آيا الگوريتم فوق درست کار مي¬کند با ذکر دليل. b. اگر در خط 6 به جاي سقف از علامت کف استفاده شود درست کار مي¬کند. c. رابطه بازگشتي مربوط به تعداد مقايسه عناصر (تعداد اجراي خط2) را بنويسيد و رابطه مورد نظر را حل کنيد. 4- آرايه¬اي از n بردار موجود است که هر بردار شامل 3 مولفه است. هر يک ار مولفه¬ها يک عدد صحيح بين 1 تا 20 است. a. دو بردار با هم مساوي هستند اگر همه مولفه¬هاي آن با هم مساوي باشند. بنابراين بردار (4.12.3) با بردار (4،12،3) مساوي است و با بردار (12،4،3) مساوي نيست. الگوريتمي با O(n) ارائه دهيد که يک آرايه با n بردار را به عنوان ورودي بگيرد و در آن دو بردار مساوي را جستجو کند. يا اينکه پيغام بدهد که دو بردار مساوي وجود ندارد. b. دو بردار را به هم نزديک گوييم اگر در دو مولفه مساوي باشند و در مولفه ديگر حداکثر يکي اختلاف وجود داشته باشد. به عنوان مثال (3،12،4) به (3،13،4) نزديک است ولي به (4،12،3) نزديک نيست. الگوريتمي با زمان O(n) بنويسيد که دو بردار نزديک به هم را پيدا کند. 5- الگوريتمي در زمان O(n) ارائه دهيد که n عدد در رنج 1 تا n2-1 را مرتب کنيد.

این پروژه شامل 2 فایل مهم است، لطفا قبل از ارسال پیشنهاد حتما نسبت به بررسی این فایل اقدام فرمایید.

مهارت ها و تخصص های مورد نیاز

---

---