تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر [بایگانی]

View Full Version : تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر

Kambiz

پنج شنبه 20 شهریور 1382, 03:16 صبح

تقسیم و تسخیر (Divide-and-Conquer)

طراحی الگوریتم در این روش بدین صورت حاصل می‌شود که:
مورد اصلی مسئله‌ی داده شده برای حل را به چندین مورد کوچکتر (از همان نوع مورد اصلی) تقسیم می‌کنیم٬ سپس موارد کوچکتر را بطور مجزا حل و نتیجه حاصل از هر زیر مورد را با هم ترکیب کرده تا نتیجه مورد اصلی مسئله را بیابیم.

اگر تاکنون از روتینهای بازگشتی (Recursive Procedures) برای حل مسائل استفاده کرده باشید با روش کار تقسیم و تسخیر از پیش آشنایی دارید.

الگوریتمهایی که با این روش طراحی می‌‌شوند از دید من بسیار زیبا٬ ساده و خوانا هستند. اما این نکته منفی را هم نباید از قلم انداخت که اگر تعداد موارد منقسم شده از مورد اصلی زیاد باشد٬ ممکن است بازده الگوریتم حاصل از روش تقسیم و تسخیر افت کند.

مثال 1: جستجوی دودویی (Binary Search)
در نظر بگیرید که فهرستی از اسامی و آدرسهای مرتبط به هر اسم داشته باشیم و این فهرست دارای N جفت اسم و آدرس باشد که به ترتیب حروف الفبا بر اساس اسم مرتب شده و در دو آرایه نگهداری شوند:

Names(1..N)
Numbers(1..N)
می‌خواهیم با دادن هر اسم٬ آدرس مربوط به اسم را بیابیم. در این مثال فرض می‌کنیم که هر اسم مورد پرسش حتما در آرایه وجود دارد تا الگوریتم و شرح آن را ساده‌تر کرده باشیم.

الگوریتم تقسیم و تسخیری که این مسئله را حل می‌کند٬ ساده‌ترین الگوریتم در این مدل الگوریتمی است که حاصل نگرشی بگونه زیر است:

اسم داده شده
یا
درست در وسط فهرست قرار دارد
یا
در نیمه بالایی فهرست (بالا)
یا
در نیمه پایینی فهرست (پایین)

چون فهرست مرتب شده است٬ پس شرط بالا در صورتی درست است که اسم داده شده کوچکتر از اسم قرارگرفته در قسمت میانی باشد. و شرط پایین در صورتی درست است که اسم داده شده بزرگتر از اسم قرارگرفته در قسمت میانی باشد.

این دید به مسئله٬ الگوریتم زیر را در پی خواهد داشت:

function Search(X: name; Start, Finish: integer) return address
Middle: integer
begin
Middle <- (Start + Finish) / 2
if X = Names(Middle) then
return Numbers(Middle)
elseif X < Names(Middle) then
return Search(X, Start, Middle - 1)
else -- X > Names(Middle)
return Search(X, Middle + 1, Finish)
endif
end
الگوریتم بالا رو چگونه باید اصلاح کرد تا جوابگوی حالتی باشد که اسم وارد شده در فهرست موجود نیست؟ یا با عبارت متداول برای الگوریتمهای تقسیم و تسخیر، در چه مرحله‌ای این اصلاح صورت گرفته شود؟

مثال 2: بدست آوردن همه ترکیبهای مجموعه‌ای از عناصر (Permutations)
با چیدن اعداد 4 و 5 و 8 چه اعدادی می‌توان بدست آورد؟ با چیدن حروف الف و میم و لام در کنار هم چه واژه‌های می‌توان ساخت؟ شرح و الگوریتم حل این مسئله با روش تقسیم و تسخیر را قبلا در جواب پرسش یکی از دوستان در پست دیگری نوشته ام. لطفا به لینک زیر رجوع کنید:
http://www.barnamenevis.org/forum/viewtopic.php?p=13185#13185

----------------------------------------------------------------------------------------------------------
تکنیکهای طراحی الگوریتم - مقدمه (http://www.barnamenevis.org/forum/viewtopic.php?t=2796)

(امید)

پنج شنبه 20 شهریور 1382, 18:17 عصر

با سلام

برای سوال اول :

function Search(X: name; Start, Finish: integer) return address
Middle: integer
begin

if( finish<start)or(x<start)or(x>finish) then
return('موجود نبید')
else if

Middle <- (Start + Finish) / 2
if X = Names(Middle) then
return Numbers(Middle)
elseif X < Names(Middle) then
return Search(X, Start, Middle - 1)
else -- X > Names(Middle)
return Search(X, Middle + 1, Finish)
endif

endif
end

با تشکر از DelphiArea جهت توجه به این بخش :)

Kambiz

جمعه 21 شهریور 1382, 00:34 صبح

تا حدودی درسته! :wink:

دونستن اینکه پارامتر Start بزرگتر یا مساوی پارامتر Finish هست کافیه که بدونیم هنوز چیزی برای جستجو (تقسیم) داریم. بطور کلی در روش تقسیم و تسخیر وقتیکه دیگه مسئله قابل تقسیم نیست به معنی اینه که کار تموم شده و نوبت این رسیده که نتایج حاصل از حل زیر مسائل رو برای بدست آوردن نتیجه‌ی مسئله اصلی با هم ترکیب کنیم. به این مرحله مبنای بازگشت (Recursive Base) هم گفته می‌شه.

اما چرا گفتم که اصلاحی که انجام دادی تا حدودی درسته؟ پارامتر X که به روال فرستاده شده حاوی اسمی است که می‌خواهیم دنبالش بگردیم٬ در صورتی که پارامترهای Start و Finish عددی بوده و نشان دهنده بازه‌ای از آرایه هستند که باید جستجو در آن بازه صورت بگیرد. بنابر‌این منطقا" نمی‌توانیم X را با Start یا Finish مقایسه کنیم. جدا از اینکه نیازی هم به شروط بیشتر نیست.

function Search(X: name; Start, Finish: integer) return address
Middle: integer
begin
if Start > Finish then
return موجود نبید
else
Middle <- (Start + Finish) / 2
if X = Names(Middle) then
return Numbers(Middle)
elseif X < Names(Middle) then
return Search(X, Start, Middle - 1)
else -- X > Names(Middle)
return Search(X, Middle + 1, Finish)
endif
endif
end

با تشکر از DelphiArea جهت توجه به این بخش :)
خواهش می‌کنم٬ فقط دارم دست و پا شکسته انجام وظیفه می‌کنم.

Kambiz

جمعه 21 شهریور 1382, 01:20 صبح

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

در الگوریتم جستجوی بالا٬ ما در هربار نیمی از فهرست را که امکان وجود مورد جستجو در آن نبود، از رده خارج کردیم و جستجو را در نیمه دیگر ادامه دادیم.

حال فرض کنید که به جای دو قسمت٬ فهرست را به سه قسمت تقسیم می‌کردیم. در این صورت در هر بار فقط یک سوم از فهرست را می‌گشتیم.

و اما پرسش: آیا با افزایش تقسیمات زمان رسیدن به نتیجه کم می‌شود؟

----------------------------------------------------------------------------------------------------------

لطفا تنها خواننده مطالب نباشید و سعی کنید چیزی در پاسخ به این پرسش بنویسید. درست یا نادرست بودن جواب اصلا" مهم نیست٬ مهم درگیر شدن با مسئله و شنیدن همه نقطه نظرات هست.

phantasm

جمعه 21 شهریور 1382, 03:14 صبح

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

درخت اقتباص شده بصورت ساختار گراف با n نود در میاد یه چیزی تو مایه ها ی ایندکس.

(امید)

جمعه 21 شهریور 1382, 05:00 صبح

با سلام

فکر کنم با زیاد کردن تقسیمات تعداد دستورات IF هم بیشتر شود که در این صورت احتمالا سرعت تفاوت چندانی نخواهد کرد . ( دستور IF دستور سنگین و زمانبری می باشد ).
برای مثال در تقسیم به 3 قسمت ما 2 IF دیگر هم خواهیم داشت.یعنی در این صورت فرض کنید middle1,middle2 را داریم برای حالت اول که ببینیم x مساوی با middle1 است یا کوچکتر یا مساوی که 2 if داریم و اگر بزرگتر بود همین کار برای middle2 .

phantasm

جمعه 21 شهریور 1382, 10:21 صبح

سلام
من هم اول به این موضوع فکر کردم .البته تا حدودی درسته و این در صورتی هست که تعداد اعضای لیست کم باشه.
با لیستی با تعداد زیاد تعداد تقسیمات بیشتر که متعاقبا تعداد if بیشتری داره به صرفه تر میشه

Kambiz

شنبه 22 شهریور 1382, 07:28 صبح

قبل از ادامه دادن بحث لازم بود که توضیحی رو در خصوص مقدمات تحلیل یک الگوریتم بگم. پس قبل از خواندن ادامه صحبتم لطفا "تحلیل مقدماتی الگوریتمها (http://www.barnamenevis.org/forum/viewtopic.php?t=2909)" رو بخوانید.

در مثال جستجوی دودویی، ظاهر امر اینجور نشون می‌ده که هر چی تعداد تقسیمها بیشتر باشه٬ در هر بار تلاش ناموفق٬ ما حجم بیشتری از فهرست رو کنار می‌گذاریم.

ببینیم اگر تعداد تقسیمات رو به اندازه طول فهرست (N) برسونیم چه حاصلی در بر داره. در این حالت در اولین ورود به روال باید جستجو رو تو یکی از N قسمت انجام بدیم و اگر این قسمت٬ قسمت مورد نظرمون نبود٬ باید جستجو رو در یک قسمت دیگه دنبال کنیم. خوب با این حساب در هر بار ما فقط یک قسمت از N قسمت رو کنار می‌گذاریم در صورتیکه وقتی تعداد تقسیمات کمتر بود قسمت کنار گذاشته شده بزرگتر بود.

در حقیقت با داشتن N قسمت جستجوی دودویی ما تبدیل میشه به یک جستجوی متوالی به صورت زیر:

function Search(X: name; N: Integer) return address is
begin
for i := 1 to N loop
if Names(i) = X then
return Address(i)
endif
end

همانطور که گفتید، تعداد تقسیمات و اندازه مسئله با هم در ارتباط هستند و برای داشتن یک الگوریتم تقسیم و تسخیر بهینه باید تعداد تقسیمات مناسب رو داشته باشیم.

خوب فعلا"مثال جستجوی دودوئی رو بگذارید کنار تا با مثالی یک کم کلی‌تر رابطه بین تعداد تقسیمات و اندازه‌ی مسئله رو دنبال کنیم تا ببینیم در چه شرایطی به الگوریتم سریعتری خواهیم رسید.

پرسش:

در نظر بگیرید که الگوریتمی داریم به نام A که می‌دانیم قادر است مسئله‌ای به اندازه‌ی N را در c N^2 مرحله حل کند (c ضرب در N به توان 2 و c عددی است ثابت). بعدا" الگوریتمی پیدا می‌کنیم به نام B که همان مسئله را بصورت زیر حل می‌کند:
هر مورد از مسئله را به 3 قسمت هر یک به اندازه N / 2 تقسیم می‌کند
3 قسمت را حل می کند
نتایج حاصل را در d N مرحله ترکیب می‌کند (d ضرب در N و d عددی است ثابت)فرض کنید که الگوریتم A برای حل زیر مسائل در مرحله 2 بکار می‌رود.

با استفاده از رابطه‌ی الگوریتمهای A و B ببینید کدام الگوریتم سریعتر است. و آیا سریعتر بودن یک الگوریتم نسبت به دیگری با اندازه‌ی مسئله رابطه دارد؟

Kambiz

دوشنبه 24 شهریور 1382, 00:32 صبح

مسئله‌ای که در پرسش پست قبلیم مطرح کردم الگوریتم محاسبه‌ی حاصل ضرب دو عدد n رقمی است.

ورودیها دو عدد N رقمی مثبت می‌باشند که به صورت زیر نمایش داده می‌شوند:
http://delphiarea.com/external/karatsuba/xy.gif
و خروجی یک عدد 2N رقمی خواهد بود که به صورت زیر نمایش داده می‌شود:
http://delphiarea.com/external/karatsuba/z.gif

طبق الگوریتمی که در مدرسه ابتدایی آموخته‌ایم برای برای بدست آوردن حاصل ضرب دو عدد، تک تک ارقام یک عدد را در عدد دیگر ضرب کرده و حاصلها را با هم جمع می‌کنیم تا حاصل ضرب نهایی دو عدد را بیابیم. این الگوریتم به O(N^2) مرحله برای ضرب دو عدد N رقمی نیاز دارد.

منظور از مرحله در عبارت بالا عملیات پایه‌‌ی ریاضی است که بر روی دو رقم (عدد تک رقمی) صورت می‌گیرد. مانند 3+4 یا 5*6.

در سال 1992 فردی به نام A.A. Karatsuba الگوریتم ضرب سریعتری به روش تقسیم و تسخیر یافت که به نام او الگوریتم ضرب کاراتسوبا Karatsuba Multiplication (http://mathworld.wolfram.com/KaratsubaMultiplication.html) نامیده می‌شود. تعداد مراحل مورد نیاز این الگوریتم O(N^(log 3)) یا به عبارتی O(N^1.59) است. الگوریتم کاراتسوبا برای تمام مبناهای عددی معتبر است.

حالا ببینیم این الگوریتم بر چه اساسی بدست آمده است. اعداد ورودی x و y را در نظر بگیرید:
http://delphiarea.com/external/karatsuba/xy.gif
واضح است که این دو عدد را می‌توان بصورت زیر هم نمایش داد:
http://delphiarea.com/external/karatsuba/xysum.gif
و نتیجه حاصل ضرب z = x * y را بصورت زیر بیان کرد:
http://delphiarea.com/external/karatsuba/zsum.gif

به عنوان مثال:
http://delphiarea.com/external/karatsuba/ex3.gif

حال فرض کنید که ما ارقام اعداد x و y را به دو قسمت تقسیم کنیم:
http://delphiarea.com/external/karatsuba/abcd.gif
اکنون می‌توانیم اعداد x و y را با استفاده از اعداد a و b و c و d به صورت زیر بیان کنیم:
http://delphiarea.com/external/karatsuba/xyabcd.gif

با این نگرش به اعداد x و y حاصل ضرب آنها را می‌توانیم به صورت زیر بدست آوریم:
http://delphiarea.com/external/karatsuba/xyzabcd.gif
که در آن عبارتهای (a*c) و (a*d) و (b*c) و (b*d) حاصل ضرب دو عدد N/2 رقمی می‌باشند.

بدین ترتیب حاصل ضرب دو عدد x و y با استفاده از ترمهای a و b و c و d بدین صورت بیان می‌شود که:
دو عدد تک رقمی بی‌درنگ با هم ضرب می‌شوند. (مبنای بازگشت)
اگر N > 1 بود در اینصورت حاصل ضرب دو عدد N رقمی می‌تواند بصورت ترمهایی از 4 عمل ضرب بر روی دو عدد N/2 رقمی بیان شود. (مرحله تقسیم و تسخیر)
برای محاسبه نتیجه حاصل ضرب اعداد x و y داده شده٬ تنها نیاز به جمع 4 حاصل ضرب بدست آمده در مرحله قبل (که در O(N) مرحله صورت می‌گیرد) و ضرب کردن در توانی از 10 هست (که این هم می‌تواند در O(N) مرحله صورت بگیرد٬ زیرا که تنها نیاز است به تعداد لازم صفر در انتهای عدد قرار گیرد). (مرحله ترکیب)
به عنوان مثال اگر داشته باشیم:

n = 4
x = 1026
y = 7329
در اینصورت خواهیم داشت:

a = 10
b = 26
c = 73
d = 29
پس اعداد x و y بصورت زیر قابل نمایش خواهند بود:
http://delphiarea.com/external/karatsuba/ex1.gif
و در نتیجه حاصل ضرب x و y بصورت زیر محاسبه خواهد شد:
http://delphiarea.com/external/karatsuba/ex2.gif

کاراتسوبا فهمید که می‌توان 4 عمل ضرب موجود در مرحله‌ی تقسیم و تسخیر الگوریتم ساده‌ی بالا را به 3 عمل ضرب کاهش داد. البته کاهش یک عمل ضرب در مرحله تقسیم و تسخیر باعث افزایش جزئی تعداد عملیات پایه در مرحله ترکیب می‌شود (هرچند باز به O(N) مرحله نیاز خواهد داشت).

چگونه 4 عمل ضرب می‌تواند به 3 عمل ضرب تبدیل شود؟ یک جایگزینی ساده. :idea:

U = a * c
V = b * d
W = (a + b) * (c + d)
با استفاده از U و V و W خواهیم داشت:

a * d + b * c = W - U - V
به همین سادگی 4 عمل ضرب به 3 عمل ضرب تبدیل شد و اکنون می‌توانیم حاصل ضرب دو عدد N رقمی x و y را بصورت زیر بیان کنیم:
http://delphiarea.com/external/karatsuba/xyzabcduvw.gif

الگوریتم ضرب کاراتسوبا بطور کامل:

function Karatsuba (xunder, yunder : n-digit integer;
n : integer)
return (2n)-digit integer

a, b, c, d : (n/2)-digit integer
U, V, W : n-digit integer
begin
if n = 1 then
return x(0) * y(0)
else
a := x(n-1) ... x(n/2)
b := x(n/2-1) ... x(0)
c := y(n-1) ... y(n/2)
d := y(n/2-1) ... y(0)
U := Karatsuba ( a, c, n/2 )
V := Karatsuba ( b, d, n/2 )
W := Karatsuba ( a+b, c+d, n/2 )
return U * 10^n + (W-U-V) * 10^(n/2) + V
end if
end Karatsuba

Kambiz

چهارشنبه 26 شهریور 1382, 23:32 عصر

خوب برگردیم سر پرسش بی‌جوابی که داریم:

در نظر بگیرید که الگوریتمی داریم به نام A که می‌دانیم قادر است مسئله‌ای به اندازه‌ی N را در c N^2 مرحله حل کند (c ضرب در N به توان 2 و c عددی است ثابت). بعدا" الگوریتمی پیدا می‌کنیم به نام B که همان مسئله را بصورت زیر حل می‌کند:
هر مورد از مسئله را به 3 قسمت هر یک به اندازه N / 2 تقسیم می‌کند
3 قسمت را حل می کند
نتایج حاصل را در d N مرحله ترکیب می‌کند (d ضرب در N و d عددی است ثابت)فرض کنید که در مرحله ٬2 از الگوریتم A برای حل زیر مسائل استفاده می‌شود.

می‌خواهیم با استفاده از رابطه‌ی الگوریتمهای A و B ببینیم کدام الگوریتم سریعتر است٬ و آیا سریعتر بودن یک الگوریتم نسبت به دیگری به اندازه‌ی مسئله رابطه‌ای دارد یا نه.

با استفاده از فرضیات بالا داریم:

T(A)(n) = c * (n^2) طبق تعریف

T(B)(n) = 3 * T(A)(n/2) + d * n

= 3 * (c * (n/2)^2) + d * n

= (3/4) * (c * (n^2)) + d * n

= (3/4) * T(A)(n) + d * n
با این حساب برای اینکه زمان اجرای B زمان اجرای A کمتر باشد، باید شرط زیر برقرار باشد:

d * n < (1/4) * T(A)(n)
که با جایگزینی زمان اجرای A در شرط بالا خواهیم داشت:

d * n < (1/4) * (c * (n^2))

d < (c * n) / 4

یا به عبارتی

n > (4 * d) / c

پس برای مقادیری از N (اندازه مسئله) که N از 4d/c (که عددی است ثابت) بزرگتر است٬ الگوریتم B از الگوریتم A سریعتر خواهد بود.

با توجه به رابطه‌ی الگوریتم A و B براساس فقط مقدار ثابت 4d/c ٬ می‌توانیم بگوییم که اگر اندازه‌‌ی مسئله (N) به اندازه‌ی بزرگ بود که داشته باشیم:

n > 4d/c
n/2 > 4d/c
n/4 > 4d/c

. . .

n/i^2 > 4d/c
پیشنهاد می‌شود که از الگوریتم B بجای الگوریتم A استفاده شود و با تکرار الگوریتم B در این مرحله، هر زیر مسئله را به زیر مسائل کوچکتر تقسیم کرده و هرگاه اندازه‌ی زیر مسئله‌ای به مقدار N0 که مساوی یا کوچکتر از 4d/c است رسید٬ ادامه حل آن را با الگوریتم A دنبال کنیم.

Kambiz

جمعه 28 شهریور 1382, 00:16 صبح

شکل کامل یک الگوریتم تقسیم و تسخیر به صورت زیر نوشته می‌شود:
اندازه‌ی مسئله (N)
مقدار بحرانی اندازه‌ی مسئله که برای کمتر از آن تقسیمی صورت نمی‌گیرد. مقدار بحرانی را مقدار مبنا یا مبنای بازگشت هم میگویند. (N0)
اندازه هر زیرمسئله که از تقسیم مسئلهی اصلی حاصل شده است. معمول این است که این اندازه بصورت نسبتی از اندازه‌ی‌ مسئله‌ اصلی به اندازه‌ی زیرمسائل بیان شود. (M)
تعداد تقسیمات مسئله‌ی اصلی به زیرمسائل. (R)

procedure D-and-C (N : input size)
begin
if N <= N0 then
Solve problem without further sub-division
else
Split into R sub-instances each of size N/M
for each of the R sub-instances do
D-and-C (N/M)
end for
Combine the R resulting sub-solutions
to produce the solution to the original problem
end if
end D-and-C
همانگونه که دیده شد در محاسبه زمان اجرای الگوریتمهای تقسیم و تسخیر سه عامل نقش تعیین کننده دارند:
تعداد زیرمسائلی که یک مسئله به آنها تقسیم شده تا بطور مجزا حل شوند. (a)
نسبت اندازه‌ی مسئله اصلی به اندازه زیرمسائل. (b)
تعداد مراحل مورد نیاز برای تقسیم مسئله اصلی و ترکیب نتایج حاصل از حل هر یک از زیرمسائل٬ که بصورت تابعی از n بیان شدنی است.
از آنجا که جواب مسئله اصلی از ترکیب جوابهای مسائل کوچکتر حاصل می‌شود و زمان اجرای این فرآیند به نوع مسئله مربوط است، زمان اجرا را بصورت یک چند جمله‌ای بصورت O(n^k) فرض می‌کنیم که در آن k مقداری بزرگتر یا مساوی صفر دارد. با این فرض و همچنین در حالتی که a و b هر دو ثابت باشند (همانند مثالهایی که در بالا داشتیم)، می‌توان زمان اجرای یک الگوریتم تقسیم و تسخیر را بصورت زیر بیان کرد:

O(1) n <= n0
T(n) =
a . T(n/b) + O(n^k) n > n0
با حل معادله بالا، زمان اجرای الگوریتم با تقریبی اندک (asymptotically) توسط فرمول زیر قابل محاسبه خواهد بود (*):

O(n^k) if a < b^k

T(n) = O((n^k).(log[b]n)) if a = b^k

O(n^(log[b]a))) if a > b^k

اگر به چگونگی رسیدن به فرمول بالا علاقمندید، جزئیات آن در Running Time of Divide-and-Conquer Algorithms (http://www.brpreiss.com/books/opus5/html/page452.html) بیان شده است.

------------------
* عبارت log[x]y به معنی لگاریتم y در مبنای x است.

borna66

یک شنبه 23 اردیبهشت 1386, 23:38 عصر

Kambiz عالی بود
خیلی ممنون از زحمتتان

nicolas_vires

دوشنبه 13 مهر 1388, 00:45 صبح

با سلام
مي‌دانيد كه الگوريتم فيبوناچي يك الگوريتم تقسيم و حل محسوب مي‌شود و پيچدگي آن 2 به توان n/2 مي‌باشد خيلي سعي كردم با روش‌هايي به اين پيچيدگي برسم اما به بن بست رسيدم لطفا بدون استفاده از روش استقراء اين كار را برايم انجام دهيد.
با تشكر

fp660@yahoo.com

جمعه 26 مهر 1392, 20:34 عصر

سلام من سه تا سوال دارم اگه کسی جواب شو میدونه لطف کنه بگه عجله دارم
1-چرا در جستجوی باینری آرایه رو به دو قسمت تقسیم میکنه در هر مرحله.چرا به سه قسمت تقسیم نمیکنه؟؟
2-چرا جستجوی باینری روی لیست نیمه مرتب هم جواب می دهد؟؟
3-چرا برای به دست آوردن خانه وسط آرایه وقتی شماره خانه ابتدا و انتها جمع میشود و بر 2 تقسیم میشود حد بالای عدد به دست آمده را در نظر گرفته و خانه وسط را پیدا میکنیم مثلا آرایه 5 عنصری
2.5= 2/(1+5)
و خانه 3 میشود خانه وسط چرا حد پایین را نمیگیریم یعنی 2 ؟؟؟

FastCode

پنج شنبه 02 آبان 1392, 19:27 عصر

1.برای اینکه دیگه اسمش باینری نمیشه.برای ۳ قسمت جست و جو کنید ternary search
2.جواب نمیده.
۳.چون اونطوری خانه وسط از قلم میافته.