• اگر سمپادی هستی همین الان عضو شو :
    ثبت نام عضویت

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

  • شروع کننده موضوع
  • #1

daneshvar.amrollahi

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

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

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : ساختار داده ها (Data Structures)

سوال رو دقیق‌تر بگو ! :-" j عدد ثابته الان ؟
 
  • شروع کننده موضوع
  • #3

daneshvar.amrollahi

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

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

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

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : ساختار داده ها (Data Structures)

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

daneshvar.amrollahi

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

به نقل از Damon :
ببین با پیش‌پردازش (O(n و حافظه (O(n میشه واسه هر i، عدد خواسته شده رو پیدا کرد و توی یک آرایه ریخت ! حالا هر کوئری رو از (O(1 میشه جواب داد.
راهنمایی : از داده‌ساختار deque استفاده میشه!
سوال E. Watching Fireworks is Fun هم با استفاده از همین داده ساختار حل میشه ! ;;)
یه چیزایی به ذهنم میاد نمیدونم درسته یا نه. برای تولید اون ارایه نهایی (اسمش رو بذاریم ans) که بتونیم با اون با اردر ۱ به سوالات جواب بدیم، این رابطه بازگشتی به ذهنم میرسه:
کد:
ans[i] = max(ans[i-j+1],a[i])

میشه دی پی اجراش کرد. اما اصلا درسته این رابطه؟ یعنی با این رابطه داریم هر سری ۱ دونه ۱ دونه میریم جلو (آغاز از خانه j+1 ام - j خانه ی اول قبلا مقدار دهی اولیه شده اند) و جواب اون سوال رو می سازیم برای همه ی i ها. بعدش آخر کار میریم راحت با اردر ۱ جواب میدیم.
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : ساختار داده ها (Data Structures)

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

daneshvar.amrollahi

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

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

شبیه این نیست؟
 

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : ساختار داده ها (Data Structures)

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

سوال قشنگیه :-"
 
  • شروع کننده موضوع
  • #9

daneshvar.amrollahi

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

به نقل از amoo§majid :
این درسته؟
http://paste.ubuntu.com/9428497/
توضیح میخاد؟

سوال قشنگیه :-"
آره یه توضیحی بده لطفا! :D
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : ساختار داده ها (Data Structures)

به نقل از amoo§majid :
این درسته؟
http://paste.ubuntu.com/9428497/
توضیح میخاد؟

سوال قشنگیه :-"
توضیح می‌خواد!

اینم کد من، امیدوارم درست زده باشم. ؛؛)
http://paste.ubuntu.com/9431468/
 

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
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 هستش

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