(۲۸ بهمن ۱۳۹۱ ۰۱:۲۴ ق.ظ)nelli نوشته شده توسط: دوست عزیز تو صورت سوال(مورد سوم) گفته گراف یک دور داره،ولی تو مثال شما بیشتر از یک دور وجود دارهدقیقا تو سوال گفته ۱ دور اما ایشون بیشتر از ۱ دور در نظر گرفتن وقتی فقط ۱ دور داشته باشیم یال می نی مم حتما انتخاب میشه
این نظر من بوده..لطفا بقیه هم نظرشون رو بگن
(۲۸ بهمن ۱۳۹۱ ۱۱:۴۰ ق.ظ)damavand_kellap نوشته شده توسط: دقیقا تو سوال گفته ۱ دور اما ایشون بیشتر از ۱ دور در نظر گرفتن وقتی فقط ۱ دور داشته باشیم یال می نی مم حتما انتخاب میشه
صورت سوال گفته اگر گراف G یک دور داشته باشد که این دور ....
قبول دارم بهتر می تونست بگه ولی نگفته G تنها یک دور داشته باشد یا نگفته فقط یک دور داشته باشد. گفته دوری دارد با این شرایط.
اصلا براساس نوع جمله بندی و ادبیات طراح سوال، اگر تاکید داشت کلمه "تنها" یا "دقیقا" یا "فقط" رو میاورد. همانطور که در ادامه برای گزاره ۳ آورده یا برای گزاره اول آورده.
در مورد سوال ۹۷ که گفته بود متوسط زمان الگوریتم روی ورودی های به اندازه n مرتبه n^2 است.
گزاره اول گفته بود شاید ورودی باشد که مرتبه n^3n داشته باشد
به نظرم یه الگوریتمی که فقط برای یه ورودی خاص بیاد یک تابع مرتبه n^3n رو فراخوانی کنه ولی برای بقیه ورودی ها تابع مرتبه n^2 رو اجرا کنه این گزاره هم درست میشه. چون برای تعداد زیادی داده مرتبه n^2 داریم. متوسط زمانی هم در همین حدود میشه.
نظر شما چیه؟
گزاره دوم و گزاره سوم هم به نظر درست میاد. برای دومی الگوریتم سورت درجی داریم که متوسط n^2 و بهترین حالت n دارد.
(۲۸ بهمن ۱۳۹۱ ۱۰:۲۳ ب.ظ)Computer92 نوشته شده توسط: در مورد سوال ۹۷ که گفته بود متوسط زمان الگوریتم روی ورودی های به اندازه n مرتبه n^2 است.
گزاره اول گفته بود شاید ورودی باشد که مرتبه n^3n داشته باشد
به نظرم یه الگوریتمی که فقط برای یه ورودی خاص بیاد یک تابع مرتبه n^3n رو فراخوانی کنه ولی برای بقیه ورودی ها تابع مرتبه n^2 رو اجرا کنه این گزاره هم درست میشه. چون برای تعداد زیادی داده مرتبه n^2 داریم. متوسط زمانی هم در همین حدود میشه.
نظر شما چیه؟
گزاره دوم و گزاره سوم هم به نظر درست میاد. برای دومی الگوریتم سورت درجی داریم که متوسط n^2 و بهترین حالت n دارد.
در رابطه با گزاره دوم و سوم حق با شماست
اما در رابطه با گزاره اول اگه فقط یه ورودی بیاد که [tex]n^{3n}[/tex] باشه و برای [tex]n^n[/tex] حالت دیگه، اگه حتی [tex]O(1)[/tex] هم بیاد باز میانگین [tex]n^3[/tex] میشه نه [tex]n^2[/tex]
با توجه به این که زمان اجرا فقط به سایز ورودی یعنی n وابسته است به نظرم تعداد کل حالات بعیده از [tex]n^n[/tex] بیشتر باشه
اما مطمئن نیستم
(۲۱ بهمن ۱۳۹۱ ۰۵:۴۱ ب.ظ)somaye_tex نوشته شده توسط: خوب......
تصمیم گرفتم این مسأله رو حل کنم.
البته روش باینری سرچ که دوستمون گفتن از اساس و بنیاد غلطه! چون اینکه صعودی یا نزولی باشه من با دو حرکت بهتون جوابو میگم..... که خب چون خیلی غلطه بهتره راجع بهش بحث نکنیم....
خب. همیشه برای هر الگوریتم یه اصل بنیادی وجود داره که برای اینکه متوجه بشیم الگوریتم چطور کار می کنه ابتدا باید اونو متوجه بشیم تا دچار پیچیدگیهای جزئی الگوریتم نشیم.
.............
چیزی که من از الگوریتم شما فهمیدم اینه
شما در مورد ۱۰ جعبه حرف زدید من در مورد ۳۱ جعبه میگم!
چیزی که من متوجه شدم از توضیحاتتون!
نصف جعبه هارو باز کردید یعنی وقتی ۳۱ جعبه داریم ۱۵ جعبه حداقل باز میشه
حالا بزرگترین عدد هرجا بود اعداد سمت چپ اون حذف میشه والگوریتم روی بقیه ورودی ها به صورت تکراری انجام میشه!منظورتون اینه؟!
اگر که روشتون اینه که هیچی اگرم اینطوری نیست به همین صورتی که من توضیح دادم شما بگید که ما بدونیم چی توس ذهنتونه؟!
خوب هر الگوریتمی یه توضیح فارسی می تونه داشته باشه
مثلا الگوریتم مرتب سازی حبابی ما میگیم که از عنصر اول شروع میکنیم و هر عدد رو با کنار دستیش مقایسه میکنیم اگه عدد دوم کوچیکتر بود جابه جا میشن و این کارو تا انتهای آرایه انجام میدیم تا بزرگترین عدد تو خونه اخر قرار بگیره و به این صورت یکی از طول ارایه کم شد
و همینطور راجع به هر الگوریتمی(یادمه سر جلسه c سوالات سختی استاد اورده بود بچه ها همه شاکی بودن دیگ اخر سر گفت هر چقد بلدید فارسی بنویسید )
شما هم واسه ما که دانشجوهاتونیم هرچقد می تونید فارسی در حد یکی دو خط بگید چیکار میکنه الگوریتمتون
دقیقا منم هنوز متوجه الگوریتم این دوستمون سمیه جان نشدم...
تو هیمن تاپیک هم گفتم، راه درست حل این مساله مثال زدن نیست، با مثال فقط میشه رد کرد الگوریتمهای پیشنهادی رو.
من یکبار دیگه از دوستان میخوام الگوریتمشونو بدون عدد بیان کنن که به یک توافق برسیم. هر الگوریتمی بدترین حالت مربوط به خودش رو داره پس لطفا بدون ذکر بدترین حالت و ... خود الگوریتم رو بیان کنید.
خصوصا سمیه جان،ممنون میشم یکبار دیگه الگوریتمتونو توضیح بدید
خوب مثکه این سؤال خیلی مسئله شده. شما به همون روشی که گفتم اگه موافقین الگوریتم رو چک کنیم. من با حداکثر ۱۱ حرکت جواب رو پیدا می کنم.
من می گم شما کدوم جعبه ها رو به من بگین. خوبه؟
اگه موافقین جعبه ۱ و ۹ و ۱۶ و ۲۳ و ۳۱ رو به من بگید.
فرض کنید همین اعداد باشن این جعبه هایی که گفتید
(۰۱ اسفند ۱۳۹۱ ۰۲:۲۰ ق.ظ)rezareza2 نوشته شده توسط: فرض کنید همین اعداد باشن این جعبه ها یعنی جعبه ۱ =۱ ....
این حالتی که گفتین با تعداد کمتری هم معلوم میشه و بدترین حالت نیست. اما به هر حال....
یعنی تا الان میشه این:
۳۱ - - - - - - - ۲۳ - - - - - - ۱۶ - - - - - - ۹ - - - - - - - ۱
شماره ۲۷ رو بگید.
فرض کنید ۲۷
۳۱ - - - ۲۷ - - - ۲۳ - - - - - - ۱۶ - - - - - - ۹ - - - - - - - ۱
شد این.
حالا ۲۹ رو بگین.
برای اینکه سریعتر پیش بره و لازم نباشه مدام پاسخ بدیم، فرض کنید شما نمی دونید و از من می پرسید اما عدد هرجعبه رو همون ترتبش در نظر بگیرید یعنی مثلا ۲۷ امین همون ۲۷ توش باشه.
و نکته مهمتر،لطفا مبنای انتاخاباتون رو هم بگید تا من بتونم بدترین حالت ورودی رو بهتون بگم.
هر چند این حالت بدترین حالت نیست و اصولاً من می خوام شما یک عددی بگید که فرض نکنید من با توجه به این که می دونم تو جعبه چیه جعبه رو انتخاب می کنم. اما ........
حوب میشه این:
۳۱ - ۲۹ - ۲۷ - - - ۲۳ - - - - - - ۱۶ - - - - - - ۹ - - - - - - - ۱
و حالا ۳۰ رو باز می کنم.
۳۱ ۳۰ ۲۹ - ۲۷ - - - ۲۳ - - - - - - ۱۶ - - - - - - ۹ - - - - - - - ۱
خوب عدد پیدا شد! ۳۱ و با باز کردن تنها ۸ جعبه. درسته؟
خوب حالا به نظرتون من چه پیش فرضی برای باز کردن جعبه ها داشتم؟
اگه میشه بگید الگوریتمتون چیه ؟ مبنای انتخاب کردن چبه؟
شما بنظر میاد باره رو مدام نصف میکنید و عدد وسط رو در نظر می گیرید، درسته ؟ مبنای انتخاب بازه چپ یا راست چیه ؟
مبنای باز کردن جعبه ها رو تو توضیحی که دادم گفتم. ابتدا کل بازه رو ۴ قسمت می کنیم. همون ۱ و ۹ و ۱۶ و ۲۳ و ۳۱/ هر بازه تقریباً کف n/4
بعد بازه شامل بزرگترین عدد رو نگه می داریم. و بقیه رو دور میریزیم. البته این به این معنی نیست که در اون قسمت که دور میریزیم جعبه ای با این مشخصات نداریم. چون این خاصیت منحصر به فرد نیست. بلکه به این معناست که در بازه ای که نگه میداریم حتماً عددی با این مشخصات داریم. که با کمی تمرکز متوجه میشین. در هر مرحله همین عمل رو تکرار می کنیم. یعنی بازه شامل عدد بزرگتر رو نگه میداریم و بقیه رو دور میریزیم. با کمی توجه متوجه میشین در هر مرحله تعداد اعداد تقریباً داره نصف میشه. با کمی دقت در بدترین حالت به عدد ۱۱ میرسیم.
راستی منظورم از بازه اینه:
۱--------۱۶---------۱۲--------۳---------۱۵ در این مثال بازه میشه از ۱۲ تا ۱ که شامل ۱۶ که بزرگتره میشه.
و در این :
۳۰ ----------۱۷---------۲-----------۱۵------------۱۹ از ۱۷ تا ۳۰ رو نگه میداریم مثل مثالی که شما زدین که شامل ۳۰ هست.
اگه خواستین میتونم جایگشتی رو بهتون بدم که به ۱۱ حرکت نیاز داشته باشه. اما هیچ جایگشتی وجود نداره که به ۱۲ حرکت احتیاج داشته باشه.
امیدوارم این توضیح به همراه ۳ دفعه ای که قبلاً توضیح دادم کافی بوده باشه.
اگه نه جایگشت دیگه ای بگید تا دوباره تست کنیم.