(۱۳ آذر ۱۳۸۹ ۰۸:۲۵ ب.ظ)sepid نوشته شده توسط:  سوال اول:
برای جستجوی موفق:
عنصر مورد جستجو یکی از عناصر Aتا E هست.
اگرA , B,C,D, باشه با اولین مراجعه به آدرس عنصر رو پیدا کردیم پس ۱ جستجو میخاد .
اما اگر Eباشه چون E تو خونه‌ی شوم تداخل داریم و روش حل تداخل هم کاوش خطی یعنی E الان تو خونه ۶ هست پس با شروع از ۳ تا ۶ باید ۴ تا خونه را جستجو کنه.
حالا متوسط میشه جمع تمام دفعات جستجو تقسیم به تعداد عناصر.
برای ناموفق:
عنصر مورد نظر در لیست نیست.حاصل تابع هش برای این عنصر میتونه یکی از اعداد ۰ تا ۷ باشه یعنی ۸عدد.
اگر ۰ بشه که فقط ۱ جستجو لازمه و می بینه که خونه صفر خالیه و عنصر توی لیست نیست.
اگر حاصل هش ۱ بشه‌: خونه ۱ رو میبینه پره پس طبق الگوریتم که کاوش خطیه میره سر خونه بعدی که ۲هست میبینه خالیه پس عنصر تو لیست نیست و با گشتن ۲ خونه اینو فهمید.
اگر حاصل ۳ بشه میره سر خونه ۳ میبینه پره پس خونه ۴ رو میگرده پره بعد ۵ پره بعد هم ۶که پره(E)
بعد هم ۷ که خالیه پس جستجو تموم شد و عنصر در لیست نبود پس کلا ۵ بار جستجو داشتیم.
برای بقیه نتایج تابع هش هم همینطور بررسی می کنیم.
*******************************************************************
سوال دوم:
بدترین حالت وقتی هست که حاصل تابع هش برای همه n عنصر یک عدد بشه پس همشون تو همون خونه به صورت زنجیری قرار دارن واگر دنبال اخرین عنصر تو زنجیر باشی نیاز داری همه‌ی n تا عنصر رو بگردی.
فک کنم وقتی این اتفاق می افته که تابع هش یکنواخت نباشه.
امید وارم تونسته باشم کمکتون کنم.

مرسی سپید عزیز.واقعا کمک کردی.کاملا متوجه شدم.از لطفت ممنون.میتونم بپرسم از رو چی خوندی که انقدکامل بلدی؟آیا گونه های دیگه ای هم میتونه از هش سوال مطرح بشه؟واینکه سوالای بیشترمربوط به هش رو کجامیتونم پیداکنم؟

مطمئن هستید توی تایپ خواهد و نخواهد‌، درست نوشتید .
در جواب سوال ۱ گزینه ج غلطه چراکه در اینجا اندازه زیر مسئله ما زیاده و هر گاه تعداد زیر مسائل زیاد باشه (a) یا اندازه زیر مسائل بزرگ باشه (b) از روش تقسیم وغلبه نمی توان استفاده کرد( منبع‌: کتاب مقسمی + نیپولیتان)
الگوریتم سولین هم برای درخت پوشا هست دیگه( منبع: کتاب پوران + فکر کنم هورویتز)
هافمن هم که تو هر کتابی هست

ممنون از پاسختون.سوال ۱ منظورتون گزینه ب غلطه یا ج؟اندازه زیر مسئله رو چطوری میگین بزرگه؟به خاطر n^2 ?
هافمن هم فولم ولی روش حل این سوال چطوریه؟تاحال یه همچین سوالی ندیدم!

(۱۰ آذر ۱۳۸۹ ۰۹:۳۹ ب.ظ)sal_dovomi نوشته شده توسط:  ممنون از پاسختون.سوال ۱ منظورتون گزینه ب غلطه یا ج؟اندازه زیر مسئله رو چطوری میگین بزرگه؟به خاطر n^2 ?
هافمن هم فولم ولی روش حل این سوال چطوریه؟تاحال یه همچین سوالی ندیدم!

به نظرم جفتشون و ربطی هم به c نداره که دوستمون javadjjگفتن c خیلی مهمه چون هر چی هم بزرگ باشه که به n^2 که نمیرسه. به فرمول زیر دقت کنید:

در اینجا b اندازه زیر مسئله و a تعداد زیر مسئله هست.D زمان تقسیم و C زمان ترکیب که معمولاً C ,D رو با هم بیان میکنن.

سلام دوست عزیز باید بگم که سوالات بد نیست حالا به جواب هایی که من میدم دقت کن:
در مورد سوال اول باید بگم بین دو گزینه وسط میشه شک کرد اما یادت باشه تو گزینه ۲ خوب نیست از تقسیم و غلبه استفاده بشه دلایل زیادی هست و محکم ترین دلیلش اینه که مسئله داره به زیر مسائل هم اندازه خودش تقسیم میشه اما چرا گزینه سه چون اینجا C ثابت داریم و اعداد ثابت خیلی تاثیر میزارن در تقسیم و غلبه لذا همون بهتر گزینه ۳ هستش
سوال ۲-نمیدونم چرا جواب گزینه ج هستش فرمول پویای بازگشتی این مسئله جهت ترسیم درخت این هست:
B n,k=B [n-1 ,k-1] + B [n-1,k
و فرمول محاسبه تعداد جمع‌ها این هست ترتیب n,k منهای یک C [n,k]-1=تعداد جمع ها
بایه محاسبه ساده جواب ۳۴ میشه یه بار حساب کن البته درخت رو هم رسم کنی بازم به ۳۴ تا جمع میرسی من رسم کردم
پس جواب کلید اشتباه هستش و گزینه ۲ میشه
سوال ۳- اما در مورد سوال سوم ببین این همون الگوریتم کروسکال هستش شایدم شبیه اون نمیدونم!!!!
کار این الگوریتم اینه که هر بار جنگل های مختلف بر طبق کمترین وزن درست میکنه و سپش این جنگل‌ها رو بهم اتصال میده تا درخت پوشای کمینه درست بشه که زمان مصرفیش یا همون مراحل میشه ElogE اما اینجا نمیدونم چطور جواب log n شده در صورتی که تمام الگوریتم های درخت پوشا بر مبنای تعداد یال‌ها زمانبندی میشوند

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
به این لینک یه مراجعه بکن فک کنم طراح تعداد مراحل اتصال جنگل‌ها بوده که همون log n میشه یا در صورتی که تعداد یال‌ها خیلی کم باشه
سوال چهارم:ببینید تو کد هافمن یه قانون داریم که میگه هیچ کدی پیشوند کد دیگه نمیتونه باشه اینجا داریم A:xy B=xyw
خوب A که پیشوند B شد واااااای البته میشه یه چیزایی رسم کرد اما عدم قطعیت داریم مگه نه شاید xy بره سمت راست ریشه شایدم سمت چپ پس قید حل این سوال رو به نظر من بزن البته به نظر من اگه این اشتباه نمیشد میتونست تست جالبی باشه

فک کنم طراح کلا یه کم عجله داشته
سایر دوستان جوابا رو چک کنند و نظر خودشون رو بگن

ممنون از دوستان بابت پاسخها.
در مورد سوال ۱ هنوز نظری ندارم.منتظرم شما به توافق برسین
در مورد سوال۲)
آقای javadjj گفتین که فرمول جمع‌ها C [n,k]-1=تعداد جمع ها
ولی این تعداد جملات تو روش تقسیم و حل هست که هی جملات تکراری محاسبه میشن.توی پویا از پایین شروع میکنیم و میریزیم تو آرایه تا دیگه دوباره محاسبات تکراری انجام نشه. اگه از مثلث خیام پاسکال بریم و فقط خونه هایی که برای[۷,۴] نیازه رو حساب کنیم میشه ۱۸/نمیدونم درست میگم؟
در مورد سوال ۳)
اگر sollin همون کراسکال باشه, تعداد مراحل مگه نمیشه به تعداد یالهای گراف پوشا.خوب یالهای یک گراف پوشا مگه n-1 نیست؟پس باید بشه O(n)=max
در مورد سوال ۴)
بیخیال میشیم

---

با عرض شرمندگی سوال ۱)این طوری بوده:
۱)کدام گزینه صحیح نیست؟
الف)معمولا میتوان مصرف حافظه الگوریتم های پویا را کاهش داد.
ب)اگر مسئله ای T(n)=T(n-2)+n^2 باشدٰحل این مسئله با روش تقسیم و حل امکان پذیر است.
ج)اگر در مسئله ای T(n)=T(n-3)+c حل این مسئله با روش تقسیم و حل کارایی مناسبی خواهد داشت.
د)معمولا الگوریتم های برنامه نویسی ژویا کارایی بهتری نسبت به الگوریتم های تقسیم و حل برای مسائل مشابه دارند.

فک کنم حالا دیگه جواب بشه گزینه ج.
ببخشید

(۱۱ آذر ۱۳۸۹ ۱۲:۲۷ ق.ظ)sal_dovomi نوشته شده توسط:  در مورد سوال۲)
آقای javadjj گفتین که فرمول جمع‌ها C [n,k]-1=تعداد جمع ها
ولی این تعداد جملات تو روش تقسیم و حل هست که هی جملات تکراری محاسبه میشن.توی پویا از پایین شروع میکنیم و میریزیم تو آرایه تا دیگه دوباره محاسبات تکراری انجام نشه. اگه از مثلث خیام پاسکال بریم و فقط خونه هایی که برای[۷,۴] نیازه رو حساب کنیم میشه ۱۸/نمیدونم درست میگم؟
در مورد سوال ۳)
اگر sollin همون کراسکال باشه, تعداد مراحل مگه نمیشه به تعداد یالهای گراف پوشا.خوب یالهای یک گراف پوشا مگه n-1 نیست؟پس باید بشه O(n)=max

در مورد سوال ۲ باید بگم شرمنده حواسم رو جمع نکردم و همین میتونه یه اشتباه باشه سر جلسه کنکور که سریع به جواب اشتباه برسی اما به دقت بررسی کن نتیجه میگری حتما اگه هم دیدی نشد بعید نیست جواب تو گزینه‌ها نباشه
اما الگوریتم کروسکال همون ElogE میشه شک نکن.

N بار سوال ۱ رو حل کردم به همون جواب اول ۱۲ رسیدم.
یک سوال دیگه:
مرتبه زمانی میخاد: T[n]=T[n/4]+T[3n/4] if n>1
جواب رو دارم.فقط نمیفهمم اینجا که میگه برای محاسبه ارتفاع درخت باید شاخه ای رو در نظر بگیریم که ارتفاع بیشتری دارد.چه جوری می سنجه و ارتفاع بیشتر رو به دست میاره؟

وقتی میگه n/4 یعنی n داره به ۴ تقسیم میشه تا به ۱ برسه.
وقتی میگه ۳n/4 یعنی n داره تقسیم بر ۳/۴ میشه یعنی اینکه خیلی نسبت به قبلی دیرتر به ۱ میرسه.
چون هر چی عددی که n بر اون تقسیم میشه بزرگتر باشه n سریعتر به ۱ میرسه.

ما باید ارتفاع درخت رو حساب کنیم پس باید هر دو شاخه به ۱ (شرط توقف بازگشت)برسه پس درخت رو تا زمانی ادامه میدیم که شاخه دوم هم که دیرتر به یک میرسه به یک برسه. که خودش نوشته log در پایه ۳/۴( چون اگه بر ۲ تقسیم میشد میگذاشتیم در پایه ۲ حالا که بر ۳/۴ تقسیم شده میگذاریم ۳/۴)

(۱۱ آذر ۱۳۸۹ ۱۱:۳۰ ق.ظ)afagh1389 نوشته شده توسط:  وقتی میگه n/4 یعنی n داره به ۴ تقسیم میشه تا به ۱ برسه.
وقتی میگه ۳n/4 یعنی n داره تقسیم بر ۳/۴ میشه یعنی اینکه خیلی نسبت به قبلی دیرتر به ۱ میرسه.
چون هر چی عددی که n بر اون تقسیم میشه بزرگتر باشه n سریعتر به ۱ میرسه.

ما باید ارتفاع درخت رو حساب کنیم پس باید هر دو شاخه به ۱ (شرط توقف بازگشت)برسه پس درخت رو تا زمانی ادامه میدیم که شاخه دوم هم که دیرتر به یک میرسه به یک برسه. که خودش نوشته log در پایه ۳/۴( چون اگه بر ۲ تقسیم میشد میگذاشتیم در پایه ۲ حالا که بر ۳/۴ تقسیم شده میگذاریم ۳/۴)

اگر T (n)= T(n/2)+T(n/4)+T(n/8) بود
در اینصورت شاخه n/2 دیرتر به (T(1 میرسه؟
من برای اینو حساب کردم شد O(8n

دوستان با عرض پوزش یک سوال دیگه رو مطرح میکنم. عاجزانه درخواست کمک دارم.
تو این سوال ترتیب ورود به پشته و خروج از پشته چگونه هست؟ترجیحا با شکل توضیح بدین.ممنون

سلام.
ببین اگه دستور write بالای فراخوانی بود جواب بصورت زیر میبود:
۳۲->16->8->4->2->1
(اولین خروجی ۳۲ و آخرین خروجی ۱)
اما حالا که دستور write بعد از فراخوانی داریم همین ترتیب درون پشته میره (در حالت قبل خروجی به صفحه نمایش میرفت) و بعد بصورت عکس بیرون میاد یعنی روند محاسبه مثل بالا هست اما روند چاپ برعکسه چون از تو پشته در میاد
۱->2->4->8->16->32

با تشکر از آقای مسعود.فهمیدم.
و با شرمندگی ۲تا سوال دیگه:
سوال اول:

لطفا توضیح بدین چرا اینطوری شده؟
سوال دوم:

تو سوال ۲ فقط نمیفهمم چرا بدترین حالت شده O(n) مگه تو هر لیست N/m عضو نیست؟ ژس چه جوری در بدترین حالت n عنصر رو برری میکنه؟
لطفا یه منبع خوب واسه یادگیری کامل hash table معرفی کنین.

خواهش میکنم.
خوشحالم که تونستم کمک کنم.
من از روی ساختمان پارسه و مقسمی خوندم این بخشو.
اسلایدهای clrsکه تو بسته مانشت بود هم به نظرم خوبه.
من فقط سوالای کنکور سالای پیش رو خوندم.

درمورد سوال ۴
کد هافمن کدیه که هیچ دو کدی پیشوند هم نیستند پس E و A نمی تونن یکسان باشن
اگه E= 01 پس A باید ۱۰ باشه
من فقط می تونم بگم جواب یا الف یا ب

(۱۹ آذر ۱۳۸۹ ۱۰:۵۹ ب.ظ)sarah نوشته شده توسط:  درمورد سوال ۴
کد هافمن کدیه که هیچ دو کدی پیشوند هم نیستند پس E و A نمی تونن یکسان باشن
اگه E= 01 پس A باید ۱۰ باشه
من فقط می تونم بگم جواب یا الف یا ب

منم میدونم که الف نیست چون اگه x=y=1 باشه A=11 میشه اونوقت AA با D اشتباه میشه.
ب هم نیست چون اونوقت c=1001 و A=10 و E=01 بود پس AE=C

ح و د هم نیست !!!!!

---

در مورد توضیح پشته فرض کنید شما یه جعبه برداشتین توش کاغذهای شماره دار گذاشتین اول مثلا شماره ۱ بعد ۲ بعد ۳ کاغذی که اول از همه گذاشتی(شماره ۱) رفته ته جعبه و اگه بخوای درش بیاری باید یکی یکی کاغذهای قبلی رو در بیارین (فرض کنید نمیشه همه رو با هم برداشت) تا به کاغذ شماره ۱ برسین.
در ضمن آخرین کاغذی رو که گذاشتین به راحتی میتونید از روی کاغذهای دیگه بردارید.

پشته یه اشاره گر داره که به بالای پشته اشاره میکنه.که یا به اولین خانه خالی اشاره میکنه یا به آخرین خانه پر.