الگوریتم تقسیم و حل

[diba1365]

salam
الگوریتم تقسیم و حل برای محاسبه مجموع عناصر لیستی از اعداد { 1,2,3,4,....N}
می خواستم اخه الگوریتم معمولیشو می دونم اما نمیدونم الگوریتم تقسیم و حل چیه؟؟؟؟؟ میشه کمکم کنید!
ممنون.

[raha_hakhamanesh]

با سلام

آیا مطمئن هستید سوال شما صحیح و دارای جواب است

مجموعه اعداد صحیح مجموعه متناهی نیست . ! ؟

[diba1365]

sorry سوال من::
محاسبه مجموع عناصر لیستی از اعداد {1,2.3,....N}
ok
الگوریتم تقسیم و حل /???؟؟؟؟

[raha_hakhamanesh]

با سلام

پیام شما را دیدم توجه کنید

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

موفق باشید

[k.robot]

sum(low,high)
{if low=high+1
return low+high
elseif low=high
return low
else{
mid=(low+high)/2
return(sum(low,mid)+sum(mid+1,high)
}
}

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

[diba1365]

merciiiiiiiii
bale man hamino mikhastam khode khodeshe:D
khili motashakaeram
good.

[k.robot]

u r welcome

[diba1365]

مرتبه پیچیدگی این الگوریتم چنده؟ [θ (n log n]
[W(N)=2W(N/2)+n W(1)=1]

Dorosteh?

[k.robot]

O(n)

مثل روش معمولیه

[raha_hakhamanesh]

T(n)=2T(n/2)+d

O(log n)

[k.robot]

عزیز دل برادر اونی که شما میگی ضریب 2 نداره.بیشتر دقت کن.

[diba1365]

salam
bebakhshid manzooretoon az d chie?!mishe ye kam tozih bedin!?
o(n)
mishe ya o(logn
mamNon
.

[Developer Programmer]

bebakhshid manzooretoon az d chie?

d یه عدد همیشه ثابت مثل عدد یک

T(n)=2T(n/2)+d

O(log n)

میشه (small omega (logn یا همون (small O (n

[mehdi_7]

این الگوریتم که فقط تعداد ترکیب ها را نشان می دهد. در واقع باید هر ترکیب را هم چاپ کند
مثلا 1 ، 1 2 ، 1 2 3 ، ...

[man_a_m_m]

با سلام و خسته نباشيد
يه سوال دارم


فرض كنيد در يك الگوريتم تقسيم و حل همواره نمونه اي به اندازه n را بهn زير نمونه به اندازه ي n/3 تقسيم مي كنيم و مراحل تقسيم و تركيب ، زمان خطي هستند . يك معادله بازگشتي براي زمان اجراي T(n) بنويسيد و اين معادله بازگشتي را براي T(n) حل كنيد . حل خود را با نماد مرتبه نشان دهيد .


با تشكر

[Developer Programmer]

فرض كنيد در يك الگوريتم تقسيم و حل همواره نمونه اي به اندازه n را بهn زير نمونه به اندازه ي n/3 تقسيم مي كنيم و مراحل تقسيم و تركيب ، زمان خطي هستند . يك معادله بازگشتي براي زمان اجراي T(n) بنويسيد و اين معادله بازگشتي را براي T(n) حل كنيد . حل خود را با نماد مرتبه نشان دهيد

Off Topic:
میخوای، یه روز هماهنگ کن با بچه ها بیایم دانشگاه، تمرینانت رو تحویل بدیم؟

T(n)=3t(n/3)+n

مثلا اگه یه لیست رو 5 قسمت بشکنیم طوری که اندازه هر قسمت 1/3 قبلی باشه و قسمت ترکیب آرایه، خطی باشه :
T(n)=5t(n/3)+n