(۱۰ اسفند ۱۳۹۰ ۱۰:۲۲ ب.ظ)Masoud05 نوشته شده توسط:(10 اسفند ۱۳۹۰ ۰۹:۴۳ ب.ظ)aliebtehaj نوشته شده توسط: بابا بخدا منم می دونم دور منفی رو تشخیص می ده خیلی خوبم می دونم اون سوال سال ۸۴ ۲۰۰۰ بار خوندم ولی صورت سوال گفته فاصله هر راس از خودش صفره این معنیش این نیست که هزینه طوقه صفره بلکه یعنی تمام دور هامون صفره در غیر این صورت سوال غلط بیان شده. و گرنه این سوال ابتدایی بود من ترم ۵ هم یاد داشتم تمام این فرمول های clrs و پوران و اینا رو خوندم خوب می دونم ولی صحبت من یه چیزه دیگه است.
خب ، نمیدونم ، اما چرا باید دورها صفر باشه ؟!!! بنظرم اشکال کار تو همینه . در کل من فقط در حد ارسال بالا بلد بودم . باید سایر دوستان نظر بدن .
باور کنید من هم گزینه ۱ و می زدم به خاطر اینکه اینقدر به فرضش توجه کردم باید اینجوری ضایع بشم برا همینم میگم امسال سوالای تخصصی ها (مخصوصاً هوش) رو نباید زیاد بهش توجه می کردی و یه رو خونی می کردی و بعد تستشو می زدی . ولی باور کنید اگه طراح سوالم بیاد کلاشو قاضی کنه می فهمه که حق با ماست.چون وقتی میگه فاصله هر راس از خودش همواره صفره یعنی تمام مسیر هایی که از راس به خودش حالا شامل طوقه یا تمام دورهای دیگه میشه صفره که در این صورت اصلاً دور منفی نداریم که بخواد تشخیص بده وکلاً سوال غلط بود و گزینه ها هم همه غلط بود فقط گزینه ۴ یک کم با جواب مطابقت داشت خوب دورها هم می تونه صفر باشه یعنی مثلاً از راس ۲ به خودش شامل یال های ۲ و -۱ و -۱ باشه که میشه صفر یعنی تمام راس هامون همین ویژگی رو دارند. اگه اینطوری نیست چه دلیلی داره اصلاً فرضو اینجوری بیان کنه یا اصلاً چه دلیلی داره فرضو بیان کنه چون تو تمام کتابا اینطوری گفتند اگر i=j در اینصورت wij=0 برا تمام الگوریتم های زوج راس همین بوده ولی نگفته که فاصله هر راس تا خودش صفره. بازم ممنون از این که وقت گذاشتین من دلایلم رو برا سنجش نوشتم حالا اگه وجدان داشته باشند که .....
درسته ، فرضیات صورت سئوال اصلا خوب بیان نشده بود.یا حداقل گزینه های درستی انتخاب نکرده بودند
کرمن گفته به دو طریق میشه دور منفی را تشخیص دهیم ۱-اگر عناصر قطر اصلی یکیشون منفی بشه که با فرض سوال این اتفاق اصلا اتفاق نمیفته ۲-دوباره الگوریتم را اجرا کنیم اگر مقادیر ماتریس d کمتر شدند دور منفی داریم در مورد روش دوم هم با یک مثال که پیوست کردم این اتفاق نمیفته چون هر چقدر اجرا کنیم ماتریس d مقادیرش ثابته
(۱۰ اسفند ۱۳۹۰ ۱۰:۴۵ ب.ظ)aliebtehaj نوشته شده توسط: باور کنید من هم گزینه ۱ و می زدم به خاطر اینکه اینقدر به فرضش توجه کردم باید اینجوری ضایع بشم برا همینم میگم امسال سوالای تخصصی ها (مخصوصاً هوش) رو نباید زیاد بهش توجه می کردی و یه رو خونی می کردی و بعد تستشو می زدی . ولی باور کنید اگه طراح سوالم بیاد کلاشو قاضی کنه می فهمه که حق با ماست.چون وقتی میگه فاصله هر راس از خودش همواره صفره یعنی تمام مسیر هایی که از راس به خودش حالا شامل طوقه یا تمام دورهای دیگه میشه صفره که در این صورت اصلاً دور منفی نداریم که بخواد تشخیص بده وکلاً سوال غلط بود و گزینه ها هم همه غلط بود فقط گزینه ۴ یک کم با جواب مطابقت داشت خوب دورها هم می تونه صفر باشه یعنی مثلاً از راس ۲ به خودش شامل یال های ۲ و -۱ و -۱ باشه که میشه صفر یعنی تمام راس هامون همین ویژگی رو دارند. اگه اینطوری نیست چه دلیلی داره اصلاً فرضو اینجوری بیان کنه یا اصلاً چه دلیلی داره فرضو بیان کنه چون تو تمام کتابا اینطوری گفتند اگر i=j در اینصورت wij=0 برا تمام الگوریتم های زوج راس همین بوده ولی نگفته که فاصله هر راس تا خودش صفره. بازم ممنون از این که وقت گذاشتین من دلایلم رو برا سنجش نوشتم حالا اگه وجدان داشته باشند که .....
من فکر میکنم این جمله فقط یک توضیح اضافه ست مثل توضیحات قبل که فلوید رو تشریح کرده و منظورش همین جمله ایه که خودتون نوشتین "اگر i=j در اینصورت wij=0 " و احتمالا منظور از لفظ "همواره" تاکید بر اینه که در هر مرحله قطر ماتریس همون عدد صفره و تغییر نمیکنه! (توضیح واضحات برای انحراف ذهن دانشجو
) البته منم رو این سوال شک داشتم چون باور نمیکردم انقد ساده باشه و دنبال نکته انحرافیش میگشتم
سوالای ۱۱۰ و ۱۱۳ رو کسی میتونه توضیح بده؟
(۱۴ اسفند ۱۳۹۰ ۰۶:۲۴ ب.ظ)abcd1234 نوشته شده توسط: سوالای ۱۱۰ و ۱۱۳ رو کسی میتونه توضیح بده؟
سوال ۱۱۰
سوال راحتی بود که، چون توی گزینه ها [logn-1] و [logn+1] و از این چیزا نداشت و کافی بود ببینی از چه مرتبه ایه
هر بار مساله رو نصف میکنه و بدون هزینه ترکیب میکنه (T(n)=2*T(n/2
توی این جور مسائل درنظر بگیرید اگه اندازه آرایه دو برابر بشه، هزینه ۱ مقایسه بیشتر میشه و این خاصیت شگفت انگیز لگاریتمه
______________________
سوال ۱۱۳
سوال قشنگیه، از نظر ذهنی میتونستید تشخیص بدید همون خاصیت لگاریتم صادقه؛ و با یک مقایسه نصف آرایه حذف میشه
اما توضیح دقیق تر یک الگوریتم پیشنهادی:
می دونیم: برای پیدا کردن کوچکترین عنصر در یک آرایه حلقوی مرتب، باید جایی که آرایه ناگهان خیلی بزرگ میشه رو پیدا کنیم
مثال صورت سوال: [۵۰,۴۰,۳۰,۲۰,۱۰,۸۰,۷۰,۶۰]
عنصر اول رو تو متغیر a میریزیم (این کار هزینه نداره)
عنصر وسط رو چک میکنیم؛ اینجا ۲۰
آرایه از ۵۰ به ۲۰ رسیده و جهش ناگهانی رو نداشته پس حالا نصف اول آرایه رو کنار میذاریم
دقت داشته باشید بعد از این بزرگ شدن ناگهانی، بزرگترین عضو آرایه هست و تمام عناصر بعد از اون جهش هم از همه ی عناصر قبل از جهش بزرگترند، پس اگه اون جهش قبل از عنصر وسط بود، حالا این عنصر وسط بزرگ تر از عنصر اول بود
به محض این که متوجه شدید با هزینه ۱ میشه نصف آرایه رو حذف کرد بزنید logn
ممنون ازتوضیحاتتون.
سوال ۱۱۰ رو موافقم ولی چرا در نهایت n-1 میشه؟ مگه با این توضیحات lgn نیست؟
اما در مورد سوال ۱۱۳ هنوز نمیتونم قبول کنم. آخه lgn وقتیه که آرایه مرتب باشه، فکر نمیکنم به این راحتی نصف آرایه قابل حذف باشه... مثلا آرایه رو اینطوری در نظر بگیرین : ۸۰-۷۰-۶۰-۵۰-۴۰-۳۰-۲۰-۱۰-۹۰ چطوری با مقایسه ۹۰ و ۴۰ میشه نصف آرایه رو حذف کرد؟
(۱۹ اسفند ۱۳۹۰ ۰۶:۴۱ ب.ظ)abcd1234 نوشته شده توسط: ممنون ازتوضیحاتتون.خواهش میکنم؛ امیدوارم توضیحاتم مفید باشه؛ البته اگه مثل سوال ۱۱۰ غلط نباشه!
سوال ۱۱۰ رو موافقم ولی چرا در نهایت n-1 میشه؟ مگه با این توضیحات lgn نیست؟
اما در مورد سوال ۱۱۳ هنوز نمیتونم قبول کنم. آخه lgn وقتیه که آرایه مرتب باشه، فکر نمیکنم به این راحتی نصف آرایه قابل حذف باشه... مثلا آرایه رو اینطوری در نظر بگیرین : ۸۰-۷۰-۶۰-۵۰-۴۰-۳۰-۲۰-۱۰-۹۰ چطوری با مقایسه ۹۰ و ۴۰ میشه نصف آرایه رو حذف کرد؟
____________
سوال ۱۱۰ رو من کلا اشتباه گرفتم
T(n)=2T(n/2)+1 ==> O(n
من سر جلسه هم اشتباهی گزینه ۴ رو زدم
اما این که چرا n-1 نه n
۱) جواب رابطه بازگشتی T(n)=2T(n/2)+1 با شرط T(2)=1 هست n-1
۲) با مثال برای آرایه ۴ عنصری: [a b c d] میشه ۳ رو بدست آورد
[a b] <>[c d]
[a]<>[b]
[c]<>[d]
______________
سوال ۱۱۳
آرایه ای که مثال زدم نزولی بود
آرایه ای که شما مثال زدید صعودی مرتب هست و ما دنبال جایی هستیم که کوچک شدن ناگهانی وجود دارد
a=90
۴۰ کوچکتر از a درنتیجه از کوچک شدن ناگهانی گذشته ایم و نیمه دوم رو کنار میذاریم
۲۰ کوچکتر از a در نتیجه از کوچک شدن ناگهانی گذشته ایم ...
دقت کن همه ی اعداد قبل از "کوچک شدن ناگهانی"، بزرگترند از همه ی اعداد بعد از "کوچک شدن ناگهانی" و این دلیل درست کار کردن الگوریتم توی همه ی مثال هاست
نظرت چیه؟
برای سوال سوال ۱۱۰ با یه مثال میشه به جواب n-1 رسید .موفق به ارسال تصویر مثال براتون نشدم( برای ارسال فایل ۱۱کیلو بایتیم به مانشت با پیام حجیم بودن فایل مواجه شدم نمی دونم مشکل از کجاست)
برای سوال ۱۱۳ راه حل من اینه که تو لیست دنبال کوچکترین یا بزرگترین عنصر بگردیم که زمان هر دوشون یکیه و logn شماره خونه عنصر iام =(i+اینکدکس کوچکترین عنصر) که زمان پیدا کردنش = ۱
زمان کل عملیات = logn+1 ===logn
(۲۰ اسفند ۱۳۹۰ ۰۲:۰۱ ب.ظ)abcd1234 نوشته شده توسط: هرچند هنوز کاملا نتونستم قبول کنم! ولی سعی میکنم بفهممبرای ۱۱۰ اگر درخت بکشید مشکل حله
بازهم تشکر
سوال ۱۱۰ رو متوجه شدم، مشکلم سوال ۱۱۳ ست. با نظر anyone هم موافق نیستم آخه وقتی شماره خونه عنصر iام رو بدونیم که دیگه نمیشه جستجو!
فرض کنید دنبال سومین کوچکترین عضو می گردیم
در حالت عادی در لیست مرتب :وقتی عنصر اول(کوچکترین عنصر) تو خونه اول باشه پس سومین کوچکترین عنصر هم تو خونه سومه
اما در این حالت (صف حلقوی) نمی دونیم عنصر اول در کجا قرار داره پس باید مکان این عنصر رو پیدا کنیم(با هزینه logn)
با پیدا کردن مکان این عنصر حالا نسبت به محل این عنصر می تونیم محل عضو i ام رو تشخیص بدیم یعنی شماره عنصری که می خوایم رو با محل این عنصر (کوچکترین عنصر)جمع کنیم البته چون صف حلقوی هست باید عدد حاصل بر اندازه کل صف تقسیم بشه.
هزینه جستجو بر هزینه سایر عملیات غالبه پس هزینه کل= logn