من خودم نتونستم برای این سوال الگوریتم پیدا کنم.جواب پارسه رو خوندم.اینجا هم گذاشتم. دقیقا متوجه نمیشم چرا هربار عددی که قدر مطلق بیشتری داره از دوطرف حذف میکنه. چرا اینجوری مجموع به صفر نزدیکتر میشه؟ مثلا فرض کنید مجموعمون -۵ شده. حالا یه طرف ۶ داریم یه طرف -۴ اگه ۶ رو حذف کنیم که بدتر میشه مجموع.
ممنون میشم اگه یکی توضیح بده
سوال:
[attachment=15168]
جواب پارسه:
[attachment=15169]
این چرا آرایه رو مرتب میکنه ؟! مگه اندیس نمی خواد ؟ خوب با مرتب کردن که اندیس آرایه ى اولى که از بین میره. اصلا دیگه همه ى حساب کتابایى که کرده توى آرایه اصلى جواب نمیده.
به نظر من این مساله راه حل پویا از مرتبه ى n به توان ۲ داره.
—-----------
یه چیز دیگه الان متوجه شدم. این کسی که سوال رو جواب داده فکر کرده سوال حاصل سیگما رو میخواد. سوال اون اندیس ها رو مى خواد.
از یه ادمی که تو الگوریتم خیلی بزرگه پرسیدم گفت با تقسیم و حل nlogn میشه می گفت قبل کنکور کدش رو زده بوده(توضیح داد ولی نفهمیدم)
داریم در مورد فاصله حرف میزنیم اون عددی که قدر مطلق بیشتر داره ما را بیشتر از صفر دور میکنه پس جواب خوبی نیست
الان یک مثال عددی بزن
مثلا ارایه-۶ -۳ -۲ ۲ ۳ اگر ۶- حذف کنی فاصله ات میشه ۰
(۱۳ بهمن ۱۳۹۲ ۰۱:۵۸ ب.ظ)atharrashno نوشته شده توسط: داریم در مورد فاصله حرف میزنیم اون عددی که قدر مطلق بیشتر داره ما را بیشتر از صفر دور میکنه پس جواب خوبی نیست
الان یک مثال عددی بزن
مثلا ارایه-۶ -۳ -۲ ۲ ۳ اگر ۶- حذف کنی فاصله ات میشه ۰
خوب این چه ربطى به مرتب کردن آرایه داره ؟ بعد اینکه اصلا این استدلال که اونى که قدر مطلق بیشترى داره باید حذف شه قابل قبول نیست. شاید اگر همین رو با عدد دیگه اى جمع کنیم حاصل نزدیک صفر بشه.
(۱۳ بهمن ۱۳۹۲ ۰۱:۵۸ ب.ظ)atharrashno نوشته شده توسط: داریم در مورد فاصله حرف میزنیم اون عددی که قدر مطلق بیشتر داره ما را بیشتر از صفر دور میکنه پس جواب خوبی نیست
الان یک مثال عددی بزن
مثلا ارایه-۶ -۳ -۲ ۲ ۳ اگر ۶- حذف کنی فاصله ات میشه ۰
برای این مثال خاص کار میکنه. اما به قول دوستمون نباید مرتب مبکرده، حتی اگه مرتب هم کنه برای مثالهای دیگه هم جواب نمیده این روش.
کسی هست که الگوریتم کاملشو بلد باشه؟
(۱۳ بهمن ۱۳۹۲ ۰۹:۱۹ ب.ظ)PanizIr نوشته شده توسط:بعد از چند تا مثال نقض فهمیدم که این الگوریتم فقط برای وقت هایی که جواب سیگما ۰ باشه درست کار میکنه چون اصولا این حل همیشه جواب ۰ بدست میاره!! (احتمالا حل کننده هم همچین مثالی زده)(13 بهمن ۱۳۹۲ ۰۱:۵۸ ب.ظ)atharrashno نوشته شده توسط: داریم در مورد فاصله حرف میزنیم اون عددی که قدر مطلق بیشتر داره ما را بیشتر از صفر دور میکنه پس جواب خوبی نیست
الان یک مثال عددی بزن
مثلا ارایه-۶ -۳ -۲ ۲ ۳ اگر ۶- حذف کنی فاصله ات میشه ۰
برای این مثال خاص کار میکنه. اما به قول دوستمون نباید مرتب مبکرده، حتی اگه مرتب هم کنه برای مثالهای دیگه هم جواب نمیده این روش.
کسی هست که الگوریتم کاملشو بلد باشه؟
الان سر خونه اولیم
اما اول:
دکتر سید جوادی برای این سوال ان به توان دو مهندس یوسفی گفتن ان لاگ ان ایشون احتمالا فرض بر مرتب کردن گذاشتن
دوم
مشابه همین سوال را اگر سیگما ماکزیمم را بخواد در کتاب پوران پژوهش گفتن با درجه ان امکان پذیره
اگر کسی چاپ جدید صحفه ۳۴۱ داره پاسخ سوال ۸۰ را یه نیگا بکنه(من ندارم)
سلام....
چون یکی از بچه ها گفتن این سوالو از دکتر یوسفی بپرسم همین الان از ایشون از طریق تلفن پرسیدم:
گفتن اگر بخواهیم اینکارو انجام بدیم باید در ابتدا آرایه رو sort کنیم که مرتبه sort آرایه هم میشه تتا nlogn و بعد از طریق الگوریتم بدستش بیاریم گفتن الگوریتمشم جوری نیست که اط پشت تلفن بشه گفت...
موفق باشید....
(۱۶ بهمن ۱۳۹۲ ۱۰:۰۲ ب.ظ)mahsalove نوشته شده توسط: سلام....
چون یکی از بچه ها گفتن این سوالو از دکتر یوسفی بپرسم همین الان از ایشون از طریق تلفن پرسیدم:
گفتن اگر بخواهیم اینکارو انجام بدیم باید در ابتدا آرایه رو sort کنیم که مرتبه sort آرایه هم میشه تتا nlogn و بعد از طریق الگوریتم بدستش بیاریم گفتن الگوریتمشم جوری نیست که اط پشت تلفن بشه گفت...
موفق باشید....
این که شد همون روش اول. آخه اگه مرتب کنبم که ایندکسارو از دست دادیم. مگه اینکه صورت سوال اشتباه باشه!