|
Дано действительное число а и целое число n>=0. Вычислить a^n (a в степени n).
В первой программе A2_20a реализован самый простой алгоритм: присвоим p:=1; (строка 7), а затем умножим p n раз (проверка в строке 8) на a. Получим a^n. Если n=15 – умножать будем 15 раз (цикл в строках 8-12), если n=100 – умножать будем 100 раз, а если n=1000 – умножать будем 1000 раз. Все очень просто. Во второй программе A2_20b реализован более сложный алгоритм. В этом алгоритме учитывается четность или нечетность степени a. Например, если n=15, следует вычислять a^15= a^14*a, а если n=14,то a^14= a^7* a^7. В этой программе при n=15 цикл 8-14 будет выполняться 7 раз, при n=100 – 9 раз, а при n=1000 – 15 раз. Ощутимая разность в количестве вычислений по сравнению с первой программой. Третья программа A2_20c это программа A2_20b, в которую добавлена переменная m для подсчета количества выполнений цикла в строках 9 – 16. Примечание. Хотя программа A2_20b намного сокращает количество действий , по сравнению с программой A2_20a, она все равно не оптимальна. Например, используя только операцию умножения (*) и присваивания a^15 можно получить за 5 умножений, а не за 7, как выполняет программа A2_20b (проверьте программой A2_20c). Попробуйте вычислить (вручную, на бумаге) a^15, используя только 5 операций умножения и операции присваивания.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
Program A2_20a;
Var
a,p:real;
n,k:integer;
BEGIN
readln(a,n);
p:=1; k:=n;
while (k>0) do
begin
p:=p*a;
k:=k-1;
end;
writeln(p);
readln;
END.
|
//Program A2.20a;
#include <iostream>
using namespace std;
int main()
{
double a,p;
int n,k;
cin>>a>>n;
p=1; k=n;
while(k>0)
{
p=p*a;
k--;
}
cout << p << endl;
return 0;
}
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
Program A2_20b;
Var
a,b,p:real;
n,k:integer;
BEGIN
readln(a,n);
k:=n; p:=1; b:=a;
while (k>0) do
begin
if (k mod 2=0) then
begin k:=k div 2; b:=b*b; end
else
begin k:=k-1; p:=p*b; end;
end;
writeln(p);
readln;
END.
|
//Program A2.20b;
#include <iostream>
using namespace std;
int main()
{
double a,b,p;
int n,k;
cin>>a>>n;
k
= n; p = 1; b=a;
while(k>0)
{
if(k%2==0) {k=k/2; b=b*b;}
else { k--; p=p*b;}
}
cout << p<< endl;
return 0;
}
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
Program A2_20c;
Var
a,b,p:real;
n,k,m:integer;
BEGIN
readln(a,n);
k:=n; p:=1; b:=a;
m:=0;
while (k>0) do
begin
m:=m+1;
if (k mod 2=0) then
begin k:=k div 2; b:=b*b; end
else
begin k:=k-1; p:=p*b; end;
end;
writeln(p,' ',m);
readln;
END.
|
//Program A2.20c;
#include <iostream>
using namespace std;
int main()
{
double a,b,p;
int n,k,m=0;
cin>>a>>n;
k
= n; p = 1; b=a;
while(k>0)
{ m++;
if(k%2==0) {k=k/2; b=b*b;}
else { k--; p=p*b;}
}
cout << p<<" "<<m<<endl;
return 0;
}
|
|
