Printable View
با سلام
من نیاز به الگوریتم باینری سرچ و فیبوناچی سرچ دارم
لطفا اگر کد می ذارید C باشه
لطفا توضیح کامل الگوریتم ها رو هم بدین
به علاوه ی بررسی پیچیدگی زمانی یا time complexity یا big Oh این الگوریتم ها که در درس یاختمان داده ها بررسی میشه
دوستان هر قسمتش هم که باشه غنیمته
ممنون
سرچ باینری چون روی یه لیست مرتب شده انجام میشه و در هر دفعه فضای جستجو رو نصف می کنه، در نتیجه پیچیدگی زمانیش O(lgn) هست.
اینجوری که مثلاً برای یه آرایه i تا j اگه عنصر s برابر [ x[(i+j)*2 بود که جستجو تمومه. اگه s بزرگتر بود باید سمت چپ رو بگردیم. اگه s کوچکتر بود باید سمت راست رو بگردیم . (مثل جستجو توی یه دیکشنری).
شبه کدش به صورت زیر هست. تبدیلش به کد سی کاری نداره.
کد:BinarySearch(A[0..N-1], value, low, high) {
if (high < low)
return -1 // not found
mid = (low + high) / 2
if (A[mid] > value)
return BinarySearch(A, value, low, mid-1)
else if (A[mid] < value)
return BinarySearch(A, value, mid+1, high)
else
return mid // found
}
این رو ببین:
کد:http://www.ics.forth.gr/~lourakis/fibsrch/
کد:*
* If val is found in arr, return the index of its location in arr.
* Otherwise, return the index of the smallest element greater than val
*/
static int binsrch_geq(const int *arr, int n, int val)
{
register int low, high, mid;
int geq;
low=0; high=n-1; geq=-1;
/* binary search for finding the element with value val */
while(low<=high){
mid=(low+high)>>1; //(low+high)/2;
if(val<arr[mid]){
high=mid-1;
geq=mid;
}
else if(val>arr[mid])
low=mid+1;
else
return mid; /* found */
}
return geq; /* not found */
}
/*
Fibonaccian search for locating the index of "val" in an array "arr" of size "n"
that is sorted in ascending order. See http://doi.acm.org/10.1145/367487.367496
Algorithm description
-----------------------------------------------------------------------------
Let Fk represent the k-th Fibonacci number where Fk+2=Fk+1 + Fk for k>=0 and
F0 = 0, F1 = 1. To test whether an item is in a list of n = Fm ordered numbers,
proceed as follows:
a) Set k = m.
b) If k = 0, finish - no match.
c) Test item against entry in position Fk-1.
d) If match, finish.
e) If item is less than entry Fk-1, discard entries from positions Fk-1 + 1 to n.
Set k = k - 1 and go to b).
f) If item is greater than entry Fk-1, discard entries from positions 1 to Fk-1.
Renumber remaining entries from 1 to Fk-2, set k = k - 2 and go to b)
If Fm>n then the original array is augmented with Fm-n numbers larger
than val and the above algorithm is applied.
*/
int fibsrch(const int *arr, int n, int val)
{
register int k, idx, offs;
static int prevn=-1, prevk=-1;
/* Precomputed Fibonacci numbers F0 up to F46. This implementation assumes that the size n
* of the input array fits in 4 bytes. Note that F46=1836311903 is the largest Fibonacci
* number that is less or equal to the 4-byte INT_MAX (=2147483647). The next Fibonacci
* number, i.e. F47, is 2971215073 and is larger than INT_MAX, implying that it does not
* fit in a 4 byte integer. Note also that the last array element is INT_MAX rather than
* F47. This ensures correct operation for n>F46.
*/
const static int Fib[47+1]={0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578,
5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296,
433494437, 701408733, 1134903170, 1836311903, INT_MAX};
/* find the smallest fibonacci number that is greater or equal to n. Store this
* number to avoid recomputing it in the case of repetitive searches with identical n.
*/
if(n!=prevn){
#if 1
k=(n>1)? binsrch_geq(Fib, sizeof(Fib)/sizeof(int), n) : 1;
#else /* the above binary search call can be substituted by the following code fragment: */
{
register int f0, f1, t;
for(f0=0, f1=1, k=1; f1<n; t=f1, f1+=f0, f0=t, ++k)
;
}
#endif
prevk=k;
prevn=n;
}
else k=prevk;
/* If the sought value is larger than the largest Fibonacci number less than n,
* care must be taken top ensure that we do not attempt to read beyond the end
* of the array. If we do need to do this, we pretend that the array is padded
* with elements larger than the sought value.
*/
for(offs=0; k>0; ){
idx=offs+Fib[--k];
/* note that at this point k has already been decremented once */
if(idx>=n || val<arr[idx]) // index out of bounds or val in 1st part
continue;
else if (val>arr[idx]){ // val in 2nd part
offs=idx;
--k;
}
else // val==arr[idx], found
return idx;
}
return -1; // not found
}
#if 0
/* Sample driver program for fibsrch() */
main()
{
int data[]={1, 4, 5, 7, 9, 11, 13, 16, 18, 20, 25, 27, 30, 32, 33, 36, 39, 41, 44, 47, 51, 53, 55};
int i, x, n;
x=30; n=sizeof(data)/sizeof(int);
i=fibsrch(data, n, x);
if(i>=0)
printf("%d found at index %d\n", x, i);
else
printf("%d was not found\n", x);
}
#endif
کد:The Algorithm
Let Fk represent the k-th Fibonacci number where Fk+2=Fk+1 + Fk for k>=0 and F0 = 0, F1 = 1. To test whether an item is in a list of n = Fm ordered numbers, proceed as follows:If n is not a Fibonacci number, then let Fm be the smallest such number >n, augment the original array with Fm-n numbers larger than the sought item and apply the above algorithm for n'=Fm.
- Set k = m.
- If k = 0, finish - no match.
- Test item against entry in position Fk-1.
- If match, finish.
- If item is less than entry Fk-1, discard entries from positions Fk-1 + 1 to n. Set k = k - 1 and go to 2.
- If item is greater than entry Fk-1, discard entries from positions 1 to Fk-1. Renumber remaining entries from 1 to Fk-2, set k = k - 2 and go to 2.
A C implementation of the Fibonaccian search algorithm is shown below. You can scroll through it while keeping the above pseudocode visible.
---------------------------------------------------------------
خب تا اینجا فیبوناچی بود حالا باینری:
اول این رو ببین:
کد:http://en.wikipedia.org/wiki/Binary_search
تو لینکایی که واست گذاشتم کد به اکثر زبانهای رایج برنامه نویسی هستکد:low = 0
high = N
while (low < high) {
mid = (low + high)/2;
if (A[mid] < value)
low = mid + 1;
else
//can't be high = mid-1: here A[mid] >= value,
//so high can't be < mid if A[mid] == value
high = mid;
}
// high == low, using high or low depends on taste
if ((low < N) && (A[low] == value))
return low // found
else
return -1 // not found
ممنون از همه ی دوستان
واقعا لطف کردید
اگر براتون ممکنه می تونینین همینارو به خصوص فیبوناچی رو مرحله به مرحله به فارسی بگین که چی کار می کنه؟
خیلی ممنون از کمکتون واقعا لطف کردین
اگر ممکنه سرچ فیبوناچی رو به صورت فارسی مرحله مرحله توضیح بدین که من بفهمم چی به چیه خیلی ممنون میشم
دوست من بگو کدومشون به دردت خوره همون رو ترجمه کنم:20:نقل قول:
خیلی ممنون از لطفتون
من کلا نحوه ی سرچ فیبوناچی رو متوجه نشدم که چی کار می کنه
دوستان لطفا سریع تر جواب بدین من وقت ندارم :(
الگوریتمش رو اینجا کاربر فاطمه گفته:نقل قول:
اگه یه کم با دقت مطالعش کنید متوجه میشیه. الگوریمش شبیه الگوریتم جستجوی باینری هست (اون که خیلی ساده هست و امیدوارم بدونین چه جوریه). با این تفاوت که به جای اینکه از وسط آرایه رو نصف کنه از اعداد فیبوناتچی برای این کار استفاده می کنه. از مرتبه log n هست. همون طور که در الگوریتم بالا می بینید تا مرحله چهار چک می کنه که آیا این عنصر برابر عنصر مورد نظر یا خیر. اگه نباشه می ره به قدم 5. در ایون جا هم بر حسب اینکه از اون عدد کوچیکتره یا بزرگتر تصمیم می گیره که یه قسمت از آرایه رو دیگه جستجو نکنه (مثل جستجوی باینری).نقل قول:
نوشته شده توسط فاطمه
بله شبیه ولی نحوه ی کارش خیلی برام مفهوم نیست!
اگر ممکنه با 1 مثال مرحله به مرحله توضیح بدین
دوستان لطفا کمک کنید امروز آخرین فرصته
:20:التماس می کنم کمک کنید
کمککککککککککککککککککک
اگر لطف کنید الگوریتمشو ترجمه کنید هم کافیه
mishe baynary serch ra tozih bedin .mamnon