امثلة عملية

المحاضرة الثانية

مثال3/ اعداد فيبوناتشي ( Fibonacci numbers).
متتابعة فيبوناتشي للاعداد تبدأ كالاتي:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ….
حيث ان كل حد جديد يتم الحصول عليه من خلال جمع الحدين السابقين، فاذا كان F0 يمثل الحد الاول في المتتابعة فان F0=0 و F1=1 و بصورة عامة:

Fn = Fn - 1 + Fn - 2 , n?2

Algorithm fibonacci (n):
Input: a nonnegative integer n.
Output: fib, the nth term of the fibonacci sequence.
1. if n ? 1 then
2. fib n
3. else
4. fnm1 0
5. fnm2 1
6. for i 2 to n
7. fib fnm1 + fnm2
8. fnm1 fnm2
9. fnm2 fib
10. end for
11. end if
12. return fib

يتصف مثال المسألة بـ n
تعقيدات الخزن:- تتطلب هذه الخوارزمية اربع خلايا خزنية لخزن قيم fib و fnm1 و fnm2 و i وهو خزن ثابت لا يعتمد على خصائص المثال.

Sfibonacci(n)= 0


تعقيدات الوقت باستخدام عد الخطوات:- يجب اعتبار حالتين في هذه الطريقة:

الحالة الاولى :- عندما n=0 او n=1 فان عدد الخطوات يساوي 3.
الحالة الثانية :- عندما n>1 فان عدد الخطوات يساوي 4n+1.









مثال4/ مسألة حساب المتوسطات السابقة (Prefix averages) لمجموعة من الاعداد.
مفهوم المسألة:- اذا كان لدينا مصفوفة معينة X مخصصة لخزن n من الاعداد الصحيحة، فالمطلوب في مسألة المتوسطات السابقة حساب مصفوفة اخرى ولتكن A بحيث ان العنصر A[i] يمثل متوسط قيم العناصر من X[1] الى X[i] لقيم i من 1 الى n وهذا يعني


الخوارزمية التالية تقوم بحل هذه المسألة:

Algorithm prefixAverages(X):
Input: An n-element array X of numbers.
Output: An n-element array of numbers A such that
A[i] is the average of elements
X[1],…,X[i].
1. for i 1 to n
2. a 0
3. for j 1 to i
4. a a + X[j]
5. end for
6. A[i] a /i
7. end for
8. return array A

يتصف مثال المسألة بـ n

تعقيدات الوقت باستخدام عد الخطوات:
1. ……. n+1
2. ……. n
3. …….
4. …….
6. ……. n
8. ……. n

TprefixAverages(n)= n2 + 6n +1

واجب/ اعد صياغة الخوارزمية prefixAverages لتصبح تعقيداتها خطية وليست تربيعية.