مرجع دانلود پاورپوینت های درسی

حجم فایل : 56.8 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 23
بنام خدا الگوریتم ضرب اعداد صحیح بزرگ مسئله: ضرب دو عدد صحیح بزرگ u و v

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);
}
} تحلیل پیچیدگی زمانی در بدترین حالت برای ا لگوریتم( ضرب اعداد صحیح) عمل اصلی: دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در
هنگام جمع کردن ، تفریق کردن، یا انجام اعمالdivide 10 ^ m ،
rem 10 ^m یا ×10 ^ m. هر یک از این اعمال را m بار انجام می دهد.
اندازه ورودی: n ، تعداد ارقام هر یک از دو عدد صحیح.

به ازای n > s که n توانی از 2استT ( n ) = 4 T (n / 2) + cn
T ( s ) = 0

T ( n ) Є θ ( n² )
در چه مسائلی نمی توان از روش تقسیم وحل استفاده کرد 1- مسایلی با اندازه n به چند زیر مسئله تقسیم می شود که اندازه زیر مسئله ها نیز تقریبا برابر n است.
زمان نمایی ایجاد می کند.

2- مساله ای با اندازه n تقریبا به اندازه n زیر مسئله با اندازه 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
.
.
.
a0b0

R(x)= P(x)Q(x)=
a0b0 + a...