کسی میدونه با استفاده از روش binary search چطوری میشه عددی مانند x رو در یک ماتریس n*n پیدا کرد که سطر و ستوناش مرتباً و هزینه اش هم از n^2 کمتر باشه؟؟؟
اگه کسی میدونه ممنون میشم کمک کنه:لبخندساده:
Printable View
کسی میدونه با استفاده از روش binary search چطوری میشه عددی مانند x رو در یک ماتریس n*n پیدا کرد که سطر و ستوناش مرتباً و هزینه اش هم از n^2 کمتر باشه؟؟؟
اگه کسی میدونه ممنون میشم کمک کنه:لبخندساده:
یه نمونه از ماتریس مورد نظرتون رو بذارین
به کل ماتریس ها باید جواب بدهنقل قول:
نوشته شده توسط Afshin_Zavar
5 4 3 2 1
14 13 12 11
21 20 19 18
25 24 23 22n*n باشه و سطر و ستوناش به صورت صعودی مرتب شده باشه از روش "divide & conquer"
نمیشه یه نفر جواب سوال منو بده؟؟؟
اینقد سوالم سخته؟؟؟:گریه::ناراحت:
برای پیدا کردن یه عنصر، اون رو به اولین و آخرین عنصر هر سطر مقایسه کنین تا بدونین در کدام طر دنبلش بگردین. اما اینکه قطعا 2^n میشه یا نه... نمیدونم.
مطابق با الگوریتم جستجوی دودوئی برای آرایه خطی عمل کن با این تفاوت که :
Left := 0 ;
Right := n*n-1 ;
while(right>left) do
begin
middle := [(right+left) / 2];
row :=[middle / n];
column := middle mod n;
if(matrix[row][column]==item) then item found;
else if (matrix[row][column]<item) then left=middle;
else if (matrix[row][column]>item) then right=middle;
end while;
زمان مصرفی این الگوریتم (Ө(logn هست.