2-20r · informatik.az

Дано действительное число а и целое число 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 операций умножения и операции присваивания.

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;

}

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;

}

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;

}