سلام
قصدم از این سوال حل این دوتا مثال نیست ، و فقط میخوام یه موضوعی را بفهمم
تو این سوال خرس ما گفته از مرتبه n روز زنده می مونه
![[تصویر: Exam12.JPG]](https://dl.dropboxusercontent.com/u/100069389/Images/Manesht/Sakhteman/Exam12.JPG)
حالا ما میدیم n=4 که میشه ۷ روز واسه زنده موندن خرس . و به نظر میاد بشه nlogn
حالا ما اگه n=8 بدیم تعداد روز زنده موندن خرس میشه ۱۵ روز و اینجا دیگه nlogn نمیشه
و حالا یه مدل بدتر
اینجا جواب میشه nlogn
ولی وقتی عدد گذاری میکنیم واضحه که بیشتر از nlogn میشه .
مثلا به ازای n=2 حدود ۲۱ مرتبه اجرا میشه
و برای n=8 حدود ۶۰ مرتبه اجرا میشه که با nlogn اختلاف زیادی داره
![[تصویر: Exam12_1.JPG]](https://dl.dropboxusercontent.com/u/100069389/Images/Manesht/Sakhteman/Exam12_1.JPG)
توی مثالهای قبلی به ازای nهای بزرگ مقداری که بدست میاد با مرتبه ای که در نظر میگیریم تناسب برقرار میشه ولی تو این جور مسائل به ازای nهای کوچک ممکنه جواب غلط را بدست بیاریم
اما سوال: آیا اینگونه سوالات تیپ خاصی دارند که معلوم باشه نباید با جایگذاری حل کرد ؟
چون اغلب مسائلی که راه حل برای حل کردنش نداریم و یا سخته سعی میکنیم از جایگذاری استفاده کنیم ، ولی ممکنه این جایگذاری به قیمت یک تست اشتباه تموم بشه
(۲۲ بهمن ۱۳۹۲ ۱۲:۱۳ ق.ظ)masoud67 نوشته شده توسط: سلام
قصدم از این سوال حل این دوتا مثال نیست ، و فقط میخوام یه موضوعی را بفهمم
تو این سوال خرس ما گفته از مرتبه n روز زنده می مونه
حالا ما میدیم n=4 که میشه ۷ روز واسه زنده موندن خرس . و به نظر میاد بشه nlogn
حالا ما اگه n=8 بدیم تعداد روز زنده موندن خرس میشه ۱۵ روز و اینجا دیگه nlogn نمیشه
و حالا یه مدل بدتر
اینجا جواب میشه nlogn
ولی وقتی عدد گذاری میکنیم واضحه که بیشتر از nlogn میشه .
مثلا به ازای n=2 حدود ۲۱ مرتبه اجرا میشه
و برای n=8 حدود ۶۰ مرتبه اجرا میشه که با nlogn اختلاف زیادی داره
توی مثالهای قبلی به ازای nهای بزرگ مقداری که بدست میاد با مرتبه ای که در نظر میگیریم تناسب برقرار میشه ولی تو این جور مسائل به ازای nهای کوچک ممکنه جواب غلط را بدست بیاریم
اما سوال: آیا اینگونه سوالات تیپ خاصی دارند که معلوم باشه نباید با جایگذاری حل کرد ؟
چون اغلب مسائلی که راه حل برای حل کردنش نداریم و یا سخته سعی میکنیم از جایگذاری استفاده کنیم ، ولی ممکنه این جایگذاری به قیمت یک تست اشتباه تموم بشه
من خودم سوالایی رو که تتا و O , ... ازین جور چیزا ندارن رو با جایگذاری حل می کنم و بقیه رو هم با روشهای دیگه مثل قضیه اصلی و ... .
(۲۲ بهمن ۱۳۹۲ ۱۲:۱۳ ق.ظ)masoud67 نوشته شده توسط: سلام
قصدم از این سوال حل این دوتا مثال نیست ، و فقط میخوام یه موضوعی را بفهمم
تو این سوال خرس ما گفته از مرتبه n روز زنده می مونه
حالا ما میدیم n=4 که میشه ۷ روز واسه زنده موندن خرس . و به نظر میاد بشه nlogn
حالا ما اگه n=8 بدیم تعداد روز زنده موندن خرس میشه ۱۵ روز و اینجا دیگه nlogn نمیشه
و حالا یه مدل بدتر
اینجا جواب میشه nlogn
ولی وقتی عدد گذاری میکنیم واضحه که بیشتر از nlogn میشه .
مثلا به ازای n=2 حدود ۲۱ مرتبه اجرا میشه
و برای n=8 حدود ۶۰ مرتبه اجرا میشه که با nlogn اختلاف زیادی داره
توی مثالهای قبلی به ازای nهای بزرگ مقداری که بدست میاد با مرتبه ای که در نظر میگیریم تناسب برقرار میشه ولی تو این جور مسائل به ازای nهای کوچک ممکنه جواب غلط را بدست بیاریم
اما سوال: آیا اینگونه سوالات تیپ خاصی دارند که معلوم باشه نباید با جایگذاری حل کرد ؟
چون اغلب مسائلی که راه حل برای حل کردنش نداریم و یا سخته سعی میکنیم از جایگذاری استفاده کنیم ، ولی ممکنه این جایگذاری به قیمت یک تست اشتباه تموم بشه
خب باید تا nهای خیلی بزرگ پیش بریم ولی وقتی سخته من معمولا چندبار تریس میکنم تا روندش دستم بیاد، بعد یه رابطه ی بازگشتی واسش درمیارم و اونو حل میکنم. وگرنه اینکه چون ۷ شده nlogn باشه به نظرم درست نیست، مگر تصادفی! چون اصلا بحث O هستش...
مثلا یه سوال ساختمان ۹۱ کامپیوتر بود فکر کنم، یه نوع ساختار داده بود که از چند مجموعه تشکیل شده بود و ... اونو اگه میخواستی با عددگذاری بری یادمه که اشتباه درمیومد. باید باتوجه به روندش، رابطه مینوشتی.
(۲۲ بهمن ۱۳۹۲ ۱۲:۲۹ ق.ظ)ka arman نوشته شده توسط: من خودم سوالایی رو که تتا و O , ... ازین جور چیزا ندارن رو با جایگذاری حل می کنم و بقیه رو هم با روشهای دیگه مثل قضیه اصلی و ... .یعنی میگید با دیدن تتا و O و ... از خیر خطر جایگذاری بگذریم ؟
به نظرم جایگذاری موقعی خوبه که تو گزینه ها رابطه رو داریم نه مرتبه رو. تازه اون هم مرتبه O که اصلا نمیتونه تخمین دقیقی باشه
مثلا برای سوال اول اگرچه فک کنم شما گفتی nlogn جوابه من مثل زیر حل کردم و به جواب n رسیدم که کلید هم همونو زده بود:
من گفتم از n تا عددمون logn تا عدد داریم (۲، ۴، ۸ و ...) که log روز مصرفشون طول میکشه.
از n-logn عدد باقی مونده حدودا (تاکیدم روی حدودا هستش چون خیلی دقت لازم نداریم) (n-logn) تقسیم بر ۲ عدد زوج داریم که تقریبا ۲ مرجله خوردنشون طول میکشه و n-logn تقسیم بر ۲ عدد فرد داریم که با یه مرحله تموم میشن
[tex](\log n\times\log n) (((n-\log n)\div2)\times2) (((n-\log n)\div2)\times1)=\frac{3n}{2} \log^2n-\frac{3\log n}{2}\in O(n)[/tex]
حالا نمیدونم این روش رو تا چه حد قبول دارین ولی کلا نظرم اینه که در مورد مرتبه ها از جاگذاری استفاده نکنید
(۲۲ بهمن ۱۳۹۲ ۱۲:۳۱ ق.ظ)masoud67 نوشته شده توسط:(22 بهمن ۱۳۹۲ ۱۲:۲۹ ق.ظ)ka arman نوشته شده توسط: من خودم سوالایی رو که تتا و O , ... ازین جور چیزا ندارن رو با جایگذاری حل می کنم و بقیه رو هم با روشهای دیگه مثل قضیه اصلی و ... .یعنی میگید با دیدن تتا و O و ... از خیر خطر جایگذاری بگذریم ؟
دقیقا...
(۲۲ بهمن ۱۳۹۲ ۱۲:۳۷ ق.ظ)hosshah نوشته شده توسط: به نظرم جایگذاری موقعی خوبه که تو گزینه ها رابطه رو داریم نه مرتبه رو. تازه اون هم مرتبه O که اصلا نمیتونه تخمین دقیقی باشهچرا سفسطه میکنی
مثلا برای سوال اول اگرچه فک کنم شما گفتی nlogn جوابه من مثل زیر حل کردم و به جواب n رسیدم که کلید هم همونو زده بود:
من گفتم از n تا عددمون logn تا عدد داریم (۲، ۴، ۸ و ...) که log روز مصرفشون طول میکشه.
از n-logn عدد باقی مونده حدودا (تاکیدم روی حدودا هستش چون خیلی دقت لازم نداریم) (n-logn) تقسیم بر ۲ عدد زوج داریم که تقریبا ۲ مرجله خوردنشون طول میکشه و n-logn تقسیم بر ۲ عدد فرد داریم که با یه مرحله تموم میشن
[tex](\log n\times\log n) (((n-\log n)\div2)\times2) (((n-\log n)\div2)\times1)=\frac{3n}{2} \log^2n-\frac{3\log n}{2}\in O(n)[/tex]
حالا نمیدونم این روش رو تا چه حد قبول دارین ولی کلا نظرم اینه که در مورد مرتبه ها از جاگذاری استفاده نکنید
من کی گفتم nlogn جوابه؟ گفتم وقتی مقدارگذاری با n کوچیک انجام میدی به نظر میاد nlogn جواب باشهحلش رو میدونم و قبول دارم n میشه ولی سوال چیز دیگه ای بود که جواب شما هم ، راه حل خوبیه. یعنی وقتی مرتبه را خواستند ریسک جایگذاری بالاست
(۲۲ بهمن ۱۳۹۲ ۱۲:۳۰ ق.ظ)El@he نوشته شده توسط: خب باید تا nهای خیلی بزرگ پیش بریم ولی وقتی سخته من معمولا چندبار تریس میکنم تا روندش دستم بیاد، بعد یه رابطه ی بازگشتی واسش درمیارم و اونو حل میکنم. وگرنه اینکه چون ۷ شده nlogn باشه به نظرم درست نیست، مگر تصادفی! چون اصلا بحث O هستش...حرف شما درست ولی گیر ما همین رونده است
مثلا یه سوال ساختمان ۹۱ کامپیوتر بود فکر کنم، یه نوع ساختار داده بود که از چند مجموعه تشکیل شده بود و ... اونو اگه میخواستی با عددگذاری بری یادمه که اشتباه درمیومد. باید باتوجه به روندش، رابطه مینوشتی.
وقتی روند بدست بیاد که دیگه حله. ولی وقتی روند گیرمون نیاد چاره ای جز مقداردهی نداریم. مثلا واسه همین مثال دومی
۲ و ۴ میذاری بیشتر از n به توان ۲ میشه
۸ میذاری میشه n به توان ۲
۱۶ بذاری میشه nlog^2n
۳۲ بذاری بازم همون
ونهایتا بالاتر که بری تازه یه خرده به جواب نزدیک میشی
که این جایگذاری تو این مثال راحته و خیلی پیچیده نیست ولی بعضی مثالها واقعا جایگذاری روال سخت و وقت گیری داره
معمولا منظورشون O هستش ولی همیشه تتا مینویسن.میدونیم که Oهم کران بالا هستش.وجواب دقیق نمیده .اون موقع با جایگذاری نمیاد.
پس یه نتیجه گیری کلی میکنم
۱/ وقتی ازمون مرتبه را میخواد مثل تتا و O و ... حواسمون به مقدارگذاری با nهای کوچیک باشه چون ممکنه گزینه اشتباه بهمون بده
۲/ وقتی تو گزینه های رابطه رو داریم جایگذاری مورد خوبی هست
۳/ اگر مسئله جوری هست که میشه مقدار گذاری کرد، شروع کنیم مقدار گذاری و بریم به سمت n های بالا . و اگر دیدیم به ازای n های بزرگتر مرتبه ای که پیدا میشه کمتر و یا بیشتر میشه ، پس نتیجه میگیریم که نباید با صرف جایگذاری چند عدد جواب را بدست بیاریم بلکه باید سعی کنیم رابطه رو حل کنیم ویا یک روال خاص برای مسئله پیدا کنیم و اگر این دوتا مقدور نبود، دوباره عدد های بزرگ و بزرگتر بذاریم و ببینیم جوابمون به کدوم گزینه نزدیک تر میشه
تشکر از همه
اینقدر پوران خوندی شبیه هادی یوسفی شدیا
همش دوست داری نکته در بیاری
قبول دارم حرفاتو
(۲۲ بهمن ۱۳۹۲ ۱۲:۴۱ ق.ظ)masoud67 نوشته شده توسط: چرا سفسطه میکنی
شرمنده اشتباه بصری بود
(۲۲ بهمن ۱۳۹۲ ۱۲:۳۷ ق.ظ)hosshah نوشته شده توسط: به نظرم جایگذاری موقعی خوبه که تو گزینه ها رابطه رو داریم نه مرتبه رو. تازه اون هم مرتبه O که اصلا نمیتونه تخمین دقیقی باشهااینجا من راه حل دکتر ابراهمیم مقدم را میزارم.برای همین سوال یک حلقه while و شرطش اینکه تا موقعه ای n>0باشد خرس زنده میمونه.ابتدا select میکنه یک قطعه رو اگه قطعه فرد باشه یکی از کل کم میکنه و اگه زوج باشه به عنوان یک قطعه کامل اونو در نظر میگیریم .حال میشه یک حلقه while که مرتبش میشه nهمون گزینه یک درسته.
مثلا برای سوال اول اگرچه فک کنم شما گفتی nlogn جوابه من مثل زیر حل کردم و به جواب n رسیدم که کلید هم همونو زده بود:
من گفتم از n تا عددمون logn تا عدد داریم (۲، ۴، ۸ و ...) که log روز مصرفشون طول میکشه.
از n-logn عدد باقی مونده حدودا (تاکیدم روی حدودا هستش چون خیلی دقت لازم نداریم) (n-logn) تقسیم بر ۲ عدد زوج داریم که تقریبا ۲ مرجله خوردنشون طول میکشه و n-logn تقسیم بر ۲ عدد فرد داریم که با یه مرحله تموم میشن
[tex](\log n\times\log n) (((n-\log n)\div2)\times2) (((n-\log n)\div2)\times1)=\frac{3n}{2} \log^2n-\frac{3\log n}{2}\in O(n)[/tex]
حالا نمیدونم این روش رو تا چه حد قبول دارین ولی کلا نظرم اینه که در مورد مرتبه ها از جاگذاری استفاده نکنید
(۲۲ بهمن ۱۳۹۲ ۱۲:۵۳ ق.ظ)hosshah نوشته شده توسط: اینقدر پوران خوندی شبیه هادی یوسفی شدیاما دانشجوهای نکته سنجی هستیم
همش دوست داری نکته در بیاری
قبول دارم حرفاتو
(۲۲ بهمن ۱۳۹۲ ۰۱:۰۳ ق.ظ)hnarghani نوشته شده توسط: ااینجا من راه حل دکتر ابراهمیم مقدم را میزارم.برای همین سوال یک حلقه while و شرطش اینکه تا موقعه ای n>0باشد خرس زنده میمونه.ابتدا select میکنه یک قطعه رو اگه قطعه فرد باشه یکی از کل کم میکنه و اگه زوج باشه به عنوان یک قطعه کامل اونو در نظر میگیریم .حال میشه یک حلقه while که مرتبش میشه nهمون گزینه یک درسته.hosshah تحویل بگیر. وقتی میای سفسطه میکنی، بقیه هم میان مثالو حل میکنن. ولی به متن سوال نگاه نمیکنن
(۲۲ بهمن ۱۳۹۲ ۰۱:۰۸ ق.ظ)masoud67 نوشته شده توسط: hosshah تحویل بگیر. وقتی میای سفسطه میکنی، بقیه هم میان مثالو حل میکنن. ولی به متن سوال نگاه نمیکنن
نه بابا من خواستم مثال بزنم که ما اگه قراره از جایگذاری استفاده نکنیم اینجوری تحلیل کردنم یه راهشه
(۲۲ بهمن ۱۳۹۲ ۰۱:۱۰ ق.ظ)hosshah نوشته شده توسط:از من به تو نصیحت بیشتر پوران بخون، که بیشتر مثل هادی یوسفی نکته سنج بشی(22 بهمن ۱۳۹۲ ۰۱:۰۸ ق.ظ)masoud67 نوشته شده توسط: hosshah تحویل بگیر. وقتی میای سفسطه میکنی، بقیه هم میان مثالو حل میکنن. ولی به متن سوال نگاه نمیکنننه بابا من خواستم مثال بزنم که ما اگه قراره از جایگذاری استفاده نکنیم اینجوری تحلیل کردنم یه راهشه
(۲۲ بهمن ۱۳۹۲ ۰۱:۱۰ ق.ظ)hosshah نوشته شده توسط:البته من متوجه منظورتون شدم ولی من یه راه حلی دیده بودم خواستم اینو در میان بذارمش.دیدی که منبعشو هم بهت گفته بودم..به هر حال ممنون از لطفت آقا مسعود(22 بهمن ۱۳۹۲ ۰۱:۰۸ ق.ظ)masoud67 نوشته شده توسط: hosshah تحویل بگیر. وقتی میای سفسطه میکنی، بقیه هم میان مثالو حل میکنن. ولی به متن سوال نگاه نمیکنن
نه بابا من خواستم مثال بزنم که ما اگه قراره از جایگذاری استفاده نکنیم اینجوری تحلیل کردنم یه راهشه