תרגיל במדעי המחשב, הצילו

[miaoo673]

פונקציית אקרמן מוגדרת רקורסיבית באופן הבא:

A(m,n) = n+1 if m=0

A(m-1,1) if m>0 and n=0

A(m-1,A(m,n-1)) if m>0 and n>0

צריך למצוא את סיבוכיות הזמן והזכרון של הפונקציה עבור m=0,1,2,3 (כתלות ב-n)

אין לי מושג איך לפתור את 2 ו-3. בבקשה תעזרו לי.

[Yehudaa]

תכתוב את הקוד באופן מסודר ותשים אותו ב #

[miaoo673]

נכתב ב-scheme:

(cond ((= m 0) (+ n 1))
((and (> m 0) (= n 0)) (ackerman (- m 1) 1))
((and (> m 0) (> n 0)) (ackerman (- m 1) (ackerman m (- n 1))))
)
)

(define (ackerman m n)

[BiG_BuG]

מצטרף לשאלה .. :

[yousux]

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

http://hwzone.co.il/community/index.php?board=27.0

[miaoo673]

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

[Zelig]

פוקנציית אקרמן גודלת מאוד מהר. מאוד מהר.

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

עריכה: ציטוט שמצאתי בויקיפדיה:

If we define the function f (n) = A(n, n), which increases both m and n at the same time, we have a function of one variable that dwarfs every primitive recursive function, including very fast-growing functions such as the exponential function, the factorial function, multi- and superfactorial functions, and even functions defined using Knuth's up-arrow notation (except when the indexed up-arrow is used).

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

[yousux]

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

[BiG_BuG]

Zelig, תודה! :]