صفحه 1:
الگوریتم(0-4: ضرب اعداد صحیح بزرگ
مسئله: ضرب دو عدد صحیح بزرگ بو
( تا رن وا ) لو تا ما
1
2 , نس faxpe_heewer x,y,
رمعم
w= woxiwuro(auwber oF digits it umber oF digits ict)
||[v==©0) - دمما ع
retura O 5
صفحه 2:
phe PB (0 < = threshol!)
له ند ان موف athe usd way;
ube {
w
1۰/9 15:
بس “ 00 p= row : (00 طبر ند
۸ 0) مور << : و (00 طغظا نا 2 w
“Ger + ( prod (x, 2) + prod ۵ سم لو موم
(w, vv )) ¥ AD * w + prod (vy, 2);
x
صفحه 3:
تحلیل پیچیدگی زمانی در بدترین حالت برای ! لگوریتم( ضرب اعداد صحیح)
عمل اصلی: دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در
هنكام جمع کردن » تفریق کردن» یا انجام اعمالس ۸ cute ID
۸۰ 00 مور یا 000 4 س. هر يك از اين اعمال را جه بار انجام مى دهد.
اندازه ورودى: ج ٠ تعداد ارقام هر یک از دو عدد صحیح.
به ازاى ج < که و توانی از ©استحم + (© /0) 4 6 -
D(a
رم و 6 T(a)
صفحه 4:
در چه مسائلی نمی توان از روش تقسیم وحل
استفاده کرد
٠ - مسایلی با اندازه ب به چند زیر مسئله تقسیم می شود که
اندازه زیر مسئله ها نیز تقریبا برابر ب است.
زمان نمایی ایجاد می کند.
٠ تالایا اندازه و تفرییابه انداژه زیر مسلهبا
اندازه ج/- که در آن ج ثابت است تقسیم می شود.
زمان ",ام ایجاد می کند.
صفحه 5:
فرش كردن صفحه شطرنجی
۰ ابعاد صفحه 2*۷ است.
* موزاییک به شکل را است.
۶ در بدترین حالت یکی از خانه ها خالی می ماند.
صفحه 6:
صفحه 7:
صفحه 8:
صفحه 9:
صفحه 10:
صفحه 11:
صفحه 12:
صفحه 13:
ضرب چند جمله ای ها
۰ ۳ ومع( cae ره + tty
۰ Q(x) Eb ath, perth exe? .. . box? + bythe
٠١ Rlx)= PAK)
صفحه 14:
۱ ی
© Qq)Rb th gather? .. . . وعلذابييا + قبريها
© 800-009 0(-
abo + ciybyx tay bax? FE لحيو وت + عي عليه یی + abo
mbox bee tab? +. + abe" + be + abt
جلي مه لوعي دوعصو نيه
صفحه 15:
۰ (۳6۵۵۶
۱ ی ی
abort shox tao? +. ab ox! + ab ge + abe
taabex® +. agb gx? + aah gat + ugh et? مم طنه +« ونه
صفحه 16:
۳6۵۵۶( ۰
۱
كتم ی ی ی جارك
باه ارت بیج . جک سر + مره جنگ مر
who * (subotsabale +
صفحه 17:
۰ (۳6۵۵۶
Po t aphex tay hor? +. A ab ox + طريه gent + agh x”
abort ybox tao? + abort + ab ge + abe
obo
Ot aby tagbax® +. aah ox? + aah get! + ugh"?
Sebo)? + + يطيه + ببطريه) + +«( وطريهخروطيه) + وطريه
صفحه 18:
۵ <() ۰
ی ی ۱
۳
x ره ره ری رن مرت یی
aby 2°F ayhyx? tagbox® +. ugh. ox" + ugh gx ره
(bot Igbalx + (Soke + aba tIebo? +. + - + توت
k
بط 2 -مدجمله لم th
FO
(۵۵
2 |
صفحه 19:
57 ۲
از به دو مر برای محاسبه بنابراین : O?)
صفحه 20:
روش تقسیم وحل
برای ضرب چند جمله ایها
R(x)= P(WJA(x)
P(x) =Bx") +B
Q(x) = C x) + ©
sul dC Ad ظ) , 9) جند جمله لیاز ,) ,0 ۶
R(x)= Px)A(x)=(Ox)+B (Cx) +O)
= BOw +(BO+BC)x)+ BO
تعداد ضرب ها 6 تا است, ۰
حم ۲ (۳)۰(<2/)/۵ عمل ضرب
D(a)=8(0?)
الگوریتم بهتر نشده است. ۰
صفحه 21:
(۵+ ر)(۲۵)ع() ۵00۵ ع(
Ox +))۱0+)0(۷۵ =
@PO+PO=(W-0)(O-C)+PC+OO
(x)= BCx? +((PW-B)(D-C)+PO+OO px) + BO
(x)= BCx* +((B-B)(O-C)+@C+OO)x)+ BO
سه ضرب لازم است. ٠
D(a)=O (al) +00
1(- 9۳۰
عملکرد بهتر است. ٠»
ضرب اعداد صحیح بزرگ:2-9الگوریتم
v وu ضرب دو عدد صحیح بزرگ:مسئله
large _ integer prod ( large_integer u, large_integer v)
{
large_inreger x , y , w , z ;
int n , m ;
n = maximum(number of digits in u,number of digits in v)
if (u = = 0 || v = = 0)
return 0 ;
else if
(n < = threshold)
return u × v obtained in the usual way;
else {
m = Į n / 2 ⌡;
x = u divide 10 ^ m ; y = rem 10 ^ m;
w = v divide 10 ^ m ; z = rem 10 ^ m;
return prod (x ,w) × 10 ^2m + ( prod ( x, z) + prod
(w, y )) × 10 ^ m + prod ( y, z);
}
}
تحلیل پیچیدگی زمانی در بدترین حالت برای ا لگوریتم( ضرب اعداد صحیح)
عمل اصلی :دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در
هنگام جمع کXردن ،تفریق کردن ،یا انجام اعمال، divide 10 ^ m
rem 10 ^mیا × .m ^ 10هر یک از این اعمال را mبار انجام می دهد.
اندازه ورودی ، n :تعداد ارقام هر یک از دو عدد صحیح.
به ازای n > sکه nتوانی از 2استT ( n ) = 4 T (n / 2) + cn
T(s)=0
) T ( n ) Є θ ( n²
در چه مسائلی نمی توان از روش تقسیم وحل
استفاده کرد
• -1مسایلی با اندازه nبه چند زیر مسئله تقسیم می شود که
اندازه زیر مسئله ها نیز تقریبا برابر n Xاست.
زXمان نمایی ایجاد می کند.
• -2مساله ای با اندازه nتقریبا به اندازه nزXیر مسئله با
اندازه n/cکه در آن cثابت است تقسیم می شود.
زمان nlognایجاد می کند.
فرش کردن صفحه شطرنجی
• ابعاد صفحه 2k*2kاست.
• موزاییک به شکل Lاست.
• در بدترین حالت یکی از خانه ها خالی می ماند.
•
4*4
ضرب چند جمله ای ها
• P(x)=anxn+an-1xn-1+an-2xn-2 . . . a2x2 + a1x1+a0
• Q(x)=bnxn+bn-1xn-1+bn-2xn-2 . . . b2x2 + b1x1+b0
• R(x)= P(x)Q(x)
• P(x)=anxn+an-1xn-1+an-2xn-2 . . . a2x2 + a1x1+a0
• Q(x)=bnxn+bn-1xn-1+bn-2xn-2 . . . b2x2 + b1x1+b0
• R(x)= P(x)Q(x)=
a0b0 + a0b1x1+a0b2x2 + . .+ a0bn-2xn-2 + a0bn-1xn-1 + a0bnxn
a1b0x+ a1b1x2+a1b2x3 + . .+ a1bn-2xn-1 + a1bn-1xn + a1bnxn+1
a2b0 x2+ a2b1x3+a2b2x4 + . .+ a2bn-2xn + a2bn-1xn+1 + a2bnxn+2
.
.
.
• R(x)= P(x)Q(x)=
a0b0 + a0b1x1+a0b2x2 + . .+ a0bn-2xn-2 + a0bn-1xn-1 + a0bnxn
a1b0x+ a1b1x2+a1b2x3 + . .+ a1bn-2xn-1 + a1bn-1xn + a1bnxn+1
a2b0 x2+ a2b1x3+a2b2x4 + . .+ a2bn-2xn + a2bn-1xn+1 + a2bnxn+2
.
.
.
a 0b 0
• R(x)= P(x)Q(x)=
a0b0 + a0b1x1+a0b2x2 + . .+ a0bn-2xn-2 + a0bn-1xn-1 + a0bnxn
a1b0x+ a1b1x2+a1b2x3 + . .+ a1bn-2xn-1 + a1bn-1xn + a1bnxn+1
a2b0 x2+ a2b1x3+a2b2x4 + . .+ a2bn-2xn + a2bn-1xn+1 + a2bnxn+2
.
.
.
a0b0 + (a1b0+a0b1)x +
• R(x)= P(x)Q(x)=
a0b0 + a0b1x1+a0b2x2 + . .+ a0bn-2xn-2 + a0bn-1xn-1 + a0bnxn
a1b0x+ a1b1x2+a1b2x3 + . .+ a1bn-2xn-1 + a1bn-1xn + a1bnxn+1
a2b0 x2+ a2b1x3+a2b2x4 + . .+ a2bn-2xn + a2bn-1xn+1 + a2bnxn+2
.
.
.
a0b0 + (a1b0+a0b1)x + (a0b2 + a1b1 + a2b0)x2 +
• R(x)= P(x)Q(x)=
a0b0 + a0b1x1+a0b2x2 + . .+ a0bn-2xn-2 + a0bn-1xn-1 + a0bnxn
a1b0x+ a1b1x2+a1b2x3 + . .+ a1bn-2xn-1 + a1bn-1xn + a1bnxn+1
a2b0 x2+ a2b1x3+a2b2x4 + . .+ a2bn-2xn + a2bn-1xn+1 + a2bnxn+2
.
.
.
a0b0 + (a1b0+a0b1)x + (a0b2 + a1b1 + a2b0)x2 + . . .
k
•k XمX اX=جملهci=
aibk-i
i=0
•R(x)= P(x)Q(x)=
2
n
i=0
c ix i
cixi
2
n
i=0
نیاز به دو forبرای محاسبه بنابراین :
)O(n2
=)•R(x)= P(x)Q(x
روش تقسیم وحل
برای ضرب چند جمله ایها
)• R(x)= P(x)Q(x
• P(x) =Ax(n/2) + B
• Q(x) = C x(n/2) + D
Xست
• A , B ,C ,Dجند جمله XاXیاز مرتبه n/2 Xا .
)R(x)= P(x)Q(x)=(Ax(n/2)+B)(Cx(n/2) +D
= ACxn +(AD+BC)x(n/2)+BD
• تعداد ضرب ها 4تا است.
T(n)=4T(n/2)+cnعمل ضرب
)T(n)=θ(n2
• الگوریتم بهتر نشده است.
•
•
•
•
• R(x)= P(x)Q(x)=(Ax(n/2)+B)(Cx(n/2) +D)
•
= ACxn +(AD+BC)x(n/2)+BD
• AD+BC=(A-B)(D-C)+AC+BD
• R(x)= ACxn +((A-B)(D-C)+AC+BD)x(n/2)+BD
• R(x)= ACxn +((A-B)(D-C)+AC+BD)x(n/2)+BD
.• سه ضرب الزم است
• T(n)=3T(n/2)+cn
• T(n)= θ(nlog 3)
.• عملکرد بهتر است