רוטר - עזרה בבקשה + חידה קטנה ברקורסיה

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"עזרה בבקשה + חידה קטנה ברקורסיה"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #7429	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 7429

shklar1

19:42 26.11.03

עזרה בבקשה + חידה קטנה ברקורסיה

היי אנשים...
המורה שלנו הביא לנו רקורסיה מסויימת, וביקש לדעת מה היא עושה..
יש לי כיוון מסויים, אני חושב שכל פעם הערך מקבל את ערך ההליך של שני
המספרים הקודמים שלו.. אבל אין לי מושג מה זה אומר..
הוא רמז לנו שזה גם קשור קצת במוסיקה... אם מישהו יודע אני אשמח גם לדעת

Function yos(N:Integer):Integer;
Begin
If (n=1) or (n=2) then
yos:=n
Else
yos:=yos(n-yos(n-1)) + yos(n-yos(n-2));
End;

תודה מראש

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
מקפיץ בבקשה...	shklar1	28.11.03 00:00	1
אז ככה	yoash	28.11.03 13:22	2
הפונקציה הזאת היא ממש לא פיבונאצ'י	dryice	28.11.03 16:29	3
?	katorza	28.11.03 16:40	4
מימוש בC עם אופטימזציות מהירות:	dryice	28.11.03 18:34	5
ושיפור קל, אתחול אלגנטי יותר:	dryice	28.11.03 18:36	6

shklar1

00:00 28.11.03

1. מקפיץ בבקשה...
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

yoash

13:22 28.11.03

2. אז ככה
בתגובה להודעה מספר 1

הפונקציה שלנו מחשבת את סדרת פיבונאצי.
זואי סדרה מיוחדת מאוד, אפשר למצוא אותה בטבע.
בסדרה זו כל איבר הוא סכום שני האיברים שלפניו.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

16:29 28.11.03

3. הפונקציה הזאת היא ממש לא פיבונאצ'י
בתגובה להודעה מספר 2

אני לא מצליח למצוא שום הגיון בסדרת המספרים שהיא מגדירה,
תכונות של הפונקציה:
מוגדרת לכל n שלם חיובי.
חיובית לכל n.
לא מונטונית.
קצב הגידול של yos הוא ככל הנראה לינארי בN (אסימפטוטית)
מאוד קרוב ל0.5n
טרם מצאתי חסם לינארי, זה צריך להיות אפשרי.
אני לא מצליח למצוא פה שום הגיון בעל משמעות.
DRYICE

נ.ב
בעזרת תכנות דינאמי טריוויאלי ניתן לחשב הפונקציה ביעילות.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

katorza

16:40 28.11.03

4. ?
בתגובה להודעה מספר 3

מונטונית
אסימפטוטית
טריוויאלי
חח אני לא מבין מה זה אומר

אם זה היה מתורגם ל C הייתי מנסה לעזור.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

18:34 28.11.03

5. מימוש בC עם אופטימזציות מהירות:
בתגובה להודעה מספר 4

להלן תוכנית C אשר ממשת את הפונקציה, ומחשבת אותה
עבור המספרים 1 עד MAX אשר עברה אופטימזיציות בשביל
שזמן החישוב יהיה O(N) במקרה הגרוע ביותר, ובפועל כאשר
קוראים לפונקציה לפי הסדר אז החישוב הוא O(1)

#include <stdio.h>
#define MAX 10000
int vals[MAX];
int yos(int n) {
if (vals[n]) return vals[n];
return (vals[n]=(yos(n-yos(n-1)) + yos(n-yos(n-2))));
}
int main() {
int i;
memset(vals,0,sizeof(vals));
vals[1]=1;
vals[2]=2;
for (i=1;i<MAX;++i) {
printf("%d: %d\n",yos(i),i);
}
return 0;
}

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

18:36 28.11.03

6. ושיפור קל, אתחול אלגנטי יותר:
בתגובה להודעה מספר 5

int vals[MAX]={0,1,2,0}
ואז אין צורך באתחול מתוך main.

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד