(1 курс ФИИТ) ОП - лекц - 2015 (устарело)

Архив 2015/16
#1

Поддержка лекционной части курса Основы программирования

1 лайк
Алгоритм возведения в степень
#2

Был ли уже условный оператор? И если нет, то когда планируется?

#3

По поводу бонусных трех баллов. Необходимо было написать универсальный алгоритм возведения х в степень n. Вот мой вариант.

var
    x, n, i: integer;
    xn: real;
    
begin
    write ('Число: ');
    readln (x);
    write ('Степень: '); 
    readln (n);
    xn := 1;
    i := 0;
    while i < abs(n) do 
      begin
        xn := xn * x;
        i := i + 1
      end;
    if n < 0 then
        xn := 1 / xn;
    writeln (xn:10:5);
end.
#5

Алгоритм возведения числа в натуральную степень(ДЗ):

begin
  var x := readreal;
  var n := readinteger;
  var res : real := 1;
  while n > 0 do
  begin
    if (n and 1 = 0) then
    begin
      x *= x;
      n := n shr 1;
    end
    else
    begin
      res *= x;
      n -= 1;
    end;
  end;
  print(res);
end.
#6 
function p (x,y:integer):integer;
var m: integer;
begin
m := 1;
while (y > 0) do
begin
if (y and 1 = 1) then 
m := m * x;
x := x + x;
y := y shr 1;
end;
p := m;
end;
#7

Не работает. Деление на 2 выполняется и для четных, и для нечетных Y. И сложение там не нужно.

#8

“y and 1 = 1” - проверка на четность. я правильно тебя понял? если да, то почему именно таким образом?

#9

да,увидела,спасибо

#10

верно,планировалось именно как проверка на четность.По принципу “почему бы и нет”

#11 
var
  x, y, st, r: real;
  m: integer;

begin
  readln(x, y);
  if (x < 0) then 
    st := (-1) * Exp(y * Ln(Abs(x))) 
  else
  if (x > 0) then 
    st := Exp(y * Ln(Abs(x))) 
  else
    st := 0;
  m := round(y);
  if (m mod 2 = 0) then 
    R := Abs(st);
  if (y = 0) then 
    st := 1;
  writeln(st);
end.

как вариант через экспоненту/логарифм

#12

Это же: power(x,n); Вычисление логарифма и экспоненты требует намного больше ресурсов, чем умножение.

#14

Возведение числа в натуральную степень

begin
  var x := readreal;
  var n := readinteger;
  var power : real := 1;
  while n > 0 do
  begin
    if (n and 1 = 1) then
      power *= x;
    x *= x;
    n := n div 2;    
  end;
  println(power);
end.
#15 
//Возможно есть лучший алгоритм, но хоть работает и уменьшает кол-во умножений
var
x,n,k:integer;
s,m:real;
a,b,dis:integer;
t1,t2,t3:BigInteger;

Begin 

  write('Основание:');
  readln(x);

  write('Степень(>=4):');
  readln(n);

  t1:=1;
  t2:=1;
  t3:=1;




  s:=Trunc((ln(Trunc(n/2))/ln(2)));
  
  m:=Trunc(n/(2*s));
  
  dis:=Trunc(n-2*m*s);
  
  a:=dis div Trunc(s);
  b:=dis mod Trunc(s);
  
  for var i:=1 to Trunc(s) do
  t1*=x;
  
  for var i:=1 to Trunc(m) do
  t2*=t1;
  
  t3:=t2*t2;
  
  for var i:=1 to a do 
  t3*=t1;
  
  for var i:=1 to b do 
  t3*=x;
  
  k:=Trunc(s)-1+Trunc(m)-1+1+a+b;
  
  writelnFormat('{0}^{1}={2}',x,n,t3);
  writeln('Количество умножений:',k);

end.  

{
Лог:
Основание:2
Степень:6
2^6=64
Количество умножений:3

Основание:3
Степень:897
    3^897=95009161123575509487351704781088869938617224968466170303382900843729981391283919691164882664197959088504417084098297169055790972369938213220938911078242284999919071499869139981768195924855915761275737321875981297858361822710733623890018339420314312678414112106464281875678934335899626687582223979042456389921303116179345175869062457591662665121821558114220781174709278473033080178547607090094610212237198288445045715853644136963
Количество умножений:64
}
#16

Вот мой вариант программы ( правда,не уверенна,что она будет быстро работать,да и памяти уходит много):

function Power(x, n: integer): integer;
begin
  if n = 0 then result := 1
  else if n = 1 then result := x
  else
  if n = 2 then result := x * x
  else
  if (n mod 2) = 0 then
    result := Power(x, n div 2) * Power(x, n div 2)
  else
    result := Power(x, (n - 1) div 2) * Power(x, (n - 1) div 2) * x;
end;

begin
  var x := ReadInteger('Введите х:');
  var n := ReadInteger('Введите степень :');
  writeln('Получившееся число:', Power(x, n));
end.
#17

Уважаемые студенты!

Пожалуйста, используйте средства оформления кода на форуме:

```
begin 
    мой код
end.
```
#18

Работает на всех случаях, получился громоздкий, но толко на вид. Количество переменных минимально, и сам упакован в функцию для удобства. Надеюсь он лучше, чем просто power().

function Xpower(x,n:integer):integer; //Автор: Тактаров Евгений 1.9 дата: 15.09.15
 var t:integer;
begin
  If n mod 2=0 then
  begin
   t:=x*x;
   n:=n div 2;
   while n>1 do
    begin
     t:=t*t;
     n:=n div 2;
    end;
  end
   else 
    begin
     t:=x;
     while n>1 do
       begin
        t:=t*t;
        n:=n div 2;
       end;
       t:=t*x;
    end;
  result:=t;
  if n=0 then result:=1;
end;
begin
 writeln(Xpower(2,9)); // тестовое исполнеие функции - можно вставить значения для проверки
 
end.
#19

If сегодня уже был.

#20

О, вот хорошо, спасибо.

#21

2Sirenity Это конечно очень простой вариант, требующий n-1 умножения.

2Eselkopf Это уже лучше - этот алгоритм основан на степени двойки. Не оптимален, но хорош и прост

2Anastasiya_Belova Первый алгоритм я не понял, там внезапно возникает сложение x := x + x; - сложение нельзя использовать Второй алгоритм использует exp и ln, что конечно для чисел правильно, но задача стояла - использовать только умножения. Если x - многочлен или матрица, логарифм Вы не возьмёте. y := y shr 1; - проще y := y div 2. И аналогично чётность. Трудно читать

2Ilya_Yakubovskij Опять-таки, этот алгоритм основан на делении степени на 2 - это просто и хорошо, но неоптимально. x^15 как раз - пример, на котором это рушится

2Nan - хорошая попытка, но ничего не объясняется, поэтому трудно разобрать. Для x^15 сколько умножений требуется?

2Haku Хороший код, та же идея - делить на 2 степень если n четно, но Вы повторно вычисляете например Power(x, n div 2), поэтому у Вас в итоге n умножений - надо использовать функцию sqr или промежуточную переменную

2je_day Код немного закрученный, но, видимо, работает неверно - по ветке n- четно Вы далее предполагаете, что и после деления на 2 n останется четным

В любом случае - спасибо всем, кто принял участие в решении! Оперативно! Молодцы!

#22 
var shag: integer;

function pow(x: real; n: integer): real;
begin
  var res: real;
  res := 1;
  if ((n and 7) = 7) and (((n mod 3) = 0) or ((n mod 3) = 1)) then
  begin
    var t: array [0..100] of real;
    var i := 6;
    t[1] := x;
    var j := 3;
    t[j] := x * x * x;
    shag := 2;
    while i <= n do
    begin
      i *= 2;
      j *= 2;
      t[j] := t[j div 2] * t[j div 2];
      shag += 1;
    end;
    res := t[j];
    i := i div 2;
    while (i < n) and (j > 1) do
    begin
      j := j div 2;
      if (i + j) <= n then
      begin
        res *= t[j];
        shag += 1;
        i += j;
      end;
    end;
  end
  else
  begin
    var t: array [0..100] of real;
    var i := 4;
    t[1] := x;
    var j := 2;
    t[j] := x * x;
    shag := 1;
    while i <= n do
    begin
      i *= 2;
      j *= 2;
      t[j] := t[j div 2] * t[j div 2];
      shag += 1;
    end;
    res *= t[j];
    i := i div 2;
    while (i < n) and (j > 1) do
    begin
      j := j div 2;
      if (i + j) <= n then
      begin
        res *= t[j];
        shag += 1;
        i += j;
      end;
    end;
  end;
  result := res;
end;

begin
  var x := ReadReal('Введите число: ');
  var n := ReadInteger('Введите степень: ');
  var res1 := pow(x, n);
  writeln(res1);
  writeln(shag);
end.