سلام.
دوستان تست زیر چطور حل میشه؟ و لطفا یه نفر قانون و روش حل اینطور سوالات رو توضیح بده. ممنون میشم ازتون.
کد:
for(i=0;i<n;i=i/2)
for(j=i;j<n;j=j/3)
x++;سلام
اینجور سوالات من اینجور واسه خودم تحلیل میکنم حالا نمیدونم چطور میشه واسه بعضیها درست جواب میده و اسه بعضیها نه!
حلقه while بیرونی در این سوال داره هر بار بازه رو نصف میکنه یعنی log n مبنای ۲، اما این حلقه، حلقه دیگه ای از while در دل خودش داره که همون i رو این دفعه یه log n مبنای۳ دیگه میگیره ولی حاصلش بر روی حلقه بیرونی تاثیری نداره واسه همین نمیگیم log logn و لگاریتم ها در هم ضرب میشن
اگر بخوایم بگیم مبناها رو در نظر نگیریم فکر کنم گزینه ۲ باشه...
لطفا دوستان دیگه راهنمایی کنند
(۱۹ آذر ۱۳۹۱ ۰۲:۴۸ ب.ظ)Amir V نوشته شده توسط: سلام.
دوستان تست زیر چطور حل میشه؟ و لطفا یه نفر قانون و روش حل اینطور سوالات رو توضیح بده. ممنون میشم ازتون.
کد:
for(i=0;i<n;i=i/2)
for(j=i;j<n;j=j/3)
x++;
با سلام:
به نظر من یه جای این سوال لنگ میزنه و حلقه بی نهایت بار اجرا میشه آخه شرط i=i/2 هیچ وقت افزایش پیدا نمیکنه وقتی حلقه از i=0 شروع میشه همیشه شرط برقراره/...
دوستان یه چک کنن ببینن چه جوری میشه!!!!
(۱۹ آذر ۱۳۹۱ ۰۸:۴۱ ب.ظ)m@hboobe نوشته شده توسط: سلامبا سلام:
اینجور سوالات من اینجور واسه خودم تحلیل میکنم حالا نمیدونم چطور میشه واسه بعضیها درست جواب میده و اسه بعضیها نه!
حلقه while بیرونی در این سوال داره هر بار بازه رو نصف میکنه یعنی log n مبنای ۲، اما این حلقه، حلقه دیگه ای از while در دل خودش داره که همون i رو این دفعه یه log n مبنای۳ دیگه میگیره ولی حاصلش بر روی حلقه بیرونی تاثیری نداره واسه همین نمیگیم log logn و لگاریتم ها در هم ضرب میشن
اگر بخوایم بگیم مبناها رو در نظر نگیریم فکر کنم گزینه ۲ باشه...
لطفا دوستان دیگه راهنمایی کنند
این سوال که شما عکس اونا گذاشتین جوابش [tex]log^{2}n[/tex]
حلقه اول [tex]logn[/tex] حلقه دوم هم[tex]logn[/tex] بار تکرار میشه در کل همون [tex]log^{2}n[/tex] میشه/...
منم موافقم با شما :
من اینطور تستا رو با نوشتن چند مرحله از اجراش و بعد بسطش تا آخر حل میکنم که اینطور میشه:
[tex]log_{3}^{n} log_{3}^{n/2} log_{3}^{n/4} ... log_{3}^{2} log_{3}^{1}[/tex]
که تعداد این log ها برابر با[tex]log_{2}^{n}[/tex]
و از اونجایی که تمام log ها با هم هم رشد هستند برای تعیین مرتبه میتونیم پایه log ها رو ۲ در نظر بگیرم و بگیم که lg n تا lg داریم(n و n/2 و ... رو هم میتونیم همرو n در نظر بگیریم).
که میشه : [tex]\Theta (lgn lgn lgn ...)=\Theta(lg^2n)[/tex]
(۱۹ آذر ۱۳۹۱ ۰۹:۱۹ ب.ظ)deh-ab نوشته شده توسط: به نظر من یه جای این سوال لنگ میزنه و حلقه بی نهایت بار اجرا میشه آخه شرط i=i/2 هیچ وقت افزایش پیدا نمیکنه وقتی حلقه از i=0 شروع میشه همیشه شرط برقراره/...بله همین جوره که میگید !
دوستان یه چک کنن ببینن چه جوری میشه!!!!
من تستهای سال۹۱ کامپیوتر و ایتی چک کردم فقط این سوال بود که چنین شباهتی داشت با این تیکه کد!!
ممنون بچه ها.
یه دفعه دیگه میشه بگین چرا loglogn نمیشه؟
منبعی یا جزوه ای چیزی دارین که بشه این نوع مرتبه زمانیها رو از روش خوند؟ یا مثلا مرتبه زمانیهایی که نیاز به تغییر متغیر دارن.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
یه کتاب طراحی الگوریتم هست، از دکتر باقری انتشارات ناقوس چاپش کرده و جلد سیاه و زردی داره
اون کتاب پر مسئله و تمرین واسه اینجور مرتبه زمانی هاست انواع مختلفی ازش رو حل کرده
(۱۹ آذر ۱۳۹۱ ۱۰:۲۲ ب.ظ)Amir V نوشته شده توسط: ممنون بچه ها.
یه دفعه دیگه میشه بگین چرا loglogn نمیشه؟
منبعی یا جزوه ای چیزی دارین که بشه این نوع مرتبه زمانیها رو از روش خوند؟ یا مثلا مرتبه زمانیهایی که نیاز به تغییر متغیر دارن.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
ببینید داخل تمام حل هایی که دوستان انجام دادند ثابت شد که ما به تعداد lgn بار حلقه شامل حلقه داخلی (که خود حلقه داخلی هم تقریبا هر بار lgn بار اجرا میشه) رو اجرا میکنیم پس lgn * lgn جواب میشه. اما lglgn رشدش خیلی کمتر از این حرفاست، هیچ ربطی به جواب این سوال نداره دلیل سوالتون رو نمیفهمم، جایی همچین جوابی دادند که واسه شما سوال شده؟
البته گاهی دیدم برخی این ۲ تا رو به اشتباه(بخاطر نزدیکی ظاهری) یکی میدونن ، اما با کمی توجه میفهمید که خیییییلی با هم فرق دارند!
(۱۹ آذر ۱۳۹۱ ۱۱:۱۱ ب.ظ)javadem نوشته شده توسط:حق با شماست من اشتباه دیدم. درسته Logn به توان ۲ هستش.(19 آذر ۱۳۹۱ ۱۰:۲۲ ب.ظ)Amir V نوشته شده توسط: ممنون بچه ها.
یه دفعه دیگه میشه بگین چرا loglogn نمیشه؟
منبعی یا جزوه ای چیزی دارین که بشه این نوع مرتبه زمانیها رو از روش خوند؟ یا مثلا مرتبه زمانیهایی که نیاز به تغییر متغیر دارن.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
ببینید داخل تمام حل هایی که دوستان انجام دادند ثابت شد که ما به تعداد lgn بار حلقه شامل حلقه داخلی (که خود حلقه داخلی هم تقریبا هر بار lgn بار اجرا میشه) رو اجرا میکنیم پس lgn * lgn جواب میشه. اما lglgn رشدش خیلی کمتر از این حرفاست، هیچ ربطی به جواب این سوال نداره دلیل سوالتون رو نمیفهمم، جایی همچین جوابی دادند که واسه شما سوال شده؟
البته گاهی دیدم برخی این ۲ تا رو به اشتباه(بخاطر نزدیکی ظاهری) یکی میدونن ، اما با کمی توجه میفهمید که خیییییلی با هم فرق دارند!
مرسی از لطفت.
(۱۹ آذر ۱۳۹۱ ۱۰:۴۷ ب.ظ)a.nikfarjam نوشته شده توسط: یه کتاب طراحی الگوریتم هست، از دکتر باقری انتشارات ناقوس چاپش کرده و جلد سیاه و زردی دارهمرسی همشهری جدید.
اون کتاب پر مسئله و تمرین واسه اینجور مرتبه زمانی هاست انواع مختلفی ازش رو حل کرده
لینک دانلود نداری واسه این کتاب؟
(۱۹ آذر ۱۳۹۱ ۰۹:۱۹ ب.ظ)deh-ab نوشته شده توسط: با سلام:شما درست میگید.
به نظر من یه جای این سوال لنگ میزنه و حلقه بی نهایت بار اجرا میشه آخه شرط i=i/2 هیچ وقت افزایش پیدا نمیکنه وقتی حلقه از i=0 شروع میشه همیشه شرط برقراره/...
من منظورم همون عکسی هست که دوستمون گذاشتن. خواستم به صورت for بنویسم که راحت تر بشه تحلیلش کرد.
درستش اینه:
کد:
for(i=0;i<n;i=i/2)
for(j=i;j>1;j=j/3)
x++;(۲۰ آذر ۱۳۹۱ ۰۱:۰۷ ق.ظ)Amir V نوشته شده توسط:(19 آذر ۱۳۹۱ ۱۱:۱۱ ب.ظ)javadem نوشته شده توسط:حق با شماست من اشتباه دیدم. درسته Logn به توان ۲ هستش.(19 آذر ۱۳۹۱ ۱۰:۲۲ ب.ظ)Amir V نوشته شده توسط: ممنون بچه ها.
یه دفعه دیگه میشه بگین چرا loglogn نمیشه؟
منبعی یا جزوه ای چیزی دارین که بشه این نوع مرتبه زمانیها رو از روش خوند؟ یا مثلا مرتبه زمانیهایی که نیاز به تغییر متغیر دارن.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
ببینید داخل تمام حل هایی که دوستان انجام دادند ثابت شد که ما به تعداد lgn بار حلقه شامل حلقه داخلی (که خود حلقه داخلی هم تقریبا هر بار lgn بار اجرا میشه) رو اجرا میکنیم پس lgn * lgn جواب میشه. اما lglgn رشدش خیلی کمتر از این حرفاست، هیچ ربطی به جواب این سوال نداره دلیل سوالتون رو نمیفهمم، جایی همچین جوابی دادند که واسه شما سوال شده؟
البته گاهی دیدم برخی این ۲ تا رو به اشتباه(بخاطر نزدیکی ظاهری) یکی میدونن ، اما با کمی توجه میفهمید که خیییییلی با هم فرق دارند!
مرسی از لطفت.
(۱۹ آذر ۱۳۹۱ ۱۰:۴۷ ب.ظ)a.nikfarjam نوشته شده توسط: یه کتاب طراحی الگوریتم هست، از دکتر باقری انتشارات ناقوس چاپش کرده و جلد سیاه و زردی دارهمرسی همشهری جدید.
اون کتاب پر مسئله و تمرین واسه اینجور مرتبه زمانی هاست انواع مختلفی ازش رو حل کرده
لینک دانلود نداری واسه این کتاب؟
(۱۹ آذر ۱۳۹۱ ۰۹:۱۹ ب.ظ)deh-ab نوشته شده توسط: با سلام:شما درست میگید.
به نظر من یه جای این سوال لنگ میزنه و حلقه بی نهایت بار اجرا میشه آخه شرط i=i/2 هیچ وقت افزایش پیدا نمیکنه وقتی حلقه از i=0 شروع میشه همیشه شرط برقراره/...
من منظورم همون عکسی هست که دوستمون گذاشتن. خواستم به صورت for بنویسم که راحت تر بشه تحلیلش کرد.
درستش اینه:
کد:
for(i=0;i<n;i=i/2)
for(j=i;j>1;j=j/3)
x++;
آقا امیر داداش نه بازم درست نیست اخه این حلقه اول( for( i=0 ; i<n ; i=i/2 بی نهایت بار اجرا میشه برای مثال ببین:
اگر i=0 و n=1 باشه داریم:
شرط حلقه چک میشه ۱>0 هست پس وارد گام بعدی حلقه میشه (i=i/2) پس میشه i=0/2 (مشکل اینجاست که جواب این رابطه همیشه ۰ هست یعنی ۰ تقسیم بر ۲ میشه ۰ ،پس دوباره i برابر با ۰ میشه و این حلقه بی نهایت بار به همین منوال تکرار میشه)
درستش این جوریه:
( for( i=n ; i>0 ; i=i/2
( for( j=i ; j>0 ; j=j/3
x++
امیدوارم خوب توضیح داده باشم/...
موفق و پیروز باشید یا حق/...
درسته. بابت گیج بازیم شرمنده.
مرسی.
Sent from my Google Galaxy Nexus using Tapatalk 2.4