1. اگر سمپادی هستید برای دسترسی کامل به مطالب و امکانات سایت عضو شوید :
    ثبت نام عضویت

ساختار داده ها (Data Structures)

شروع موضوع توسط daneshvar.amrollahi ‏2014/12/5 در انجمن المپیاد كامپيوتر

  1. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    سلام. احساس کردم تاپیکی برای مطلب ساختار داده ها نداریم. ساختمش. چون برای برنامه نویسی تو المپیاد کامپیوتر مهمه.

    اولین سوال هم می پرسم: ساختار داده ای طراحی کنید که برای بزرگترین عدد از بین i-j تا i را با اردر 1 جواب دهد. محدوده ی عدد ها از 1 تا n هستش و n خیلی برزگ نیست. یعنی میشه حافظه ی n تا یی گرفت.
     
    • لایک لایک x 4
  2. rezaezio

    rezaezio کاربر فوق حرفه ای

    ارسال‌ها:
    1,168
    امتیازات:
    +2,039 / -78
    نام مرکز سمپاد:
    حلّیِ 2
    شهر:
    تهران
    دانشگاه:
    شریف
    رشته دانشگاه:
    نرم افزار
    پاسخ : ساختار داده ها (Data Structures)

    سوال رو دقیق‌تر بگو ! :-" j عدد ثابته الان ؟
     
  3. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : ساختار داده ها (Data Structures)

    آره j یه عدد ثابت هستش. در واقع صورت کلی تر سوال اینه: n تا عدد بهمون میدن. بعدش یه عدد تابت j ورودی میدهند. بعدش m تا سوال ازمون می پرسن که هر سوال یه عدد i بهمون ورودی میده. ما باید بزگترین عدد بین بازه ی i-j تا i رو با اردر ۱ جواب بدیم.

    میشه همچنین ساختار داده طراحی کرد؟ اگر آره بگید چحوری...
     
  4. rezaezio

    rezaezio کاربر فوق حرفه ای

    ارسال‌ها:
    1,168
    امتیازات:
    +2,039 / -78
    نام مرکز سمپاد:
    حلّیِ 2
    شهر:
    تهران
    دانشگاه:
    شریف
    رشته دانشگاه:
    نرم افزار
    پاسخ : ساختار داده ها (Data Structures)

    ببین با پیش‌پردازش (O(n و حافظه (O(n میشه واسه هر i، عدد خواسته شده رو پیدا کرد و توی یک آرایه ریخت ! حالا هر کوئری رو از (O(1 میشه جواب داد.
    راهنمایی : از داده‌ساختار deque استفاده میشه!
    سوال E. Watching Fireworks is Fun هم با استفاده از همین داده ساختار حل میشه ! ;;)
     
    • لایک لایک x 1
  5. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : ساختار داده ها (Data Structures)

    یه چیزایی به ذهنم میاد نمیدونم درسته یا نه. برای تولید اون ارایه نهایی (اسمش رو بذاریم ans) که بتونیم با اون با اردر ۱ به سوالات جواب بدیم، این رابطه بازگشتی به ذهنم میرسه:
    کد:
    ans[i] = max(ans[i-j+1],a[i])
    
    میشه دی پی اجراش کرد. اما اصلا درسته این رابطه؟ یعنی با این رابطه داریم هر سری ۱ دونه ۱ دونه میریم جلو (آغاز از خانه j+1 ام - j خانه ی اول قبلا مقدار دهی اولیه شده اند) و جواب اون سوال رو می سازیم برای همه ی i ها. بعدش آخر کار میریم راحت با اردر ۱ جواب میدیم.
     
  6. rezaezio

    rezaezio کاربر فوق حرفه ای

    ارسال‌ها:
    1,168
    امتیازات:
    +2,039 / -78
    نام مرکز سمپاد:
    حلّیِ 2
    شهر:
    تهران
    دانشگاه:
    شریف
    رشته دانشگاه:
    نرم افزار
    پاسخ : ساختار داده ها (Data Structures)

    نه خُب واضحه این غلطه ! به دو دلیل، اول این که از deque استفاده نکردی ;;) دوم اینکه هر مثالی بزنی این آرایه ای که پر میکنی اشتباهه واسش ! یعنی اصن درک نمیکنم منطق این رابطه بازگشتی رو :-"
     
  7. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : ساختار داده ها (Data Structures)

    از dequeue که معلوم بود استفاده نکردم! اما حس کردم شاید بدون اون هم بشه! منطقش هم اینطوری به ذهنم اومد: مثلا فرض کنید j = 4 هستش. ۴ تا خونه ی متوالی رو درنظر بگیرید. هر سری یدونه شیفت میدیم راست. میخوایم هر دفعه که شیفت دادیم بیایم بزرگترین توی بازه ی جدید تولید شده (شیفت داده شده) رو پیدا کنیم. دیدم که یه عنصر i امی داره اضافه میشه که ممکنه ماکسیمم باشه. پس ماکسیمم گرفتمش با بهترین حالتی که تا قبل پیدا شده بود!

    شبیه این نیست؟
     
  8. Anita H

    Anita H کاربر فوق حرفه ای

    ارسال‌ها:
    570
    امتیازات:
    +2,935 / -42
    نام مرکز سمپاد:
    حلّی ۲
    شهر:
    تهران
    سال فارغ التحصیلی:
    1396
    پاسخ : ساختار داده ها (Data Structures)

    این درسته؟
    http://paste.ubuntu.com/9428497/
    توضیح میخاد؟

    سوال قشنگیه :-"
     
    • لایک لایک x 2
  9. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : ساختار داده ها (Data Structures)

    آره یه توضیحی بده لطفا! :D
     
  10. rezaezio

    rezaezio کاربر فوق حرفه ای

    ارسال‌ها:
    1,168
    امتیازات:
    +2,039 / -78
    نام مرکز سمپاد:
    حلّیِ 2
    شهر:
    تهران
    دانشگاه:
    شریف
    رشته دانشگاه:
    نرم افزار
    پاسخ : ساختار داده ها (Data Structures)

    توضیح می‌خواد!

    اینم کد من، امیدوارم درست زده باشم. ؛؛)
    http://paste.ubuntu.com/9431468/
     
    • لایک لایک x 3
  11. Anita H

    Anita H کاربر فوق حرفه ای

    ارسال‌ها:
    570
    امتیازات:
    +2,935 / -42
    نام مرکز سمپاد:
    حلّی ۲
    شهر:
    تهران
    سال فارغ التحصیلی:
    1396
    پاسخ : ساختار داده ها (Data Structures)

    آقا من توضیح دادن بلد نیستم :-"
    اولن واضحه که خونه ی اول هر کدوم از pair های D یه عدد از آرایه A هست
    ثانین فرض میکنیم جمع خونه های دوم هر کدوم از Pair های D برابر j هست!
    وقتی فور توی مرحله ی i ام هست خونه های i – j تا i ام آرایه ی A رو در نظر بگیر؛ توی این مرحله از فور، مولفه های اول D توی همین بازه هستن، حالا مولفه های دوممون چین؟ فرض کن توی یه خونه از D عدد A[k] رو ذخیره کرده باشیم. مولفه ی دوم این pair، ماکزیمم عدد x هست به طوری که:
    کد:
    Max( a[i], a[i – 1], …, a[k], a[k - 1], ..., a[k - x] ) = a[k]		( x <= j - i + k )
    همه دستورات توی for برای آپدیت کردن این دیکیو ئه هستن!
    ans[ i] با این فرض که توی مرحله ی i ام for هستیم، برابر یکی از خونه های ابتدایی یا انتهایی(بسته به مدل پر کردنمون) D هستش

    پ.ن: یه جوری توضیح دادم علاوه بر این که هیچی نفهمید، جرئت سوال کردنم نداشته باشید :))
     
    • لایک لایک x 2