راهنمایی در مورد چند برنامه

amir_a2015 · Mar 28, 2015

سلام
در مورد نوشتن دو برنامه مشکل دارم، در صورت امکان راهنماییم کنین. منظورم فقط راهنمایی در مورد راه حله، کدش رو نمیخوام.
1- پیدا کردن i-امین عنصر ماکسیمم یا (مینیمم) در یک آرایه نامرتب
2- پیدا کردن زوج عنصر با مجموع مشخص در یک آرایه نامرتب (مثلا 2 عنصر که مجموعشون 10 بشه)
یه راه حل بهینه میخوام با کمترین زمان اجرا.
ممنون میشم راهنمایی کنین.

rezazarasvand · Mar 29, 2015

سلام دوست من به انجمن خوش اومدی برای این کار روش های زیادی وجود داره من چیزی که به ذهنم میرسه رو عرض میکنم
سوال اول:
به ترتیب شروع به خواندن آرایه میکنی مثلا آرایه a{i} v رو در نظر بگیر. ابتدا a1 رو به یک متغیر کمکی بده و متغییر کمکی رو به ترتیب با اعضا بعد مقایسه کن برای ماکسیمم بزرگتر رو به متغیر کمکی بده و برای مینیمم برعکس. سپس جواب متغیر کمکی خواهد بود.
سوال دوم:
راهی که به ذهنم میرسه اینه آرایه بخوان و عضو اول رو از مجموع مشخص کم کن سپس حاصل رو با دیگر اعضا مقاسه کن اگر برابر اون پیدا کردی دو عضو آرایه رو به خروجی بده در غیر این صورت عضو بعد به همین ترتیب.
موفق باشی.

amir_a2015 · Mar 29, 2015

rezazarasvand گفت:
سلام دوست من به انجمن خوش اومدی برای این کار روش های زیادی وجود داره من چیزی که به ذهنم میرسه رو عرض میکنم
سوال اول:
به ترتیب شروع به خواندن آرایه میکنی مثلا آرایه a{i} v رو در نظر بگیر. ابتدا a1 رو به یک متغیر کمکی بده و متغییر کمکی رو به ترتیب با اعضا بعد مقایسه کن برای ماکسیمم بزرگتر رو به متغیر کمکی بده و برای مینیمم برعکس. سپس جواب متغیر کمکی خواهد بود.
سوال دوم:
راهی که به ذهنم میرسه اینه آرایه بخوان و عضو اول رو از مجموع مشخص کم کن سپس حاصل رو با دیگر اعضا مقاسه کن اگر برابر اون پیدا کردی دو عضو آرایه رو به خروجی بده در غیر این صورت عضو بعد به همین ترتیب.
موفق باشی.

ممنون از راهنماییتون. اما بازم فکر میکنم زمان اجراش زیاده. باید با یه روش تقسیم و حل رفت.

the_king · Mar 29, 2015

amir_a2015 گفت:
سلام
در مورد نوشتن دو برنامه مشکل دارم، در صورت امکان راهنماییم کنین. منظورم فقط راهنمایی در مورد راه حله، کدش رو نمیخوام.
1- پیدا کردن i-امین عنصر ماکسیمم یا (مینیمم) در یک آرایه نامرتب
2- پیدا کردن زوج عنصر با مجموع مشخص در یک آرایه نامرتب (مثلا 2 عنصر که مجموعشون 10 بشه)
یه راه حل بهینه میخوام با کمترین زمان اجرا.
ممنون میشم راهنمایی کنین.

پیچیدگی زمانی این دو تا برنامه اولی در حد (O(n و دومی (O(n log n ئه، یعنی ذاتا ساده و با پیچیدگی کم هستند و راه حل ساده و عادی شون با راه حل بهینه شده شون فرق آنچنانی نداره.
اینجور مسائل ساده رو نمیشه با روش های بهینه و تخمینی بصورت محسوس سریعتر کرد.
الگوریتم هایی که برای اینجور مسائل طراحی میشه راه حل بهتری مثل n / 2 یا (log(n نخواهند داشت.