سلام دوستان.
جواب این سوال چی میشه؟
امکانش هست برنامه رو هم از طریق تریس کردن و هم از طریق سیگما حل کنید؟
[attachment=20730]
ممنونم.
روش اول: سیگما
[tex]\sum^n_{i=1}\sum^n_{j=i}\sum^{j-1}_{r=1}1[/tex]
چرا کران بالای r برابر شده با j-1? چون r با k که مقدار j رو گرفته مقایسه میشه و چون تا زمانی که r<k مقایسه میشه پس به ازای r=j-1=k-1 هم درست هست و اجرا میشه.
چرا یک؟ چون مرتبه ی اجرای x++ برابر هست با ۱
ادامه ش:
[tex]\sum^n_{i=1}\sum^n_{j=i}\sum^{j-1}_{r=1}1=\sum_{i=1}^n\sum_{j=i}^n(j-1)[/tex]
مقدار داخلی ترین سیگما میشه از یک تا j-1 تا اجرا با هزینه ی ۱ که میشه j-1 تا اجرا با هزینه ی ۱
[tex]\sum^n_{i=1}\sum^n_{j=i}\sum^{j-1}_{r=1}1=\sum_{i=1}^n\sum_{j=i}^n(j-1)=\sum_{i=1}^n[(i-1)+(i+1-1)+(i+2-1)+(i+3-1)+...+(n-1)]=\sum^n_{i=1}[(i-1)+(i)+(i+2)+...+(n-1)]=\sum_{i=1}^n\frac{[n-1-(i-1)+1][n-1+(i-1)]}{2}=\sum^n_{i=1}\frac{[n-i+1][n+i-2]}{2}[/tex]
[tex]\sum^n_{i=1}\frac{[n-i+1][n+i-2]}{2}=\sum^n_{i=1}\frac{[n^2+ni-2n-ni-i^2-2+n+i+2i]}{2}=\frac{1}{2}\sum_{i=1}^n[n^2-i^2-n+3i-2]=[\frac{1}{2}\sum n^2-n-2-\sum i^2+3\sum i]=\frac{1}{2}[n\times(n^2-n-2)-\frac{n(n+1)(2n+1)}{2}+\frac{3n(n+1)}{2}][/tex]
[tex]\frac{1}{2}[n^3-n^2-2n-\frac{2n^3}{6}-\frac{3n^2}{6}-\frac{n}{6}+\frac{3n^2}{2}+\frac{3n}{2}]=\frac{1}{12}[6n^3-6n^2-12n-2n^3-3n^2-n+9n^2+9n]=\frac{1}{12}[4n^3-4n]=\frac{(n^3-n)}{3}[/tex]
روش دوم:
سوال تبدیل میشه به:
for i=1 to n
for j=i to n
for r=1 to j-1
i=1
اصلا اجرا نمیشه چون شرط whileبرقرار نیست.
i=2
یک بار اجرا میشه
i=3
j=3>1 پس دو بار اجرا یعنی از ۱ تا ۲
j=4>1 پس سه بار اجرا یعنی از ۱ تا ۳
.
.
j=n>1 پس n-1 بار اجرا از ۱ تا n-1
برای i=1 تعداد ۱+۲+۳+…+ n-1 بار اجرا میشه که برابر هست با n(n-1)/2 بار
برای i=2 تعداد ۱+۲+۳+…+n-1 بار
برای i=3 تعداد ۲+۳+…+n-1 بار
.
.
.
یکی کم میشه از سمت پایین دنباله ی جمع.
مجموع اینا [tex]\sum^n_{k=0}\frac{1}{2}[(n-k)\cdot(n-1+k)]=\frac{1}{2}\sum(n^2-n+nk-kn+k-k^2)=[/tex]
.
[tex]\frac{1}{2}\sum^n_{k=0}(n^2-n+k-k^2)=\frac{1}{2}[n^3-n^2]+\frac{1}{2}\sum^n_{k=0}k+\frac{1}{2}\sum k^2=\frac{(n^3-n^2)}{2}+\frac{(n+1)(n+2)}{4}-\frac{(n+1)(2n+3)(n+2)}{12}=\frac{[6n^3-6n^2+3n^2+9n+9n^2-12n-n-3n^2-2n^3]}{12}=\frac{[4n^3-4n]}{12}=\frac{[n^3-n]}{3}[/tex]
for j=i to n
for r=1 to j-1
i=1
اصلا اجرا نمیشه چون شرط whileبرقرار نیست.
i=2
یک بار اجرا میشه
i=3
j=3>1 پس دو بار اجرا یعنی از ۱ تا ۲
j=4>1 پس سه بار اجرا یعنی از ۱ تا ۳
.
.
j=n>1 پس n-1 بار اجرا از ۱ تا n-1
برای i=1 تعداد ۱+۲+۳+…+ n-1 بار اجرا میشه که برابر هست با n(n-1)/2 بار
برای i=2 تعداد ۱+۲+۳+…+n-1 بار
برای i=3 تعداد ۲+۳+…+n-1 بار
.
.
.
یکی کم میشه از سمت پایین دنباله ی جمع.
مجموع اینا [tex]\sum^n_{k=0}\frac{1}{2}[(n-k)\cdot(n-1+k)]=\frac{1}{2}\sum(n^2-n+nk-kn+k-k^2)=[/tex]
.
حل این سوال به یه روش دیگه:
[attachment=20757]