طلب مساعده في Fibonacci Algorithim

والله ما عندي فكرة fibonacci numbers لاني نسيتها تماماً :(

لكن لو كنت مكانك اول شيء بأعمله هو الدخول على موقع wikipedia والقراءة عن هذا الموضوع حتى اجد طريقة حساب عدد elements

السلام عليكم

الفايبونشي هي متسلسلة مشهورة في الرياضيات

تقوم على جمع العدد الذي تريده مع العدد الذي قبله

مثال اذا كانت السلسلة : 01

الحل:

0+1=1

اذا كانت السلسة 012

انت تريد الجواب ل 2

2+1=3

اذا كانت : 0123

انت تريد ل 3

3+2=5

and so on

أرجو أن أكون قد أفتدك

مجلـد جديـد

يسلموا ايديك على المساعده,,

حاولت ادور بال wikipedia بس مع الاسف ما استفدت :S

سامي راتب

اخوي سامي,,

يمكن انت ما فهمتي سؤالي مزبوط

الخلاصة

ما هي العلاقة Explicit formula المستخدمة في المتسلسه التاليه:

1,3,5,9,19,.....

شكرا الك على المساعدة

بسم الله الرحمن الرحيم

لنلاحظ الشكل التالي

يمكننا أن نجد بسهولة أن الحد العام للمتسلسلة هو :

Elem(n) = Elem(n-1) + Elem(n-2) + 1

أي أن عدد العناصر في المرحلة n هو مجموع عدد العناصر في المرحلتين n-1 و n-2 زائد واحد (العنصر الأب)

الآن :

الجدول التالي يبين لنا عدد Fibonacci و عدد العناصر Elem لمجموعة من الأعداد

يمكننا ببساطة ملاحظة أن عدد العناصر في المرحلة n يساوي ضعف عدد Fibonacci في المرحلة n+1 منقوصاً واحد

تخبرنا wikipedia في الصفحة :

http://en.wikipedia.org/wiki/Fibonacci_number

أن الصيغة الصريحة لعدد Fibonacci هي :

حيث phi هي النسبة الذهبية (http://en.wikipedia.org/wiki/Golden_ratio) و تساوي :

بإجراء التعويضات المناسبة نجد :

و بالتالي :

هذا و الله أعلم

هذا برنامج بلغة الجافا يحوي ثلاث توابع :

1 التابع fib لحساب عدد Fibonacci بالصيغة الصريحة

2 التابع elem لحساب عدد العناصر بالصيغة العودية

3 التابع elem2 لحساب عدد العناصر بالصيغة الصريحة التي قمنا باستنتاجها

عند تنفيذ البرنامج يقوم بحساب هذه التوابع الثلاثة للأعداد من 1 إلى 15

يمكننا ملاحظة تتطابق نتائج الحساب للتابعين الثاني و الثالث

public class Fib {

	static double phi = (1 + Math.sqrt(5))/2;

	public static void main(String[] args) {
		System.out.println("n\tfib(n)\telem(n)\telem2(n)");
		System.out.println("---\t------\t------\t------");
		for (int i = 1; i <= 15; i++) {
			System.out.println(i+"\t"+fib(i)+"\t"+elem(i)+"\t"+elem2(i));
		}
	}

	public static int fib(int n){
		double phiN = Math.pow(phi, n);
		double phi1_N = Math.pow(1-phi, n);
		double fib = (phiN - phi1_N)/Math.sqrt(5);
		return (int) Math.round(fib);
	}

	public static int elem(int n){
		if(n<0){
			return 0;
		} else if(n==0){
			return 1;
		}else if(n==1){
			return 1;
		}else{
			return elem(n-1)+elem(n-2)+1;
		}		
	}

	public static int elem2(int n){
		double phiN1 = Math.pow(phi, n+1);
		double phi1_N1 = Math.pow(1-phi, n+1);
		double elem = 2*(phiN1 - phi1_N1)/Math.sqrt(5) - 1;
		return (int) Math.round(elem);
	}	
}

النتيجة ستكون بالشكل التالي :

n fib(n) elem(n) elem2(n)
--- ------ ------ ------
1   1	  1	  1
2   1	  3	  3
3   2	  5	  5
4   3	  9	  9
5   5	  15	 15
6   8	  25	 25
7   13	 41	 41
8   21	 67	 67
9   34	 109	109
10  55	 177	177
11  89	 287	287
12  144	465	465
13  233	753	753
14  377	1219   1219
15  610	1973   1973

اقترح نقل الموضوع إلى منتدى الرياضيات و الخوارزميات ..

ما شالله عليك استاذ ابو خالد

كفيت ووفيت,,اتعبتك معاي بالشرح

جربت المعادلة اللي اعطيتني اياها وهي صحيحة 100%

بس عندي ملاحظة واحدة بالنسبه للبرنامج

انه الفنكشون elem2 ببطل يعمل بعد Fib 74

عندك فكره عن السبب؟

انا محتاج اجد عدد ال Elemnts في Fib 100

السبب هو نمط البيانات المستخدم و هو int و الذي حده الأعلى هو

2,147,483,647

يمكننا تغييره إلى long و الذي حده الأعلى هو

9,223,372,036,854,775,807

و لكن حتى هنا لا يمكننا الوصول للمرحلة 90 و التي عندها عدد العناصر أكبر من هذا الحد

و لا أعرف إن كان هناك نمط بيانات في الجافا يسمح بأرقام أكثر من long

على كل حال باستخدام الحاسبة العادية في windows نجد أن عدد العناصر عند المرحلة 100 هو :

1,146,295,688,027,634,168,201

أبو خالد السوري كتب:

السبب هو نمط البيانات المستخدم و هو int و الذي حده الأعلى هو

2,147,483,647

يمكننا تغييره إلى long و الذي حده الأعلى هو

9,223,372,036,854,775,807

و لكن حتى هنا لا يمكننا الوصول للمرحلة 90 و التي عندها عدد العناصر أكبر من هذا الحد

و لا أعرف إن كان هناك نمط بيانات في الجافا يسمح بأرقام أكثر من long

على كل حال باستخدام الحاسبة العادية في windows نجد أن عدد العناصر عند المرحلة 100 هو :

1,146,295,688,027,634,168,201

يسلموا ايديك

ما قصرت.

الأمانة العلمية تقتضي أن لا نقبل قضية رياضية بدون أن نبرهن صحتها ..

في المناقشة السابقة اعتمدنا على القضية

و التي استنتجناها من مراقبة مجموعة من القيم ..

رياضياً , المراقبة لا تكفي , و لا بد من برهان القضية لكي نؤمن بصحتها ..

فيما يلي سنبرهن القضية

بالاعتماد على تعريف الدالة Elem و هو :

و على تعريف دالة Fibonacci و هو :

سنستخدم في البرهان مبدأ الاستقراء الرياضي القوي (أو الكامل) (Complete induction)

http://en.wikipedia.org/wiki/Mathematical_...plete_induction

اقتباس

تذكرة :

الاستقراء الرياضي : هو طريقة في البرهان الرياضي تستخدم لإثبات أن قضية ما محققة من أجل جميع الأعداد الطبيعية ,

و ذلك من خلال إثبات القضية عند قيمة ابتدائية و من ثم إثبات أنه إذا كانت القضية محققة عند قيمة ما n فإنها تكون محققة عند القيمة n+1 .

الاستقراء الرياضي القوي : هو تعميم للاستقراء الرياضي حيث أنه بدلاً من افتراض أن القضية محققة عند n فإننا نفرض أنها محققة عند كل القيم الأصغر أو تساوي n

1) إثبات القضية عند قيمة ابتدائية :

2) نفرض أن القضية محققة من أجل جميع القيم الأصغر أو تساوي n

ما يهمنا منها هو القيمتين n و n-1 أي سنفرض أن :

3) سنبرهن بالاعتماد على فرضيات الخطوة 2 أن القضية محققة من أجل n+1

أي سنثبت أن

لنبدأ :

و هو المطلوب