راه حل چند جمله ای این سوال چیست؟
با هر حلی نمایی بدست میاد!
![[تصویر: 66534_1_1379095321.JPG]](https://img.manesht.ir/66534_1_1379095321.JPG)
من این سوال را این طوری تحلیل می کنم:
در هر سطر باید عنصر max را پیدا کنی .
در سطر اول که تکلیفش معلومه خود ۷
در سطر دوم ۱مقایسه
در سطر سوم ۲ مقایسه
در سطر چهارم ۳ مقایسه
و...
در سطر آخر برای n عنصر n-1 مقایسه
که مجموعا می شود: n*n-1 /2
پس میشه از مرتبه n^2
یعنی عمل اصلی مقایسه است.
اما خواهر این طور توی سطر دوم ۸ انتخاب میشه ولی داری بیبینی که بیشترین مسیر ما باید از ۳ بگزره بعد تازه توی سطر سوم ۸ بزرگتر که
از سطر دوم ۸ انخاب میشه از سطر سوم هم ۸ اما راهی نیست که بتونند به هم برسند!
این راه جواب نمیده خواهر
(۲۳ بهمن ۱۳۹۰ ۰۴:۱۵ ب.ظ)atharrashno نوشته شده توسط: اما خواهر این طور توی سطر دوم ۸ انتخاب میشه ولی داری بیبینی که بیشترین مسیر ما باید از ۳ بگزره بعد تازه توی سطر سوم ۸ بزرگتر کهآره این نکته رو دقت نکردم
از سطر دوم ۸ انخاب میشه از سطر سوم هم ۸ اما راهی نیست که بتونند به هم برسند!
این راه جواب نمیده خواهر
این مساله با استفاده از برنامه نویسی به روش پویا باید حل بشه....
نمی دونم چطوری توضیح بدم. اینقدر روی پویا مسلط نیستم که بتونم توضیح بدم ولی وقتی این مساله رو دیدم تونستم به جواب برسم!
مثل مساله خرد کردن پول با کمترین سکه هست
صورت سئوال گفته مسیری از راس مثلث به پایین .پس با ید حتما از بالا شروع بشه و فکر نکنم به روش پویا حل بشه.چون تو روش پویا جواب در پایین ترین سطح کاملا مشخصه و نیاز به جستجو بین سایر گزینه‌ها نیست
به نظر من دارای مرتبه n است. چون اگر فرض کنیم الگوریتم به این صورت باشه:
در بالاترین سطح ریشه با دو عدد پایین‌تر از خودش مقایسه میشه (یکی با عدد پایینی و سمت چپ خودش و همچنین با عدد پایینی و سمت راست خودش) هرکدوم که بیشتر بود اون رو انتخاب میکنه.در لایه بعد هم به همین صورت.( برای هر عدد ۲ تا مقایسه باید انجام بده و این کار رو به تعداد سوح باید انجام بده یعنی به اندازه طول مسیر)
خواهر فاطیما شما لازم نیست برای همه عناصر هر سطح مقایسه را انجام بدی مثلا فک کن ۷۳۸ را تا حالا اومدی بعدی ۱ هست که باید اتخاب بشه برای اینکه ۱ انتخاب کنی لازم نیست مثلا ۴ سطر سوم را براش مقایسه انجام بدی
دوم هم اینکه فرض برا همه عناصر یک سطح مقایسه انجام بدی
خوب
توی هر سطح که عناصر ثابت نیستند که در بدترین حالت توی سطر اخر تعداد عناصر ان هست خوب با ان تا سطر جواب میشه ان به توان دو
پس این شیوه هم جواب نمیده
(۲۳ بهمن ۱۳۹۰ ۰۵:۲۵ ب.ظ)باد نوشته شده توسط: این مساله با استفاده از برنامه نویسی به روش پویا باید حل بشه....یه خورده بیشتر توضیح بدین
نمی دونم چطوری توضیح بدم. اینقدر روی پویا مسلط نیستم که بتونم توضیح بدم ولی وقتی این مساله رو دیدم تونستم به جواب برسم!
مثل مساله خرد کردن پول با کمترین سکه هست
بچه‌ها به نظورتون نمیشه این الگوریتم را با تصیحح به یک الگوریتم دکستری تبدیل کرد که به جای کوتاه ترین مسیر دنبال طولانی ترین مسیره و به جای همه رئوس مسیر ان راس میخواد؟(تعداد کل رئوس این جا o(n^2 هست
نظرتون چیه؟
به کمک توضیحات دوستان سوال حل شد:
ما میتونیم مساله را یگ گراف جهت دار فرض کنیم که هر گره به دو گره سطح گایین خودش یال داره
۲ این گراف در حقیقت یک گراف توپولوزیکی است که با یک تغیر میتوان ان را به یک گراف n+1 مرحله تبدیل کرد
کافی است از همه گره های سطح اخر یک یال به گره فرضی n+1 ببریم و هزینه ان یالها را ۰ قرار بدهیم در روند حل خلیلی وارد نمی شود:
با توجه به توضیحات کتاب اقای قلی زاده و لینک سعیده در طولانی ترین مسیر:
میتوان بزرگترین مسیر را در یک گراف k مرحله ای از درجه o(v+e+k) بدست اورد در اینجا:
تعداد یالها: =۲+۴+۶+...+n+2(n-2) = o
jتعداد راس ها= مساحت مثلث=O(n^2)
در نتیجه:
O(n^2+n^2+n)=O(n^2
(۲۶ بهمن ۱۳۹۰ ۰۱:۲۵ ب.ظ)saeedeh123 نوشته شده توسط: خیلی ممنون. من کلیت قضیه رو فهمیدم چیه و اینکه میشه از مرتبه n^2 بدست آورد ولی جزییاتش نه.
دیگه فکر کنم جزییات باشه برای بعد کنکور بهتره.
پس قرار ما جمعه بعد از ظهر همین تاپیگ
تاپیک زیر خاکی!
الگوریتم این کار این طوری میشه:
از راس بالا شروع می کنیم.
در هر سطر هر عدد موجود در اون سطر رو با max دوتا عدد بالایی جمع می کنیم.
مثلا تو سوال بالا اولین عدد ۷ هست که کاری باهاش نداریم چون عنصر بالایی نداره.
سطر بعدی اعداد ۳ و ۸ رو داریم.
۳ رو با ماکزیمم اعداد بالایی یعنی ۷ جمع می کنیم میشه ۳+۷=۱۰
۸ رو با ماکزیمم اعداد بالایی یعنی ۷ جمع می کنیم میشه ۸+۷=۱۵
میریم سطر بعدی:
۸ و ۱ و ۰
۱۸=۸+(max(10
۱۶=۱+(max(10,15
۱۵=۰+(max(15
سطر بعدی:
۲و ۷ و ۴ و ۴
۲۰=۲۰ +(max(18
۲۵=۷+(max(16,18
۲۰=۴+(max(16,15
۱۹=۴+(max(15
برای سطر بعدی هم به همین ترتیب ادامه میدیم.
به نظر من چون تو این الگوریتم پیداکردن ماکزیمم و بررسی هر گره مورد توجه هست و اینکه پیداکردن ماکزیمم در زمان (۱)o انجام میشه پس پیداکردن ماکزیمم زمان بر نیست.
چون تعداد گره ها برابر است با ۲/ (n*(n+1
پس مرتبه الگوریتم هم n^2 می شود.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
الآن مقدار n دقیقاً چیه؟ اگه ارتفاع باشه پیچیدگی میشه از مرتبه n^2 و اگه تعداد نودها باشه پیچیدگی میشه از مرتبه n. چون هر گره رو دقیقاً یکبار پیمایش میکنیم و بعد با پیدا کردن ماکزیمم در سطر آخر، مسیر رو مشخص میکنیم.
تعداد گره ها که از مرتبه n^2 هست. n هم میشه ارتفاع.
مرتبه تعداد گره هاست