۰
subtitle
ارسال: #۱
  
سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی
سلام دوستان. امیدوارم در این روز ها که خیلی به امتحان نزدیک شدیم شاد و سلامت باشید.
در ادامه سوالی را قرار دادم که پاسخ آن مرا راضی نمی کند.
اولا صورت سوال گفته فرض کنید n عنصر در جدول وجود دارد ولی در حل فرض کرده n خانه خالی داریم.
دوما هزینه سرشکن را حساب نکرده است بلکه هزینه کل را حساب کرده است (باید نتیجه را بر n تقسیم کند).
به نظر من پاسخ این سوال گزینه ۱ است.
در صورت امکان بفرمایید راه حل آن به چه صورت است.
مطالب زیر را تنها من باب مزاح عرض می کنم :
در کنکور ۹۰ نیز طراح، سوالی شبیه این مطرح کرده بود و آن قدر در صورت سوال فرو رفت که سوال را نادرست مطرح کرد و آن سوال حذف شد. گویا همان طراح دو سال بعد متوجه اشتباه خود شد و آن سوال را کمی پیچیده تر مجددا مطرح نموده و خیلی دوست دارم بدانم که آیا این بار هم برای خود پشت پا انداخته و سکندری خورده است یا اینکه من موضوعی را به یاد نمی آورم.
در ادامه سوالی را قرار دادم که پاسخ آن مرا راضی نمی کند.
اولا صورت سوال گفته فرض کنید n عنصر در جدول وجود دارد ولی در حل فرض کرده n خانه خالی داریم.
دوما هزینه سرشکن را حساب نکرده است بلکه هزینه کل را حساب کرده است (باید نتیجه را بر n تقسیم کند).
به نظر من پاسخ این سوال گزینه ۱ است.
در صورت امکان بفرمایید راه حل آن به چه صورت است.
مطالب زیر را تنها من باب مزاح عرض می کنم :
در کنکور ۹۰ نیز طراح، سوالی شبیه این مطرح کرده بود و آن قدر در صورت سوال فرو رفت که سوال را نادرست مطرح کرد و آن سوال حذف شد. گویا همان طراح دو سال بعد متوجه اشتباه خود شد و آن سوال را کمی پیچیده تر مجددا مطرح نموده و خیلی دوست دارم بدانم که آیا این بار هم برای خود پشت پا انداخته و سکندری خورده است یا اینکه من موضوعی را به یاد نمی آورم.
۵
ارسال: #۲
  
RE: سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی
سلام
این ج که واستون می نویسم ج دکتر یوسفی هست در باب این سوال که سر کلاس برای ما حل کردن!اول تعریف هزینه سرشکنی یعنی:
n عمل را در بدترین حالت بگیر سپس میانگینشان را بگیر!
بدترین حالت وقتی است که ۳/۴ جدول پر باشد در این صورت با اولین عمل درج جدولی به طول ۲ برابر ایجاد می شود و با مرتبه تتا n عناصر جدول قبلی به جدول جدید کپی می شوند.حال اگر یک عمل حذف انجام دهیم ۳/۸ جدول پر است :
۳/۴ m=
۳/۸(۲ m)
که دوباره مجبوریم جدولی به اندازه نصف ایجاد و دوباره عمل کپی را انجام دهیم.(تتا n)
پس همون تتا n ج درست است!
یعنی میانگین n عمل در بدترین حالت که بدترین حالتم این زمان اتفاق می افتد.
موفق باشید....
این ج که واستون می نویسم ج دکتر یوسفی هست در باب این سوال که سر کلاس برای ما حل کردن!اول تعریف هزینه سرشکنی یعنی:
n عمل را در بدترین حالت بگیر سپس میانگینشان را بگیر!
بدترین حالت وقتی است که ۳/۴ جدول پر باشد در این صورت با اولین عمل درج جدولی به طول ۲ برابر ایجاد می شود و با مرتبه تتا n عناصر جدول قبلی به جدول جدید کپی می شوند.حال اگر یک عمل حذف انجام دهیم ۳/۸ جدول پر است :
۳/۴ m=
۳/۸(۲ m)
که دوباره مجبوریم جدولی به اندازه نصف ایجاد و دوباره عمل کپی را انجام دهیم.(تتا n)
پس همون تتا n ج درست است!
یعنی میانگین n عمل در بدترین حالت که بدترین حالتم این زمان اتفاق می افتد.
موفق باشید....
ارسال: #۳
  
RE: سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی
سپاس فراوان از شما دوست عزیز با توضیحات شما موضوع را کاملا متوجه شدم.
ارسال: #۴
  
RE: سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی
(۱۵ بهمن ۱۳۹۲ ۱۲:۴۲ ب.ظ)mahsalove نوشته شده توسط: سلام
این ج که واستون می نویسم ج دکتر یوسفی هست در باب این سوال که سر کلاس برای ما حل کردن!اول تعریف هزینه سرشکنی یعنی:
n عمل را در بدترین حالت بگیر سپس میانگینشان را بگیر!
بدترین حالت وقتی است که ۳/۴ جدول پر باشد در این صورت با اولین عمل درج جدولی به طول ۲ برابر ایجاد می شود و با مرتبه تتا n عناصر جدول قبلی به جدول جدید کپی می شوند.حال اگر یک عمل حذف انجام دهیم ۳/۸ جدول پر است :
۳/۴ m=
۳/۸(۲ m)
که دوباره مجبوریم جدولی به اندازه نصف ایجاد و دوباره عمل کپی را انجام دهیم.(تتا n)
پس همون تتا n ج درست است!
یعنی میانگین n عمل در بدترین حالت که بدترین حالتم این زمان اتفاق می افتد.
موفق باشید....
سلام
ممنونم از جوابتون ولی من متوجه نشدم، اونچه که دیدم این بود که شما فقط دوتا عمل رو انجام دادید نه n عمل! یه دونه درج که وقتی جدول به مرز رسیده که باعث میشه ما گسترش بدیم جدولو و دیگری یه دونه حذف مانند بالا در شرایط مرزی؟ ولی چیزی از n-1 عمل باقی مونده نگفتید و میانگین نگرفتید! البته شاید من متوجه نشدم.
۳
ارسال: #۵
  
RE: سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی
ببینید تا اونجایی که من یادمه دکتر یوسفی گفتن اگر بدترین حالت این موقعه اتفاق بیفته پس به صورت مکرر با هر حذف و درج این روند داره ادامه پیدا می کنه چون طبق تعریف سرشکن شده ما برای n عمل در بدترین حالت در نظر گرفتیم پس با هر حذف و درجی این تتا n داره برای هر عمل اتفاق می افته پس برای n عمل هر کدوم جداگانه n پس میشه n^2/n=n
که دیگه طبق تعریف سرشکن شده یعنی میانگین n عمل در بدترین حالت ج همین میشه!
موفق باشید....
که دیگه طبق تعریف سرشکن شده یعنی میانگین n عمل در بدترین حالت ج همین میشه!
موفق باشید....
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close