Курс Основы программирования (лекции) 1 семестр 2018-19 гг

Здесь - материалы по курсу, обсуждение тем курса и пр.

1 лайк

Презентация первой лекции 01_Begin.pdf (472,2 КБ)

Официальная шпаргалка Шпаргалка PascalABC.NET 2018.pdf (130,2 КБ)

Домашнее задание с возведением в степень n. Основная идея заключается в переводе степени в двоичную систему исчисления по ходу решения. Не знаю, к какому типу привести переменную answ, чтобы в нее помещался ответ больший, чем 2^32 :frowning:

begin 
  var answ := 1; 
  var (a, n) := ReadInteger2('Введите число и степень:'); 
  var (a1, n1) := (a, n); 
  while (n1 > 0) do 
  begin  
    if n1 mod 2 <> 0 then answ *= a1; 
    a1 *= a1; 
    n1 := n1 div 2 
  end; 
  Println($'{a}^{n}={answ}') 
end.

(код почему-то не подсвечивается, объясните, пожалуйста, как его правильно вставлять, пришлось везде br писать)

1 лайк

Надо выделять код тремя символами ```

1 лайк

2 сообщения перенесены в тему Болталка PascalABC.NET

Домашнее задание с возведением в степень n. Возводя в квадрат a, ищу такое а в степени s, при котором s - степень двойки и s < n. Затем иду обратно по полученному массиву, прибавляя к s степени двойки и получая число a в данной степени, пока я не получу степень n.

var  
s, n, a: integer;  
begin  
Read (a,n);  
var b: array of biginteger;  
SetLength(b,n+1);  
b[1] := a; s:= 1; var i := 2;  
while s*2 <= n do  
  begin  
  b[i] := b[i-1] * b[i-1];  
  s*= 2;  
  i+=1;  
  end;  
var m: integer;  
m := s div 2;  
i-=1;  
if s = n then  
  begin  
  println( b[i] );  
  exit;  
  end;  
var c := b[i]; i-=1;  
while i >= 1 do  
  begin  
  if s+m<=n then  
    begin  
    s += m;  
    c *= b[i];  
    end;  
  if s=n then  
      begin  
      println( c );  
      exit;  
      end;  
  m:=m div 2;  
  i-=1;  
  end;  
println( c );  
end.

Да, понятно. А сколько умножений по вашему алгоритму нужно будет для a^15?

Ну, то есть, Ваш алгоритм находит не минимальное число умножений, а близкое к минимальному. На лекциях приводился алгоритм с 5 умножениями

В том-то и дело, что наиболее оптимальное количество умножений не связано со степенью двойки.

Домашнее:

  var numb,stepe :real;
  var r: longint;
  writeln('Введите число и его показатель (по очереди):');
  ///Использованы 8 битные real и longint, при необходимости можно взять более объемные типы переменных
  read(numb,stepe);
  if (numb < 0) 
    then numb := (-1)*Exp(stepe*Ln(Abs(numb)))
  else if (numb > 0) 
    then numb := Exp(stepe*Ln(Abs(numb)))
  ///На основе стандартной функции power, всего два или одно умножение, в зависимости от знака перед числом
  else numb:=0;
  r:=round(stepe);
  if (r mod 2) = 0
    then numb:=Abs(numb);
  if (stepe = 0) 
    then numb :=1;
  ///Учитываем чётность показателя степени или возможное равенство нулю
  print(numb);
end.

Проблема в том, что в стандартных exp и ln сидит много операций умножения.

И - набирайте код, окаймляя его ```

А где брать домашнее задание?

По лекциям оно говорилось на лекции

var k:BigInteger;
var f:real;
var n:=ReadReal('Введите возводимое число');
var i:=ReadInteger('Введите степень числа');
f:=n;
for k:=1 to (i-1) do
    n:=n/(1/f);
writeln(n);
end.

Чисто технически, решение вообще без умножения (зависит от того, как деление реализовано в Pascal)…

Деление запрещено :slight_smile: Скажем, надо возвести в степень квадратную матрицу

Понятно, я уж думал, можно будет пройти курс просто по выкладываемым Вами презентациями, даже не будучи студентом вуза.

Нет, этот топик только для студентов ФИИТ. Внимательнее к этому относитесь.

function maxnd (number:integer):integer;
begin 
var i:integer;
var mx:=1;
for i:=1 to (number-1) do begin
 if (number mod i = 0) and (i>mx) then 
 maxnd:=i;
 end;
end;{функция для нахождения наибольшего нетривиального делителя}

Begin
var st:=readinteger('Введите натуральную степень числа а');
var st1:=st;{запоминаем значение для красивого вывода}
var max:integer;
var count:real;
count:=0;
while st>1 do begin
 max:=maxnd(st);
 if max>1 then begin
  count:=count+st/max-1;
  st:=max
  end
 else begin
  count:=count+1;
  st:=st-1; 
  end
end;
println('Число а в стпени',st1,'можно получить из числа а при помощи',count,'умножений');
end.

{Коротко о принципе работы:в цикле при каждой итерации проверяем, есть ли у st нетривиальные делители, если есть, то увеличиваем счётчик на число умножений, которое необходимо для того,чтобы получить st из его наиольшего нетривиального делителя max и присваиваем st значение max. Если нетривиальных делителей нет,то уменьшаем st на 1, а счётчик увеличиваем на 1. Цикл повторяется, пока st не станет равно 1}

Задача - напомню - была другая. Не вычислить количество умножений, а именно перемножить, используя это минимальное количество.

По форматированию кода - пишите begin на новой строке

1 лайк
function maxnd (number:integer):integer;
begin 
var i:integer;
var mx:=1;
for i:=1 to (number-1) do begin
 if (number mod i = 0) and (i>mx) then 
 maxnd:=i;
 end;
end;{функция для нахождения наибольшего нетривиального делителя}

Begin

var x:int64; 
Writeln('Введите число x');
Readln (x);
var st:=readinteger('Введите натуральную степень числа x');
var st1:=st;{запоминаем значение для красивого вывода}
var max,i:integer;
var a:array [0..10000] of integer;


while st>1 do 
begin
 max:=maxnd(st);
 if max>1 then 
 begin
  repeat
  a[i]:=max;
  i:=i+1;
  st:=st-max
  until st=max;
  end
 else 
 begin
  a[i]:=1;
  i:=i+1;
  st:=st-1; 
  end
end;

var j:integer;
Var x1,xt:int64;
Var t:integer;
(x1,xt,t):=(x,x,1);



for j:=(i-1) downto 0 do 

begin
if a[j]=t then
 begin
 x:=x*xt;
 println(x);
 end
 
else
 if a[j]=1 then 
 begin
 t:=1;
 xt:=x1;
 x:=x1*x;
  println(x);
 end
 
 else
 begin
 xt:=x;
 x:=x*x;
 println(x);

 t:=a[j];
 end;
end;

end.

Изменил программу. Промежуточные степени записываются в массив, затем в цикле на основе анализа элементов массива производится умножение, причём для получения конечного значения используется наименьшее число умножений.