Введение в информатику. Практикум

Алгоритмы, основные свойства, структуры

Показывать лекцию целиком

Задачи

  • Привести примеры, показывающие важность и необходимость всех свойств алгоритмов. Указание: приведите примеры, когда нарушение свойства приводит к невыполнимости алгоритма, например, нарушение свойства результативности – " алгоритм " решения квадратного уравнения, не обрабатывающий случай D<0.
  • Составить структуру цикла типа "для" и преобразовать ее в структуру типа "пока". Привести примеры, показывающие разрешимость и неразрешимость обратного типа преобразования. Указание: например, любой цикл for i:=1 to n do <тело цикла> ; эквивалентен циклу i:=1; while (i<=n) do begin <тело цикла>; i:=i+1; end;.
  • Чему будет равно значение переменной s после завершения фрагмента программы:
    s:=0; 
i:=1;
while (i<4) do 
    begin 
      i:=i+1; 
      s:=s+i
    end;?
    Указание: фрагмент суммирует числа 2, 3, 4.
  • Чему будут равны значения переменных x, y после завершения фрагмента программы:
    x:=1234;
for i:=1 to 4 do 
    begin 
      y:=y+x mod 10;
      x:=x div 10
    end;?
    Указание: x mod 10 – выделяет цифру младшего разряда числа, x div 10 – "отбрасывает" эту выделенную цифру.
  • Чему будут равны значения переменных k, s после завершения фрагмента программы:
    k:=1; 
s:=x[1]; 
for i:=1 to n do
    if (s<х[i])
    then begin
           s:=х[i];
           k:=i
         end;?
    Указание: в теле цикла фиксируются последовательно значения элементов x[i] и их номера k для которых верно неравенство s<x[i].
  • Чему будет равно значение переменной s после завершения фрагмента программы:
    s:=0; 
i:=1; 
while (i<100) do
    begin 
      s:=s+x[i]; 
      i:=i+2
    end;?
    Указание: перебираются все нечетные элементы массива х из 99 элементов.
  • Чему будет равно значение переменной p после завершения фрагмента программы:
    p:=1; 
for i:=1 to int(n/2) do
    p:=p*x[i];?
    Указание: int(n/2) – "половина" n.
  • Чему будет равно значение переменной p после завершения фрагмента программы:
    р:=1; 
i:=4; 
while (i>0) do
    begin
      р:=р?i; 
      i:=i–1 
    end;?
    Указание: в теле цикла перемножаются числа i=4, i=3, i=2, i=1.
  • Найти наборы входных целых значений a, b, для которых результирующее значение переменной f будет равно 1 после завершения фрагмента программы:
    read(a,b);
b:=abs(b);
a:=abs(a); 
while ((а>0) and (b>0)) do
    if(а>b)
    then а:=mod(а,b) 
    else b:=mod(b,а); 
f=a+b; .
    Указание: подобрать соответствующий тест (набор тестов).
  • Задать некоторый массив x небольшой размерности и определить, чему будет равно значение переменной s после завершения фрагмента программы:
    i:=1;
 j:=i;
 s:=0; 
 while ((i<n) and (x[i,j]>0)) do
    begin
      j:=1;
      while ((j<m) and (x[i,j]>0)) do
         begin
           s:=s+x[i,j];
           j:=j+1
         end;
      i:=i+1
    end;?
    Указание: задайте, например, массив из чисел x[I,j]=i+j, i=1, 2 ; j=1, 2, 3.
    •

    Темы научных исследований и рефератов (Интернет-листов)

  • Что такое алгоритмика?
  • Наиболее важные и ключевые работы по теории алгоритмов.
  • А.А. Марков и нормальные алгоритмы.
  • Алгоритмическая разрешимость и неразрешимость.
  • Сложность алгоритмов.
  • P-полные алгоритмы.
  • NP-полные алгоритмы.
  • Алгоритмический стиль мышления и алгоритмический подход к решаемым задачам.
  • Математические и логические основы алгоритмизации.
  • Базовые алгоритмические структуры ; их синтаксис, семантика и прагматика.
    •
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^