این مثال از کتاب پوران پژوهش صفحه 6 هست اما به نظرم یه تیکشو جا انداخته و چاپ نشده:
for (i=1;i<=n;i++)
for(j=1;j<=n;j+=i)
x=x+1;
مگه مرتبه هر خط n نمیشه؟ لطفا جواب کتاب رو هم ببینید.
به این نکته توجه کنید که حلقه دوم وابسته به حلقه اول هست.ودیگه nنمیشه
خودتونtraceکنید.نشد من حلش میکنم
(04 آذر 1393 12:21 ب.ظ)software94 نوشته شده توسط: [ -> ]به این نکته توجه کنید که حلقه دوم وابسته به حلقه اول هست.ودیگه nنمیشه
خودتونtraceکنید.نشد من حلش میکنم
درسته چون حلقه وابسته هست ، حلقه دوم میشه n(n+1)
trace هم به این شکل انجام دادم.
به ازای i=1 ، متغیر j از 1 تا n تغییر میکنه و دستور 1 بار اجرا میشه.
به ازای i=2 ، متغیر j از 1 تا n تغییر میکنه و دستور 2 بار اجرا میشه و همینطور الی آخر...
اشتباه کارمو بهم بگید ممنون.
مگه برای حلقه های وابسته مث این سوال باید حتما تریس کنیم تا جواب بدست بیاد؟
بدون تریس مگه حلش اینطوری نمیشه که اگه حلقمون =< داشته باشه و i=a باشه تعداد اجرا میشه b-a+1+1 و دستوراتش b-a+1
[/align]
نه چون وابسته است نمیشه n+1)n)
باید به ازای هربار اجرای حلقه دوم که اجرا میشه همه رو با هم جمع بزنی که یه تصاعد میشه جواب اون تصاعد میشه جواب اخرت.
دوباره traceکن
اینو ببین
توی کتاب برای حلقه های وابسته گفته حلقه دوم میشه: n(n+1)
چرا n تقسیم بر 2 میشه؟ من همین نمیفهمم.
(04 آذر 1393 01:59 ب.ظ)sarashahi نوشته شده توسط: [ -> ]چرا n تقسیم بر ۲ میشه؟ من همین نمیفهمم.
واسه اینکه بار اول گام زمانی یک پس nبار اجرا میشه.بار دومکه گام زمانی میشه 2قبول داری دوتا دوتا میره جلو پس میشهn/2بار بعد که گام زمانی میشه 3اونوقت سه تا سه تامیره جلو
حله؟
نه نمیفهمم چرا باید تقسیم بشه. وقتی j میشه 2 پس n هم میشه 2 بار.درسته؟
(04 آذر 1393 02:07 ب.ظ)sarashahi نوشته شده توسط: [ -> ]نه نمیفهمم چرا باید تقسیم بشه. وقتی j میشه ۲ پس n هم میشه ۲ بار.درسته؟
ببین میدونی گام چیه؟وقتی گام یک حلقه یکی یکی میره جلو.وقتی گام دو حلقه دوتا دتا میره جلو.وقتی دوتا دوتا بره خب مسلما نصفه nاجرا میشه.الان کجایه این مبهمه؟
تفاوتش با این برنامه چیه؟ چون الان من این برنامه زیر رو کاملا میفهمم:
for i=1 ; i=<n ; i++
for j=i ; j =<n ; j++
x=x+1;
اینجا بار اول n بار انجام میشه
بار دوم n-1 بار چون : n-2+1
بار سوم n-2 و ...
ضمنا من مرتبه زمانی رو اینجوری یاد گرفتم
برای خود حلقه وقتی =< داره میشه b-a+1+1 اگه نداشته باشه b-a+1
برای اجرای دستور داخلیش b-a+1 و b-a
با این روش من اصلا نمیفههم چرا باید تقسیم بشه؟
(04 آذر 1393 03:06 ب.ظ)sarashahi نوشته شده توسط: [ -> ]تفاوتش با این برنامه چیه؟ چون الان من این برنامه زیر رو کاملا میفهمم:
for i=1 ; i=<n ; i++
for j=i ; j =<n ; j++
x=x+1;
اینجا بار اول n بار انجام میشه
بار دوم n-1 بار چون : n-2+1
بار سوم n-2 و ...
ضمنا من مرتبه زمانی رو اینجوری یاد گرفتم
برای خود حلقه وقتی =< داره میشه b-a+1+1 اگه نداشته باشه b-a+1
برای اجرای دستور داخلیش b-a+1 و b-a
با این روش من اصلا نمیفههم چرا باید تقسیم بشه؟
تفاوتش اینه که اینجا j هیچ ربطی به i نداره.گام زمانی دو حلقه مربوط به خودشون وحلقه دوم داخل حلقه اول هست وبه ازای هربار iکه تو حلقه اول افزایش پیدا میکنه حلقه دوم دوباره از اول شروع میشه تا حلقه اول بشه n.فکر کنم این مباحثو باید حسابی روش تمرکز کنی.یک کم به گامها ونوع حلقه ها توجه کن.
اونکه i از j مستقل هست توی پست اول رو که خودمم میدونم.
مساله ما یه حلقه وابسته هست درسته؟
از طریق اون فرمولی که نوشتم میتونیم جوابو بدست بیاریم یا حتما باید تریس کنیم؟
اگه باید حتما تریس بشه میشه تریسش رو به شکلی که هم i باشه هم j هم تعداد اجرای دستور اصلی برام بنویسید.
چون بدون شکل من اصلا نمیفهمم
فرض کنید تعداد اعداد برابر 10 می باشد. n=10
گام اول: تغییرات حلقه دوم یکی یکی است پس کلا 10 بار تکرار داریم یعنی 1+2+3+ ... +10 => n عدد
گام دوم: تعییرات حلقه دوم دو تا دو تا است پس کلا 5 بار تکرار داریم(سقف جز صحیح) یعنی 1+3+5+7+9 => n/2 عدد
گام سوم: تغییرات حلقه دوم سه تا سه است پس کلا 4 تکرار داریم(سقف جز صحیح) یعینی 1 + 4 +7+10 => n/3 عدد
گام چهارم: تغییرات حلقه دوم چهار تا چهار است پس کلا 3 تکرار داریم(سقف جز صحیح) یعنی 1+ 5+9 => n/4 عدد
گام پنجم :تغییرات حلقه دوم پنج تا پنج است پس کلا 2 تکرار داریم(سقف جز صحیح) یعنی 1+6 => n/5 عدد
گام ششم:تغییرات حلقه دوم شش تا شش است پس کلا 2تکرار داریم(سقف جز صحیح) یعنی 1+7 n/6 عدد
گام هفتم:تغییرات حلقه دوم هفت تا هفت است پس کلا 2 تکرار داریم(سقف جز صحیح) یعنی 1+8 n/7 عدد
گام هشتم:تغییرات حلقه دوم هشت تا هشت است پس کلا 2 تکرار داریم(سقف جز صحیح) یعنی 1+ 9 => n/8 عدد
گام نهم: تغییرات حلقه دوم نه تا نه است پس کلا 2 تکرار داریم(سقف جز صحیح) 1+ 10 => n/9 عدد
گام دهم : تغییرات حلقه دوم ده تا ده است پس کلا 1 تکرار داریم(سقف جز صحیح) 1 n/10 عدد
گام یازدهم خروج از حلقه
نتیجه جمع تعداد اعداد بدست امده یعنی n+n/2+n/3+n/4+...n/10
نه منظورم اینه که برای i یک ستون ، برای j یک ستون و برای اجرای دستور هم یک ستون داشته باشیم تا تغییراتش رو بفهمیم.