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


#1

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


#2

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

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


#3

Домашнее задание с возведением в степень 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 писать)


#4

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


#5

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


#6

Домашнее задание с возведением в степень 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.

#7

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


#8

6


#9

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


#10

а если я напишу этот случай отдельным условием? это будет считаться или есть ещё какие-то хитрые случаи?


#11

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


#12

Домашнее:

  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.

#13

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

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


#14

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


#15

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


#16
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)…


#17

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


#18

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


#19

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


#20
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}