پارس‌کدرز چگونه کار می‌کند؟

از پارس‌کدرز بیشترین بهره را ببرید و رویای کاری خود را زندگی کنید.

پارس‌کدرز خریداران یا کارفرمایان را به مجری‌ها /فریلنسرهای خبره‌ای متصل می‌کند که برای انجام پروژه آماده هستند.

طراحی الگوریتم تقسیم و غلبه با جاوا(۲۷۰۷)

چهار سال پیش منتشر شده

تعداد بازدید: 639

کد پروژه: 135019


شرح پروژه

سلام

پروژه تقسیم و حل طراخی الگوریتم ¼ دارم

سوال سختی بهتون دادند… برای این سوال باید یک سری پیش فرض ها رو بدونی مثل این که چه طور با استفاده از چند نقطه یک شکل محدب بسازیم و چه طور تشخیص بدیم چه نقاطی داخل این شکل محدب قرار می گیرند و چه نقاطی نه. برای این کار صفحات ۴۴ تا ۴۹ پی دی افی که می فرستم رو بخون یکم سخته فهمش ولی خب چاره ای نیست. اما فعلا الگوریتم اصلی رو اول خوب بفهمش بعد برو سر کتابه.

الگوریتم اصلی: توی این سوال ما یک سری نقطه داریم که سه مولفه دارند x و y و ارزش نقطه مورد نظر. برای حلش به روش تقسیم و حل باید اون ها رو بر اساس مولفه‌ی x یا y مرتب کنیم و بعد به دو دسته تقسیمشون می کنیم و برای هر کدوم شکل محدبی که مجموع ارزش نقطه های آن، از نصف ارزش مجموع کل نقاط زیر مسئله (و نه تمام نقاط مسئله) بیشتر هست رو پیدا کنیم. فرض می کنیم که این کار انجام شده. یعنی ما یک شکل محدب سمت چپ داریم و یک شکل محدب سمت راست. حالا برای این که شکل محدب کلی رو بدست بیاوریم باید این دو شکل را با هم ترکیب کنیم. اول تمام ترکیب های ۳ نقطه ای را که از ترکیب نقاط شکل محدب سمت چپ و راست هستند را بدست می آوریم مثلا دو نقطه از شکل سمت چپ و یک نقطه از شکل سمت راست را با هم ترکیب می کنیم تا یک مثلث بوجود بیاید حالا چک می کنیم که آیا نقطه ای از بقیه کل نقاط در این شکل هست یاد نه و اگر بود ارزشش را با ارزش سه نقطه قبلی جمع می کنیم در صورتی که از نصف مجموع ارزش کل نقاط بیشتر بود یک کاندیدای جواب است. تمام حالت های سه تایی را محاسبه می کنیم و در صورتی که چند تا از آنها کاندیدای جواب بودند شکلی را انتخاب می کنیم که کمتر از بقیه نقطه دارد. اگر دو شکل دارای تعداد یکسانی نقطه بودند هر کدام ارزش بیشتری داشتند را انتخاب می کنیم و اگر هیچ شکلی از ترکیب سه نقطه کاندیدای جواب نبود. یک گام جلوتر می رویم و ۴ نقطه را با هم ترکیب می کنیم و این کار را تا جایی که تمام نقاط شکل محدب سمت چپ و راست را در ترکیب کنیم ادامه می دهیم. 

در نهایت یک شکل چند نقطه ای بدست می آید که حتما جواب است (با روابط ریاضی میشه ثابتش کرد). حالا روند کلی روش تقسیم و حل به این شکل است که اول نقاط رو به دو دسته تقسیم می کنیم و هر کدام از دو دسته را دوباره نصف می کنیم تا جایی که تعداد نقاط از چهار نقطه کمتر شود. وقتی به چنین جایی از مسئله رسیدم تمام نقطه هایی که مانده چه یک نقطه چه دو نقطه و چه سه نقطه جواب محسوب می شوند و در یک مرحله بالاتر با نقاط جواب قسمت کناری ترکیب می شوند تا یک شکل محدب بسازند. سپس شکل محدب بدست آمده با شکل محدب جواب دو قسمت مثلا سمت راست ترکیب می شود تا به جایی برسیم که فقط یک شکل سمت چپ بماند و یک شکل سمت راست. در نهایت با ترکیب این دو شکل به جواب مسئله می رسیم.

و حالا یک سری نکات:

۱) از ترکیب سه نقطه یا بیشتر ما حتما می توانیم یک شکل محدب بسازیم. 

۲) ما باید یک تابع داشته باشیم که نقاطی که می خواهیم ترکیب کنیم را به این تابع بفرستیم و این تابع چک کند که آیا نقاط دیگری در این شکل محدب ما پیدا می شود یا نه و اگر می شود تعداد و ارزش آنها را برای برگرداند. در نهایت با جمع ارزش نقاطی که خودمان انتخاب کردیم برای ترکیب و نقاطی که تابع در شکل ما پیدا کرده ارزش کل شکل و تعداد نقاط آن مشخص می شود.

۳) چند مثال با این روش حل کنید تا روند کار دستت بیاد.

۴) برای بهتر فهمیدن روش تقسیم و حل بهتره این دو تا مثال همون کتاب یعنی تعیین نزدیک ترین زوج نقطه در فضای یک بعدی و دو بعدی رو بخون. صفحات ۴۲ تا ۴۴.

دد لاین پروژمون ۱۸ ام فروردینه

تا اون موقع حاضر میشه

این پروژه شامل 1 فایل مهم است، لطفا قبل از ارسال پیشنهاد حتما نسبت به بررسی این فایل اقدام فرمایید.

مهارت ها و تخصص های مورد نیاز


بودجه

100,000 تومان تا 300,000 تومان

مهلت برای انجام

5روز

وضعیت مناقصه

بسته


درباره کارفرما

عضویت یازده سال پیش

52953 پروژه ثبت شده ،
43 پروژه در حال انجام ،
243 پروژه آماده دریافت پیشنهاد ،
نرخ پذیرش پیشنهاد 15%

برای پیدا کردن پروژه‌های مشابه ثبت نام کنید و پروفایل خود را بسازید.

ورود با گوگل
یا
نام نباید خالی باشد.
نام خانوادگی نباید خالی باشد.

نیاز به استخدام فریلنسر یا سفارش پروژه مشابه دارید؟

سفارش پروژه مشابه

قادر به انجام این پروژه هستید؟

ثبت نام کنید

مهلت ارسال پیشنهاد قیمت برای این پروژه تمام شده است

سری به پروژه‌های مشابه بزنید

روش کار در پارس‌کدرز

به رایگان یک حساب کاربری بسازید

مهارت‌ها و تخصص‌های خود را ثبت کنید، رزومه و نمونه‌کارهای خود را نشان دهید و سوابق کاری خود را شرح دهید.

به شیوه‌ای که دوست دارید کار کنید

برای پروژه‌های دلخواه در زمان دلخواه پیشنهاد قیمت خود را ثبت کنید و به فرصت‌های شغلی منحصر به فرد دسترسی پیدا کنید.

با اطمینان دستمزد دریافت کنید

از زمان شروع کار تا انتهای کار به امنیت مالی شما کمک خواهیم کرد. وجه پروژه را از ابتدای کار به امانت در سایت نگه خواهیم داشت تا تضمین شودکه بعد از تحویل کار دستمزد شما پرداخت خواهد شد.

می‌خواهید شروع به کار کنید؟

یک حساب کاربری بسازید


بهترین مشاغل فریلنسری را پیدا کنید
رشد شغلی شما به راحتی ایجاد یک حساب کاربری رایگان و یافتن کار (پروژه) متناسب با مهارت‌های شما است.

پیدا کردن کار (پروژه)

تماشای دمو روش کار