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


#69

А в следующем году, если тогда напомнить, не хотите рассказывать?


#70

Нет. Если Вам нужно это для практики - расскажите на практике.


#71

Да мы-то расскажем, но там неприятная история, особенно если с System.Enum.TryParse. Так что я вас понимаю :slight_smile:


#72

А вот ещё вопрос: не планируется ли показывать на лекциях вызов обобщённых подпрограмм с явным указанием типа-аргумента? Там вот амперсанд этот…


#73

Студенты как один утверждают, что на лекциях не было слова nil (в теме массивов). Честно говоря, я нахожусь в растерянности.


#74

А есть новая шпаргалка по массивам?


#75

Юлии Вячеславовне надо поставить двойку. Цикл foreach записывается так:

foreach x : T in p do ...
// или
foreach var x in p do ...

@Admin, напомните, пожалуйста, чтобы исправили в начале следующей лекции, а то я for вместо foreach написала.


#76

И ещё: не используйте цикл foreach до следующей лекции. На самом деле последний алгоритм, который мы записали, неправильный. Что в нём не так, узнаете в следующий раз :wink:


#77
// реализован цикл сдвиг влево и вправо
{преимущества с приведенным выше:  можно вводить любое k
недостатки: используется дополнительный массив}

    begin
      var a := Arr(1, 2, 3, 4, 5, 6, 7);
      var a1:= copy(a);
      var k := 20;
      
      var n := a.Length;  
      for var i:=0 to n - 1 do
        a1[(i+k) mod n]:=a[i];
      
      Writeln(a1);
      a1:= Arr(1, 2, 3, 4, 5, 6, 7);
      
      for var i:=0 to n - 1 do
        a1[i]:=a[(i+k) mod n];
      
      Writeln(a1);
    end.

#78

Я конечно запоздал. Вот, что произойдет если переполнять строку:


Spoilers:

как и ожидалось, программа вылетает с искулючением на 3гб (что и свойсвенно 32 битной программе). Исключение возникает из-за ограничения строки. Вот вариант с массивом из строк

Ошибка времени выполнения: StackOverflowException: Программа завершена из-за переполнения программного стека


#79

Вот здесь Метод Гаусса:

type
  TypeSTR=(Simple, Identity, Fail);

{определяет тип строки}
function DetermineString(m: array [,] of integer; i : integer): TypeSTR;
begin
  Result:=Identity;
  for var j:=0 to m.GetLength(1) - 2 do
    if m[i, j]<>0 then 
      begin
        Result:=Simple;
        break
      end;
  if (m[i, m.GetLength(1) - 1] <> 0) and (Result=Identity) then Result:=Fail;
end;

{проверяет является столбец  нуль-столбцом}
function IsNullColumn (m: array [,] of integer; j : integer): boolean; 
begin
  Result:=True;
  for var i:=0 to m.GetLength(0) - 1 do
    if m[i, j] <> 0 then 
      begin
        Result:=False;
        exit
      end;
end;

{проверяет является столбец  нуль-столбцом c какой-то строчки}
function IsNullColumn (m: array [,] of integer; j, NumberOfMainStrings : integer; var fpI: integer): boolean; 
begin
  Result:=True;
  for var i:=NumberOfMainStrings to m.GetLength(0) - 1 do
    if m[i, j] <> 0 then 
      begin
        Result:=False;
        fpI:=i;
        exit
      end;
end;

{меняет строки} 
procedure SwapStrings(m: array [,] of integer; i1, i2: integer);
begin
  for var j:=0 to m.GetLength(1) - 1 do
    Swap(m[i1, j], m[i2, j])
end;

procedure SumTwoSringWithTwoK(a: array [,] of integer; imain, i1, kmain, k1: integer);
begin
  for var j:=0 to a.GetLength(1) - 1 do
    a[i1, j] := a[i1, j] * k1 + a[imain, j] * kmain 
end;

{присваевает побочной строке разность}
procedure MinusMain(m: array [,] of integer; fpJ, imain, i: integer);
begin
  var kp:=(-1)*m[imain, fpJ];
  var km:=m[i, fpJ];
  for var j:=fpJ to m.GetLength(1) - 1 do
    m[i, j]:= m[i, j] * kp + km * m[imain, j]; 
end;

procedure MotherOfKuzma(m: array [,] of integer; fpJ, imain: integer);
begin
  var kp:=(-1)*m[imain, fpJ];
  if kp<>0 then
  for var i:=imain + 1 to m.GetLength(0) - 1 do
  begin
  
  
    var km:=m[i, fpJ];
    if km<>0 then 
    for var j:=fpJ to m.GetLength(1) - 1 do
             m[i, j]:= m[i, j] * kp + km * m[imain, j];
  end; 
end;

function FindLastNotNullElemOfI_sString(m: array [,] of integer; i: integer; var fpJ: integer): boolean;
begin
  Result:=False;
  for var j:=m.GetLength(1) - 1 downto 0 do
    if m[i, j]<>0 then
      begin
        Result:=True;
        fpJ:=j
      end;
end;

procedure GrandmotherOfKuzma(m: array [,] of integer);
begin
  
  for var i:=m.GetLength(0) - 1 downto 1 do
  begin
    var fpJ: integer;
    if FindLastNotNullElemOfI_sString(m, i, fpJ) then 
    begin
      var kp:=(-1)*m[i, fpJ];
      
      for var i1:=i-1 downto 0 do
        if m[i1, fpJ]<>0 then 
          SumTwoSringWithTwoK(m, i, i1, m[i1,fpJ], kp)
      
      
      
      
    end;
  end; 
end;

{перепресваивает строку (Ci1:=Ci2)
procedure AssignI1StrI2Str(m: array [,] of integer; i1, i2: integer);
begin
  for var j:=0 to m.GetLength(1) - 1 do
    a[i1, j]:= a[i2, j]
end;

Удалает к строку
procedure DeleteKString(m: array [,] of integer; k: integer);
begin
  for i:=k to m.GetLength(0) - 1 do
    AssignI1StrI2Str(i, k+1);
  SetLength(m, m.GetLength(0) - 1, m.GetLength(1))
end;}

procedure TringleForm(m: array [,] of integer; var Res: string);

begin
  
      
    //Ищем не нулевой элемент в минимальной строке 
    var NumberOfMainStrings:=0;
    for var j:=0 to m.Getlength(1) - 2 do 
    begin
      //проверяем строки
      for var i:=NumberOfMainStrings to m.GetLength(0) - 1 do
      if DetermineString(m, i) = Fail then
      begin
        Res:='СЛУ не определена';
        exit
      end;
      
      var fpI:=-1;
      if Not(IsNullColumn(m, j, NumberOfMainStrings, fpi))  then
      begin
        MotherOfKuzma(m, j, fpi);
        NumberOfMainStrings+=1
      end;
      
    end;
       
end;

procedure DiagonalForm(m: array [,] of integer; var Res: string);

begin
  
  TringleForm(m, Res);

  if res<>'СЛУ не определена' then 
  begin
    GrandmotherOfKuzma(m)
    
    
    
    
    
  end else
    begin
      Res:='СЛУ не определена';
    end;
      
    
       
end;

function Answer(m: array [,] of integer; i, j: integer; var s: set of integer): string;
begin
  Result:=m[i, m.GetLength(1) - 1].ToString;
  for var jA:=j + 1 to m.GetLength(1) - 2 do
    if m[i, jA]<>0 then 
    begin
      Result+=' -'  + m[i, jA].ToString + ' * x[' + jA.ToString + ']';
      Include(s, jA);
    end;
    
    
  var res: integer;
  if integer.TryParse(Result, Res) and (res mod m[i, j] = 0) then Result:=(res div m[i, j]).ToString
    else if m[i, j] <> 1 then  Result:='( ' + Result + ' )/' + m[i, j].ToString;
    Result:='x[' + j.ToString + ']' + ' = ' + Result
  
end;

function FindIndexOfIdinityStrings(m: array [,] of integer): set of integer;
begin
  for var i:=0 to m.GetLength(0) - 1 do
    if DetermineString(m, i) = Identity then Include(Result, i);
end;

function FindIndexOfNotDetermineX (m: array [,] of integer): set of integer;
begin
  for var j:=0 to m.GetLength(1) - 2 do
    if IsNullColumn(m, j) then Include(Result, j);
end;


function  Method (m: array [,] of integer): array of string;
label 1;
begin
var Res: string;
DiagonalForm(m, Res);


if res<>'СЛУ не определена' then 
  begin
    Result:=new string[m.GetLength(1) - 1];
    var IndexOfNotDetermineStrings:=FindIndexOfIdinityStrings(m);
    var IndexOfNotDetermineX:=FindIndexOfNotDetermineX(m);
    
    
    {for var i:=0 to m.GetLength(1) - 1 do
      if not (i in IndexOfNotDetermineX) then
        Result[i]:=Answer(m, i, i, IndexOfNotDetermineX);}
    
    var j:=0;
    for var i := 0 to m.GetLength(0) - 1 do
    begin
      
      while (j in IndexOfNotDetermineX) or (j>m.GetLength(1) - 2) and (m[i, j]=0) do j+=1;
      
      if j>m.GetLength(1) - 2 then goto 1;
      if not (i in IndexOfNotDetermineStrings) then
      Result[j]:=Answer(m,i,j, IndexOfNotDetermineX);
      j+=1
    end;
    1:  
    
    
    foreach var i: integer in IndexOfNotDetermineX do 
      Result[i]:='x[' + i.ToString + ']  - свободная переменная';
  end
      
      
      // Делаем свободные элементы
    {Foreach var x: integer in  do
    Result[x]:='x[' + x.ToString + ']'}
  
      
  else 
  begin
    Result:=new string[1];
    Result[0]:='СЛУ не определена';
  end;
end;




function ARRMatrix(n, m: integer; params a: array of integer): array [,] of integer;
begin
  Result:=new integer[n, m];
  for var i:=0 to n - 1 do
    for var j:=0 to m - 1 do
      Result[i, j]:=a[i*(n+1) + j];
end;
procedure ARRPrint(a: array[,] of integer);
begin
  for var i:=0 to a.GetLength(0) - 1 do
    begin
      for var j:=0 to a.GetLength(1) - 2 do
        print(a[i, j]);
      print('  |', a[i, a.GetLength(1) - 1]);
      write(NewLine);
    end;
end;

begin
  var a: array[,] of integer;
  a:=ArrMatrix(2, 3,
    1, 1, 1,
    1, 1, 0);
  
  ARRPrint(a);
  var Re: string;
  write(newline);
  {TringleForm(a, Re);
  ARRPrint(a);
  write(re);
  write(newline);}
  DiagonalForm(a, Re);
  write(newline);
  ARRPrint(a);
  write(re);
  
  write(newline);
  var k:=Method(a);
  
  k.PrintLn(newline);

end.

Чуть позже поправлю и уберу лишнее


#81

Можете подсказать почему поменялись немного(+оформление другое) вопросы экзамена по основам программирования? Для тех кто будет пересдавать его,теперь нужно готовиться по обновленному варианту ?


#82

А какой вариант Вы смотрите? Вроде ничего не менялось.


#85

Функция Аккермана

function Akkerman(m,n:integer):integer;
begin
  if m=0 then
    Result:=n+1
  else
    if n=0 then
      Result:=Akkerman(m-1,1)
    else
      Result:=Akkerman(m-1,Akkerman(m,n-1));
end;

begin
  var m,n:integer;
  Read(m,n);
  Print(Akkerman(m,n));
end.

Подсчет А(2,3) и А(3,4) произошел быстро. Однако А(4,5) не посчиталось - переполнение программного стека. Да и не думаю, что хотя бы на один экран поместилось бы число 2^2^2^2^65536 Также переполнение программного стека вызывает А(4,1), хотя число более скромное: 65536 Изменение типа данных с integer на biginteger (ну а вдруг бы сработало) результата не принесло.


#86

Хорошо. Жаль, что программный стек переполнился.


#87

Вообще-то 65533. Хаскель посчитал его без увеличения стека, хотя медленно: за 15 секунд.

a :: Int -> Int -> Int 
a m n | m == 0    = n+1
      | n == 0    = a (m - 1) 1
      | otherwise = a (m - 1) $ a m (n-1)

main = print $ a 4 1

#88

Наверное оптимизировал концевую рекурсию


#89

Меня спрашивали на лекции. Так работает:

begin
  (new List<integer>(Seq(1,2,3))).Println();
end. 

#90

Вот реализация с классом, где доступ к глобальным переменным заменен на доступ к полям - и это легитимно:

const n = 8;

var 
  dx := Arr(2, 2, 1, 1, -1, -1, -2, -2);
  dy := Arr(1, -1, 2, -2, 2, -2, 1, -1);

type KnightProblem = class

  Solution := new integer[n, n];
  Success: boolean := false;
 
  procedure Step(i, x, y: integer);
  begin
    if Success then 
      exit;
    // отсечение неверных вариантов  
    if (x < 0) or (x >= n) or (y < 0) or (y >= n) or (Solution[x, y] > 0) then 
      exit;
   
    // запись частичного решения
    Solution[x, y] := i;
   
    if i = n * n then
      Success := true
    else 
      for var k:=0 to 7 do // перебор вариантов
        Step(i + 1, x + dx[k], y + dy[k]);
   
    if not Success then
      Solution[x, y] := 0; // возврат - стирание частичного решения
  end;
end;  
 
const
  x0 = 1; // начальная клетка коня
  y0 = 3;
 
begin
  var kp := new KnightProblem();
  kp.Step(1, x0, y0);
  if kp.Success then
    writeln(kp.Solution);
 
  writelnFormat('Время: {0} мс', Milliseconds/1000);
end.

#91

Сегодня на лекции было сказано, что деревья можно выводить при помощи Write/Writeln.

Для нашего дерева из примера выводится такая строчка: (1,(2,nil,nil),(3,nil,nil)).

Раньше такое работало и для списков, однако сейчас для них выводятся просто скобочки (). Это так и задумано?