المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۱:برنامه نویسی:سوال ۸

سوال ۸

علی یک struct سنگین به نام heavy تعریف کرده که در آن یک متغیر long long و ۳ متغیر double * و ۶ متغیر int و ۳ متغیر char و ۱۱ متغیر char * موجود است.

  1. فرض کنید h یک متغیر از نوع این struct است. چگونه می‌توانیم حجم اشغال شده توسط h را (به بایت) پیدا کنیم؟ این مقدار چند است؟
  2. می‌دانیم vector همیشه یک حافظه‌ی داخلی پویا دارد که تعداد عناصر رزرو شده‌ی آن توانی از ۲ است. این اندازه با تابع داخلی capacity() (نظیر cout « v.capacity() « endl;) قابل مشاهده است. می‌دانیم در صورتی که v.size() برابر با v.capacity() باشد و عنصر جدیدی را بخواهیم push_back کنیم، ابتدا یک آرایه‌ی پویای جدید به‌اندازه‌ی دو براب ر آرایه‌ی داخلی کنونی، درخواست (new) می‌شود. سپس عناصر موجود در آرایه‌ی قبلی به نیمه‌ی اوّل این آرایه نقل‌مکان می‌کنند.
  3. اگر با شروع از یک vector<heavy> خالی، ما ۲۰۰ شیء از ساختار heavy را دانه دانه در vectorمان، push_back کنیم، تعداد متوسط نقل‌مکان‌های هر عنصر vector چندتا است؟
  4. اکنون فرض کنید می‌خواهیم عناصر این vector را بر حسب مقدارِ تنها متغیرِ long long موجود در هر کدام از عناصر، به‌صورت نزولی، مرتب کنیم. روش انجام این کار با استفاده‌ی الزامی از تابع sort را به همراه کدهای مربوطه بنویسید.
  5. می‌دانیم تابع sort در هنگام مرتب‌سازی، بارها عناصر را بین اندیس‌های مختلف vector دوبه‌دو جابه‌جا (swap) می‌کند. این کار با توجه به حجم نسبتاً بالای هر عنصر از این struct، زمان‌بر است. با این وصف، چگونه می‌توان سرعت انجام این عمل مرتب‌سازی را بهبود ببخشیم؟ (بهینه‌سازی‌های بدیهی که ممکن‌ست کامپایلر برای اُپتیمایز کردن انجام دهد، مدّ نظر نیستند.)

ابزار صفحه