سلام.
دوستان تست زیر چطور حل میشه؟ و لطفا یه نفر قانون و روش حل اینطور سوالات رو توضیح بده. ممنون میشم ازتون.
کد:
for(i=0;i<n;i=i/2)
for(j=i;j<n;j=j/3)
x++;
سلام
اینجور سوالات من اینجور واسه خودم تحلیل میکنم حالا نمیدونم چطور میشه واسه بعضیها درست جواب میده و اسه بعضیها نه!
حلقه while بیرونی در این سوال داره هر بار بازه رو نصف میکنه یعنی log n مبنای 2، اما این حلقه، حلقه دیگه ای از while در دل خودش داره که همون i رو این دفعه یه log n مبنای3 دیگه میگیره ولی حاصلش بر روی حلقه بیرونی تاثیری نداره واسه همین نمیگیم log logn و لگاریتم ها در هم ضرب میشن
اگر بخوایم بگیم مبناها رو در نظر نگیریم فکر کنم گزینه 2 باشه...
لطفا دوستان دیگه راهنمایی کنند
(19 آذر 1391 02:48 ب.ظ)Amir V نوشته شده توسط: [ -> ]سلام.
دوستان تست زیر چطور حل میشه؟ و لطفا یه نفر قانون و روش حل اینطور سوالات رو توضیح بده. ممنون میشم ازتون.
کد:
for(i=0;i<n;i=i/2)
for(j=i;j<n;j=j/3)
x++;
با سلام:
به نظر من یه جای این سوال لنگ میزنه و حلقه بی نهایت بار اجرا میشه آخه شرط i=i/2 هیچ وقت افزایش پیدا نمیکنه وقتی حلقه از i=0 شروع میشه همیشه شرط برقراره/...
دوستان یه چک کنن ببینن چه جوری میشه!!!!
(19 آذر 1391 08:41 ب.ظ)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 ها رو 2 در نظر بگیرم و بگیم که lg n تا lg داریم(n و n/2 و ... رو هم میتونیم همرو n در نظر بگیریم).
که میشه : [tex]\Theta (lgn lgn lgn ...)=\Theta(lg^2n)[/tex]
(19 آذر 1391 09:19 ب.ظ)deh-ab نوشته شده توسط: [ -> ]به نظر من یه جای این سوال لنگ میزنه و حلقه بی نهایت بار اجرا میشه آخه شرط i=i/2 هیچ وقت افزایش پیدا نمیکنه وقتی حلقه از i=0 شروع میشه همیشه شرط برقراره/...
دوستان یه چک کنن ببینن چه جوری میشه!!!!
بله همین جوره که میگید !
من تستهای سال91 کامپیوتر و ایتی چک کردم فقط این سوال بود که چنین شباهتی داشت با این تیکه کد!!
ممنون بچه ها.
یه دفعه دیگه میشه بگین چرا loglogn نمیشه؟
منبعی یا جزوه ای چیزی دارین که بشه این نوع مرتبه زمانیها رو از روش خوند؟ یا مثلا مرتبه زمانیهایی که نیاز به تغییر متغیر دارن.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
یه کتاب طراحی الگوریتم هست، از دکتر باقری انتشارات ناقوس چاپش کرده و جلد سیاه و زردی داره
اون کتاب پر مسئله و تمرین واسه اینجور مرتبه زمانی هاست انواع مختلفی ازش رو حل کرده
(19 آذر 1391 10:22 ب.ظ)Amir V نوشته شده توسط: [ -> ]ممنون بچه ها.
یه دفعه دیگه میشه بگین چرا loglogn نمیشه؟
منبعی یا جزوه ای چیزی دارین که بشه این نوع مرتبه زمانیها رو از روش خوند؟ یا مثلا مرتبه زمانیهایی که نیاز به تغییر متغیر دارن.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
ببینید داخل تمام حل هایی که دوستان انجام دادند ثابت شد که ما به تعداد lgn بار حلقه شامل حلقه داخلی (که خود حلقه داخلی هم تقریبا هر بار lgn بار اجرا میشه) رو اجرا میکنیم پس lgn * lgn جواب میشه. اما lglgn رشدش خیلی کمتر از این حرفاست، هیچ ربطی به جواب این سوال نداره دلیل سوالتون رو نمیفهمم، جایی همچین جوابی دادند که واسه شما سوال شده؟
البته گاهی دیدم برخی این 2 تا رو به اشتباه(بخاطر نزدیکی ظاهری) یکی میدونن ، اما با کمی توجه میفهمید که خیییییلی با هم فرق دارند!
(19 آذر 1391 11:11 ب.ظ)javadem نوشته شده توسط: [ -> ] (19 آذر 1391 10:22 ب.ظ)Amir V نوشته شده توسط: [ -> ]ممنون بچه ها.
یه دفعه دیگه میشه بگین چرا loglogn نمیشه؟
منبعی یا جزوه ای چیزی دارین که بشه این نوع مرتبه زمانیها رو از روش خوند؟ یا مثلا مرتبه زمانیهایی که نیاز به تغییر متغیر دارن.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
ببینید داخل تمام حل هایی که دوستان انجام دادند ثابت شد که ما به تعداد lgn بار حلقه شامل حلقه داخلی (که خود حلقه داخلی هم تقریبا هر بار lgn بار اجرا میشه) رو اجرا میکنیم پس lgn * lgn جواب میشه. اما lglgn رشدش خیلی کمتر از این حرفاست، هیچ ربطی به جواب این سوال نداره دلیل سوالتون رو نمیفهمم، جایی همچین جوابی دادند که واسه شما سوال شده؟
البته گاهی دیدم برخی این ۲ تا رو به اشتباه(بخاطر نزدیکی ظاهری) یکی میدونن ، اما با کمی توجه میفهمید که خیییییلی با هم فرق دارند!
حق با شماست من اشتباه دیدم. درسته Logn به توان 2 هستش.
مرسی از لطفت.
(19 آذر 1391 10:47 ب.ظ)a.nikfarjam نوشته شده توسط: [ -> ]یه کتاب طراحی الگوریتم هست، از دکتر باقری انتشارات ناقوس چاپش کرده و جلد سیاه و زردی داره
اون کتاب پر مسئله و تمرین واسه اینجور مرتبه زمانی هاست انواع مختلفی ازش رو حل کرده
مرسی همشهری جدید.
لینک دانلود نداری واسه این کتاب؟
(19 آذر 1391 09:19 ب.ظ)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++;
(20 آذر 1391 01:07 ق.ظ)Amir V نوشته شده توسط: [ -> ] (19 آذر 1391 11:11 ب.ظ)javadem نوشته شده توسط: [ -> ] (19 آذر 1391 10:22 ب.ظ)Amir V نوشته شده توسط: [ -> ]ممنون بچه ها.
یه دفعه دیگه میشه بگین چرا loglogn نمیشه؟
منبعی یا جزوه ای چیزی دارین که بشه این نوع مرتبه زمانیها رو از روش خوند؟ یا مثلا مرتبه زمانیهایی که نیاز به تغییر متغیر دارن.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
ببینید داخل تمام حل هایی که دوستان انجام دادند ثابت شد که ما به تعداد lgn بار حلقه شامل حلقه داخلی (که خود حلقه داخلی هم تقریبا هر بار lgn بار اجرا میشه) رو اجرا میکنیم پس lgn * lgn جواب میشه. اما lglgn رشدش خیلی کمتر از این حرفاست، هیچ ربطی به جواب این سوال نداره دلیل سوالتون رو نمیفهمم، جایی همچین جوابی دادند که واسه شما سوال شده؟
البته گاهی دیدم برخی این ۲ تا رو به اشتباه(بخاطر نزدیکی ظاهری) یکی میدونن ، اما با کمی توجه میفهمید که خیییییلی با هم فرق دارند!
حق با شماست من اشتباه دیدم. درسته Logn به توان ۲ هستش.
مرسی از لطفت.
(19 آذر 1391 10:47 ب.ظ)a.nikfarjam نوشته شده توسط: [ -> ]یه کتاب طراحی الگوریتم هست، از دکتر باقری انتشارات ناقوس چاپش کرده و جلد سیاه و زردی داره
اون کتاب پر مسئله و تمرین واسه اینجور مرتبه زمانی هاست انواع مختلفی ازش رو حل کرده
مرسی همشهری جدید.
لینک دانلود نداری واسه این کتاب؟
(19 آذر 1391 09:19 ب.ظ)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 باشه داریم:
شرط حلقه چک میشه 1>0 هست پس وارد گام بعدی حلقه میشه (i=i/2) پس میشه i=0/2 (مشکل اینجاست که جواب این رابطه همیشه 0 هست یعنی 0 تقسیم بر 2 میشه 0 ،پس دوباره i برابر با 0 میشه و این حلقه بی نهایت بار به همین منوال تکرار میشه)
درستش این جوریه:
( 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