تابع آكرمان(5و5)

[ahmad_moin]

سلام, همگي خسته نباشيد. كسي تو اين تالار با عزمت هست كه بتونه تابع غير بازگشتي آكرمان (5و5) رو براي من بنويسه. من هر چي سعي كردم نشده. تو رو خدا در اسرع وقت كمكم كنيد. تو رو خدا فقط تيكه نندازيد. سپاسگذارم.
(ببخشبد من برنامه ای به زبان سی می خوام که بتونه این تابع رو برام حل کنه و جوابشو به من بده!)

[whitehat]

تعریف تابع آکرومان:


A(M,N)= N+1 ; if M=0
A(M,N)=A(M-1,1) ; if M>0 and N=0
A(M,N)=A(M-1,A(M,N-1)) ; if M>0 and N>0


f(5,5)=f(4,f(5,4))
f(5,4)=f(4,f(5,3))
f(5,3)=f(4,f(5,2))
f(5,2)=f(4,f(5,1))
f(5,1)=f(4,f(5,0))
f(5,0)=f(4,1)
f(4,1)=f(3,f(4,0))
f(4,0)=f(3,1)
f(3,1)=f(2,f(3,0)
f(3,0)=f(2,1)
f(2,1)=f(1,f(2,0))
f(2,0)=f(1,1)
f(1,1)=f(0,f(1,0))
f(1,0)=f(0,1)
f(0,1)=2
........................
f(1,0)=2
f(1,1)=f(0,2)=3
f(2,0)=3
........................
f(2,1)=f(1,3))
f(1,3)=f(0,f(1,2))
f(1,2)=f(0,f(1,1)=f(0,3)
-->f(1,2)=4
f(0,3)=4
f(1,3)=f(0,4)=5
f(2,1)=5
f(3,0)=5
.......................
f(3,1)=f(2,f(3,0)=f(2,5)
f(2,5)=f(1,f(2,4)
f(2,4)=f(1,f(2,3))
f(2,3)=f(1,f(2,2))
f(2,2)=f(1,f(2,1))
f(2,2)=f(1,5)
f(1,5)=f(0,f(1,4)
f(1,4)=f(0,f(1,3)=f(0,5)=6
f(1,4)=6
f(1,5)=7
f(2,2)=7
f(2,3)=f(1,7)
f(1,7)=f(0,f(1,6))
f(1,6)=f(0,f(1,5)=f(0,7)
f(1,6)=8
f(1,7)=f(0,8)=9
f(2,3)=9
f(2,4)=f(1,9)
f(1,9)=f(0,f(1,8)
f(1,8)=f(0,f(1,7)=f(0,9)
f(1,8)=10
f(1,9)=f(0,10)=11
f(2,4)=11
f(2,5)=f(1,11)
f(1,11)=f(0,f(1,10))
f(1,10)=f(0,f(1,9))=f(0,11)=12
f(1,11)=13
f(2,5)=13
f(3,1)=13
.......................
f(4,0)=13
f(4,1)=f(3,13)=f(2,f(3,12))

تا سه مرحله براتون حل کردم ، بقیه را به همین صورت حل کنید و در صورت لزوم سوال کنید

[ahmad_moin]

تعریف تابع آکرومان:


A(M,N)= N+1 ; if M=0
A(M,N)=A(M-1,1) ; if M>0 and N=0
A(M,N)=A(M-1,A(M,N-1)) ; if M>0 and N>0


f(5,5)=f(4,f(5,4))
f(5,4)=f(4,f(5,3))
f(5,3)=f(4,f(5,2))
f(5,2)=f(4,f(5,1))
f(5,1)=f(4,f(5,0))
f(5,0)=f(4,1)
f(4,1)=f(3,f(4,0))
f(4,0)=f(3,1)
f(3,1)=f(2,f(3,0)
f(3,0)=f(2,1)
f(2,1)=f(1,f(2,0))
f(2,0)=f(1,1)
f(1,1)=f(0,f(1,0))
f(1,0)=f(0,1)
f(0,1)=2
........................
f(1,0)=2
f(1,1)=f(0,2)=3
f(2,0)=3
........................
f(2,1)=f(1,3))
f(1,3)=f(0,f(1,2))
f(1,2)=f(0,f(1,1)=f(0,3)
-->f(1,2)=4
f(0,3)=4
f(1,3)=f(0,4)=5
f(2,1)=5
f(3,0)=5
.......................
f(3,1)=f(2,f(3,0)=f(2,5)
f(2,5)=f(1,f(2,4)
f(2,4)=f(1,f(2,3))
f(2,3)=f(1,f(2,2))
f(2,2)=f(1,f(2,1))
f(2,2)=f(1,5)
f(1,5)=f(0,f(1,4)
f(1,4)=f(0,f(1,3)=f(0,5)=6
f(1,4)=6
f(1,5)=7
f(2,2)=7
f(2,3)=f(1,7)
f(1,7)=f(0,f(1,6))
f(1,6)=f(0,f(1,5)=f(0,7)
f(1,6)=8
f(1,7)=f(0,8)=9
f(2,3)=9
f(2,4)=f(1,9)
f(1,9)=f(0,f(1,8)
f(1,8)=f(0,f(1,7)=f(0,9)
f(1,8)=10
f(1,9)=f(0,10)=11
f(2,4)=11
f(2,5)=f(1,11)
f(1,11)=f(0,f(1,10))
f(1,10)=f(0,f(1,9))=f(0,11)=12
f(1,11)=13
f(2,5)=13
f(3,1)=13
.......................
f(4,0)=13
f(4,1)=f(3,13)=f(2,f(3,12))

تا سه مرحله براتون حل کردم ، بقیه را به همین صورت حل کنید و در صورت لزوم سوال کنید
سلام, بسيار سپاسگذارم. آيا برنامه اي هست به زبان سي كه بصورت غير بازگشتي باشه و بتونه اين آكرمان رو حساب بكنه؟؟؟ استادمون گفته هست ولي خيلي زياده. من هرچي گشتم پيدا نكردم. ممنون ميشم اگر دوباره كمكم كنيد.:تشویق:

[ahmad_moin]

سلام, بسيار سپاسگذارم. آيا برنامه اي هست به زبان سي كه بصورت غير بازگشتي باشه و بتونه اين آكرمان رو حساب بكنه؟؟؟ استادمون گفته هست ولي خيلي زياده. من هرچي گشتم پيدا نكردم. ممنون ميشم اگر دوباره كمكم كنيد.

[newamir]

نمیدونم چطور میتونم عظمت این عدد آکرمان (5, 5) رو که گفتی میخوای با کد C حساب کنی برات بگم .. اینطوری بگم که این عدد نه تنها توی int و long و long long جا نمیشه بلکه توی کل حافظه کامپیوترت و حتی توی کل حافظه های تمام کامپیوتر های دنیا هم جا نمیشه! به هیچ وجه اغراق نمی کنم! برای اینکه حرفمو باور کنی یه سر به اینجا (http://en.wikipedia.org/wiki/Ackermann_function)بزن.

[ahmad_moin]

پس اين عدد چطور محاسبه ميشه؟ يكي از استادا ميگفت ميشه! من ميدونم كه خيلي گستردست ولي حتما بايد يه راه حلي داشته باشه! ما فقط ميخوايم جوابشو بدست بياريم كه (5و5)ACK چند ميشه. نمي‌خوايم تمام مراحلشو به ما نشون بده. در ضمن مي‌تونيم يك سري از آكرمانارو كه عددشو ميدونيم براش تعريف كنيم كه ديگه نيازي نباشه خوش محاسبه كنه! در حقيقت يك مقداري كار رو آسانتر كنيم و حافظه رو كمتر اشغال كنيم. نظر شما چيه؟

[newamir]

منظورم خود عددش بود که توی کامپیوترت جا نیمشه. یعنی تعداد رقماش اینقدر زیاده که حتی توی هارد کامپیوترت هم جا نمیشه! شاید استادتون میخواسته به این نتیجه برسید که نمیشه این کارو کرد ولی میشه به صورت متفاوتی اونو نمایش داد که البته هیچ ربطی به برنامه نویسی نداره. معلوم میشه به لینکی که از ویکی پدیا بت داده بودم توجه نکردی! برو بخونش تا خوب متوجه بشی.:چشمک:

[ahmad_moin]

باشه مرسي.