PDA

View Full Version : به نظر شما جواب این تست کدوم گزینه است؟



Developer Programmer
جمعه 20 آبان 1384, 12:42 عصر
در مورد پاسخ درست ، شک دارم ،

سوال) دلیل استفاده از برنامه نویسی پویا به جای فراخوانی های بازگشتی در محاسبه جمله n ام دنباله فیبوناچی چیست؟
الف) تفاوتی ندارند
ب) روش پویا جواب دقیقتری می دهد
ج) روش پویا حافظه کمتری مصرف میکند
د) روش پویا زمان کمتری مصرف می کند

سوال) عمل اصلی، چند بار تکرار می شود؟


for i:=1 to n do
for j:=i to n do
for k:=1 to j do
write('*');

الف) 2/(n^3+n^2)
ب) سیگمای i^2
ج) سیگمای (i^(3/2
د) سیگمای i-1) * i)

(توضیح: لطفا پاسخ تشریحی!)

seyedof
جمعه 20 آبان 1384, 13:56 عصر
سلام
آقا من تستیشو میگم
فکر کنم سوال اول ج
فکر کنم سوال دوم ب
ممنون علی

Developer Programmer
جمعه 20 آبان 1384, 20:11 عصر
جوابهایی که دادید درسته! ولی من هرچی زور می زنم نمیتونم به جواب درست برسم!
درمورد سوال اول-> تمام الگوریتم های بازگشتی حافظه زیادی مصرف میکنند... درست...ولی کتاب طراحی الگوریتم جعفرنژاد نوشته که الگوریتم پویای فیبوناچی n+1 گذر داره ولی بازگشتی بیشتر ...همچنین بازگشتی برای جمله 80 چندسال می تونه طول بکشه
پس هم ج و هم د می تونه جواب باشه ! نه ؟
در مورد سوال دو ، لطفا روشتون رو اینجا بذارین
---
پیر شین الهی ،مرسی

seyedof
شنبه 21 آبان 1384, 00:53 صبح
سلام
دلیلی ندارم ولی در الگوریتم بازگشتی همیشه معضل stack وجود داره. فکر نمیکنم دلیل دیگری وجود داشته باشه که برای مسایل ساده مثل فیبوناچی از روش بازگشتی استفاده نشه.
در مورد دومی واقعیتش رو بخواهید خودم هم شک دارم. دقیق محاسبه کنم میگم. دوستان دیگه هم اگر نظری دارن حتما بگن. من رو جواب دومی خودم هم شدیدا شک دارم.

ممنون علی

seyedof
شنبه 21 آبان 1384, 01:04 صبح
سلام
تصحیح میکنم. الگوریتم فیبونانچی بازگشتی که مشخصه حافظه بیشتری میبره یعنی تا اینجای کار قبول دارید که این گزینه درسته. گزینه اول که مسخره است. گزینه دوم هم همینطور. میمونه گزینه دال. این گزینه هم غلطه چون هر دو پیچیدگی زمانیشون n است. یعنی الزاما هیچ کدوم از نظر تئوریک از اوون یکی سریعتر نیست.
سوال دوم رو هم تست کردم همون گزینه ب درست بود ولی ذهنی حل کردم. نمیدونم چطور بتونم اثباتش کنم.
تعداد تکرار = n(n+1)(2n+1)/6
ممنون علی

Developer Programmer
شنبه 21 آبان 1384, 12:02 عصر
هر دو پیچیدگی زمانیشون n است

تعداد جمله های حساب شده توسط الگوریتم بازگشتی بیش از 2 به توان n/2 است اما تعداد محاسبه الگوریتم پویا n+1
پس الگوریتم بازگشتی برای n=80 معادل 36 سال وقت لازم دارد ولی الگوریتم معمولی می تواند در 18 دقیقه محاسبه کند
(کتاب جعفر نژاد قمی ، صفحه 24)

Developer Programmer
شنبه 21 آبان 1384, 12:16 عصر
خوب حالا یه سئوال دیگه
سوال) کدام گزینه در مورد الگوریتم حریصانه(Greedy) می تواند درست باشد؟
الف) روال انتخاب، حذف عنصر انتخاب شده از مجموعه جواب
ب) روال انتخاب، افزودن عنصر به مجموعه جواب
ج) انتخاب ،حل , تحقیق عملی بودن
د) انتخاب , تحقیق عملی بودن ؛ حل
(توضیح : تصور من اینه که الگوریتم حریصانه چیزی رو حل نمی کنه و عملی بودن آن رو چک نمیکنه بلکه انتخاب می کنه و بدون توجه به انتخاب های قبلی جلو می ره)

سوال) اگر P یک اشاره گر باشه , کدوم گزینه می تونه درست باشه؟


new(p);
new(p);
dispose(p);
dispose(p);

الف) داده زباله ای (Garbage)
ب) آدرس سرگردان (Dangling Refrence)
ج) تعریف مجدد (Duplicate)
د) در اولین Dispose فضای P آزاد میشود لذا دستور Dispose دوم دچار مشکل میشود

seyedof
شنبه 21 آبان 1384, 15:59 عصر
سلام

اولی الف
دومی د

ممنون علی

Developer Programmer
شنبه 21 آبان 1384, 22:32 عصر
سلام
---
طراح سوال:
اولی د
دومی الف
----
از نظر من :
اولی ب
دومی د

aakh1361
یک شنبه 22 آبان 1384, 03:05 صبح
سوال) اگر P یک اشاره گر باشه , کدوم گزینه می تونه درست باشه؟

کد:


new(p);
new(p);
dispose(p);
dispose(p);

الف) داده زباله ای (Garbage)
ب) آدرس سرگردان (Dangling Refrence)
ج) تعریف مجدد (Duplicate)
د) در اولین Dispose فضای P آزاد میشود لذا دستور Dispose دوم دچار مشکل میشود


هم الف و هم د
الف درسته چون در اول ما یک حافظه از سیستم می گیریم و دوباره با همون اشاره گر از سیستم حافظه دیگری می گیریم پس ادرس حافظه اولی که از سیستم گرفتیم پاک می شود دقت کنید حافظه به سیستم بازگردانده نمی شود

د درسته چون وقتی ما حافظه اشاره گری رو آزاد می کنیم اون اشاره گر
NULL
میشه یا به یک جای نا مشخص از حافظه اشاره می کنه و اگر دوباره همئن اشاره گر رو ازاد کنیم سیستم دچار مشکل میشه و در موارد حاد برنامه دچار فروپاشی میشه
:شیطان:

Developer Programmer
یک شنبه 22 آبان 1384, 16:11 عصر
با تشکر از دوستان گرامی و استادان

هر دو پیچیدگی زمانیشون n است
امروز هر طور شده دکتر رضوی رو پیدا کردم و ازش پرسیدم
ایشون ثابت کردند که مصرف حافظه در فیبوناچی بازگشتی در برابر زمان مصرفی که تابع نمایی است ناچیز است! پس تا اینجا سنجش 3 حدود 7تا تست غلط طرح کرده اند!

eyelash
یک شنبه 13 آذر 1384, 01:16 صبح
تست اول گزینه ج.
تست دوم هم فکر می کنم ب.