برنامه نویسی پویا [بایگانی]

yas1213

شنبه 12 اردیبهشت 1388, 01:31 صبح

الگوریتم ضریب دو جمله ای با استفاده از برنامه نویسی پویا را چنان اصلاح کنید که فقط از یک ارایه تک بعدی با اندیس 0 تا k استفاده کند.
(سوال 4 فصل سوم نیپولیتان)

ضریب دو جمله ای ترکیب k از n و k,n باید دو اندیس داشته باشه یعنی ارایه دو بعدی چه جوری میشه با ارایه یک بعدی نوشت؟؟؟؟

yas1213

شنبه 19 اردیبهشت 1388, 03:50 صبح

یه راهنماییی لطفا!!!!
سوال 24 همین فصل (3) رو هم راهنمایی کنید!!

mortezamsp

چهارشنبه 23 اردیبهشت 1388, 00:36 صبح

[quoteضریب دو جمله ای ترکیب k از n و k,n باید دو اندیس داشته باشه یعنی ارایه دو بعدی چه جوری میشه با ارایه یک بعدی نوشت؟؟؟؟[/quote]

خب! يه آرايه يه بعدي به طول n ميتونه نماينده ي يه آرايه دو بعدي با طول n/2 باشه ديگه !

مثلا عبارتي كه از چهار جمله تشكيل شده رو تو يه آرايه ي هشت عضوي ميريزي . و براي جمع كردن دوتا از اين آرايه ها هم كاري نداره ديگه ! تو for دوتادوتا جلوميريم.ok?

yas1213

دوشنبه 28 اردیبهشت 1388, 18:32 عصر

خوب اخه این ارایه دو بعدی یکیش k رو نشون میده اوون یکی n بعد چه جوری تو یه ارایه بذاریم؟؟؟؟!!!
k,n دوتا پارامترن!

newamir

سه شنبه 29 اردیبهشت 1388, 00:18 صبح

اگه دقت کنی میبینی که توی مثلث پاسکال یا همون ماتریسی که توی راه حل پویا استفاده میکنیم، برای تولید سطر n+1 فقط به سطر n نیاز داریم نه به تمام سطرهای قبلی. پس کافیه هر بار فقط آخرین سطر رو توی یه آرای یه بعدی ذخیره کنی تا حافظه از اوی n بشه.