игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Решение олимпиадных задач по информатике / Тест 9

Решение олимпиадных задач по информатике - тест 9

Упражнение 1:
Номер 1 
Дан двумерный массив А, размерностью 3х4. Сколько "путей" ведет из элемента А[1,1] в элемент А[3,4], с условием, что "двигаться" можно в порядке увеличения номера строки или в порядке увеличения номера столбца?

Ответ:

 10 

Номер 2 
Какие из ниже перечисленных особенностей имеют отношение к Арифметическому квадрату?

Ответ:

 (1) первая строка и первый столбец состоят из единиц 

 (2) элементы массива "симметричны" относительно главной диагонали 

 (3) элементы, находящиеся на побочной диагонали образуют палиндром 

 (4) элементы, находящиеся на главной диагонали образуют геометрическую прогрессию 

Номер 3 
Сколько путей ведет из клетки (1, 1) в клетку (n, 1) двумерного массива, если двигаться можно только вниз и вправо?

Ответ:

 1 

Упражнение 2:
Номер 1 
Приведенный ниже фрагмент программы на Паскале реализует алгоритм заполнения Арифметического квадрата. 

…
for i:=1 to n do
begin
 a[i,1]:=i; a[1,i]:=i;
end;
for i:=2 to n do
 for j:=2 to n do a[i,j]:=a[i-1,j]+a[i,j-1];
…

Найдите в нем ошибку:

Ответ:

 (1) первая строка и первый столбец должны быть заполнены единицами, а не числами натурального ряда 

 (2) в одном теле цикла нельзя обращаться к элементам первой строки и первого столбца одновременно 

 (3) заполнение массива должно идти с конца (элемента последней строки последнего столбца) 

 (4) в программе нет ошибок 

Номер 2 
Приведенный ниже фрагмент программы на Паскале реализует алгоритм заполнения Арифметического квадрата. 

…
for i:=1 to n do
begin
 a[i,1]:=1; a[1,i]:=1;
end;
for i:=1 to n do
 for j:=1 to n do a[i,j]:=a[i-1,j]+a[i,j-1];
…

Найдите в нем ошибку:

Ответ:

 (1) заполнение остального массива (кроме первой строки и первого столбца) должно происходить во вложенных циклах, начальное значение счетчиков при этом равно "2" 

 (2) первая строка и первый столбец должны быть заполнены числами натурального ряда, а не единицами 

 (3) в одном теле цикла нельзя обращаться к элементам первой строки и первого столбца одновременно 

 (4) в программе нет ошибок 

Номер 3 
Приведенный ниже фрагмент программы на Паскале реализует алгоритм заполнения Арифметического квадрата. 

…
for i:=1 to n do
 for j:=1 to n do
 begin a[i,j]:=1; a[i,j]:=1; end;
for i:=2 to n do
 for j:=2 to n do a[i,j]:=a[i-1,j]+a[i,j-1];
…

Что в нем стоит изменить?

Ответ:

 (1) программа работает неэффективно, так как происходит заполнение не только первой строки и первого столбца единицами, но и всего массива( 

 (2) первая строка и первый столбец должны быть заполнены числами натурального ряда, а не единицами 

 (3) в одном теле цикла нельзя обращаться к элементам первой строки и первого столбца одновременно 

 (4) программа полностью соответствует типовому алгоритму заполнения арифметического квадрата 

Упражнение 3:
Номер 1 
На побочной диагонали Арифметического квадрата располагаются элементы, которые являются коэффициентами для слагаемых при разложени целой неотрицательной степени суммы двух переменных в Биноме Ньютона (например, math). Массив какой размерности необходимо заполнить, чтобы получить коэффициенты для слагаемых при разложении суммы двух переменных в шестой степени?

Ответ:

 7 

Номер 2 
Предположим, что есть программа на Паскале, реализующая заполнение Арифметического квадрата порядка nxn. Для вывода на экран "Треугольника Паскаля" в программу дописали фрагмент:

…
for i:=1 to n do
 begin
 for j:=1 to ? do write (a[i,j]);
 writeln;
 end;
…

Какое значение необходимо написать в заголовке внутреннего цикла вместо знака вопроса?

Ответ:

 (1) math 

 (2) math 

 (3) math 

 (4) math 

Номер 3 
Предположим, что есть программа на Паскале, реализующая заполнение Арифметического квадрата порядка nxn. В какой части этого массива находится "Треугольник Паскаля"?

Ответ:

 (1) выше и на побочной диагонали 

 (2) выше и на главной диагонали 

 (3) ниже и на побочной диагонали 

 (4) ниже и на главной диагонали 

Упражнение 8:
Номер 1 
Установите, как будет заполнен двумерный массив в результате выполнения программы на Паскале, фрагмент которой приведен ниже:

… x:=1;
for j:=1 to n do
 for i:=1 to j do
  begin a [i, j-i+1]:=x; x:=x+1;	
  end; …

Ответ:

 (1) \begin{matrix} 1&2&4&7\\ 3&5&8&0\\ 6&9&0&0\\ 10&0&0&0 \end{matrix}  

 (2) \begin{matrix} 1&1&1&1\\ 1&2&2&1\\ 1&2&2&1\\ 1&1&1&1 \end{matrix}  

 (3) \begin{matrix} 1&2&3&4\\ 12&13&14&5\\ 11&16&15&6\\ 10&9&8&7 \end{matrix}  

 (4) \begin{matrix} 1&2&3&4\\ 8&7&6&5\\ 9&10&11&12\\ 16&15&14&13 \end{matrix}  

Номер 2 
Какое тело цикла необходимо создать, чтобы двумерный массив в результате выполнения программы на Паскале (фрагмент ниже)…

…
x:=1;
for j:=1 to n do
 for i:=1 to j do
  begin
  ???
  end;…


… заполнялся так:

\begin{matrix}
1&2&4&7\\
3&5&8&0\\
6&9&0&0\\
10&0&0&0
\end{matrix}

Ответ:

 (1) a [i, j-i+1]:=x; x:=x+1; 

 (2) x:=x+1; a [i, j-i+1]:=x; 

 (3) a [i, n-i+1]:=x; x:=x+1; 

 (4) a [n-i+1,i]:=x; x:=x+1; 

Номер 3 
Какие значения примут элементы первой строки двумерного массива, размерностью 4x4, в результате выполнения программы на Паскале, фрагмент которй приведен ниже (введите числа через пробел)

…
x:=1;
for j:=1 to n do
 for i:=1 to j do
  begin
  a [i, j-i+1]:=x; x:=x+1;
  end;…

Ответ:

 1 2 4 7 

Упражнение 4:
Номер 1 
Установите, как будет заполнен двумерный массив в результате выполнения программы на Паскале, фрагмент которой приведен ниже:

…
for k:=1 to (n div 2 +1) do
 for i:=k to n-k+1 do
  for j:=k to n-k+1 do a[i,j]:= k;
…

Ответ:

 (1) \begin{matrix} 1&1&1&1&1\\ 1&2&2&2&1\\ 1&2&3&2&1\\ 1&2&2&2&1\\ 1&1&1&1&1 \end{matrix}  

 (2) \begin{matrix} 1&2&4&7\\ 3&5&8&0\\ 6&9&0&0\\ 10&0&0&0 \end{matrix}  

 (3) \begin{matrix} 1&2&3&4\\ 12&13&14&5\\ 11&16&15&6\\ 10&9&8&7 \end{matrix}  

 (4) \begin{matrix} 1&2&3&4\\ 8&7&6&5\\ 9&10&11&12\\ 16&15&14&13 \end{matrix}  

Номер 2 
Какое тело цикла по i необходимо создать (вместо вопросительных знаков), чтобы двумерный массив в результате выполнения программы (фрагмент ниже)…

…	
for k:=1 to (n div 2 +1) do
 ???
  for j:=k to n-k+1 do a[i,j]:= k;
…

был заполнен так:

\begin{matrix}
1&1&1&1&1\\
1&2&2&2&1\\
1&2&3&2&1\\
1&2&2&2&1\\
1&1&1&1&1
\end{matrix}

Ответ:

 (1) for i:=k to n-k+1 do 

 (2) for i:=1 to n-k+1 do 

 (3) for i:=k to n do 

 (4) for i:=1 to k do 

Номер 3 
Какие значения примут элементы первой строки двумерного массива, размерностью 5x5, в результате выполнения программы на Паскале, фрагмент которй приведен ниже (введите числа через пробел)

…	
for k:=1 to (n div 2 +1) do
 for i:=k to n-k+1 do
  for j:=k to n-k+1 do a[i,j]:= k;
…

Ответ:

 1 1 1 1 1 

Упражнение 5:
Номер 1 
В каком направлении идет заполнение двумерного массива в 1-ом вложенном цикле по i, в результате выполнения программы на Паскале, фрагмент которой приведен ниже:

… x:=1;
for k:=1 to n div 2 do
 begin
 for i:=k to n-k do
  begin a[k,i]:=x; x:=x+1; end;
 for i:=k to n-k do
  begin a[i,n-k+1]:=x; x:=x+1; end;
 for i:=k to n-k do
  begin a[n-k+1,n-i+1]:=x; x:=x+1; end;
 for i:=k to n-k do
  begin a[n-i+1,k]:=x; x:=x+1; end;
end; …

Ответ:

 (1) в строку слева направо 

 (2) в столбец сверху вниз 

 (3) в строку справа налево 

 (4) в столбец снизу вверх 

Номер 2 
В каком направлении идет заполнение двумерного массива в 2-ом вложенном цикле по i, в результате выполнения программы на Паскале, фрагмент которой приведен ниже:

… 
x:=1;
for k:=1 to n div 2 do
 begin
 for i:=k to n-k do
  begin a[k,i]:=x; x:=x+1; end;
 for i:=k to n-k do
  begin a[i,n-k+1]:=x; x:=x+1; end;
 for i:=k to n-k do
  begin a[n-k+1,n-i+1]:=x; x:=x+1; end;
 for i:=k to n-k do
  begin a[n-i+1,k]:=x; x:=x+1; end;
end; …

Ответ:

 (1) в столбец сверху вниз 

 (2) в строку слева направо 

 (3) в строку справа налево 

 (4) в столбец снизу вверх 

Номер 3 
В каком направлении идет заполнение двумерного массива в 3-ем вложенном цикле по i, в результате выполнения программы на Паскале, фрагмент которой приведен ниже:

… 
x:=1;
for k:=1 to n div 2 do
 begin
 for i:=k to n-k do
  begin a[k,i]:=x; x:=x+1; end;
 for i:=k to n-k do
  begin a[i,n-k+1]:=x; x:=x+1; end;
 for i:=k to n-k do
  begin a[n-k+1,n-i+1]:=x; x:=x+1; end;
 for i:=k to n-k do
  begin a[n-i+1,k]:=x; x:=x+1; end;
end; …

Ответ:

 (1) в строку справа налево 

 (2) в строку слева направо 

 (3) в столбец сверху вниз 

 (4) в столбец снизу вверх 

Упражнение 6:
Номер 1 
Установите, как будет заполнен двумерный массив в результате выполнения программы на Паскале, фрагмент которой приведен ниже:

…
x:=1;
for i:=1 to n do
 for j:=1 to n do
  begin
  if i mod 2=0 then a[i,n-j+1]:=x 
    else a[i,j]:=x;
  x:=x+1; 
  end;
…

Ответ:

 (1) \begin{matrix} 1&2&3&4\\ 8&7&6&5\\ 9&10&11&12\\ 16&15&14&13 \end{matrix} 

 (2) \begin{matrix} 1&2&4&7\\ 3&5&8&0\\ 6&9&0&0\\ 10&0&0&0 \end{matrix} 

 (3) \begin{matrix} 1&1&1&1\\ 1&2&2&1\\ 1&2&2&1\\ 1&1&1&1 \end{matrix} 

 (4) \begin{matrix} 1&2&3&4\\ 12&13&14&5\\ 11&16&15&6\\ 10&9&8&7 \end{matrix} 

Номер 2 
Какая команда должна стоять вместо вопросительных знаков в ветвлении, чтобы двумерный массив в результате выполнения программы на Паскале (фрагмент ниже)…

…
x:=1;
for i:=1 to n do
 for j:=1 to n do
  begin
  if i mod 2=o then a[i,j]:=x
    else ???
  x:=x+1; 
  end;
…

был заполнен так:

\begin{matrix}
1&2&3&4\\
8&7&6&5\\
9&10&11&12\\
16&15&14&13
\end{matrix}

Ответ:

 (1) a[i,n-j+1]:=x; 

 (2) a[n-i+1,n-j+1]:=x; 

 (3) a[n-i+1,j]:=x; 

 (4) a[j,i]:=x; 

Номер 3 
Какие значения примут элементы последней строки двумерного массива, размерностью 4x4, в результате выполнения программы на Паскале, фрагмент которй приведен ниже (введите числа через пробел)

…
x:=1;
for i:=1 to n do
 for j:=1 to n do
  begin
  if i mod 2=o then a[i,j]:=x
    else a[i,n-j+1]:=x; 
  x:=x+1; 
  end;
…

Ответ:

 16 15 14 13 

Упражнение 7:
Номер 1 
Для реализации алгоритма заполнения Магического квадрата размерностью math методом "Террас" необходимо заполнить двумерный массив размерностью:

Ответ:

 (1) math 

 (2) math 

 (3) math 

 (4) math 

Номер 2 
Для заполнения Магического квадрата размерностью math методом "Террас" необходимо заполнять двумерный массив размерностью math:

Ответ:

 (1) в направлении, параллельном побочной диагонали массива 

 (2) числами натурального ряда 

 (3) рядом целых последовательных чисел от нуля 

 (4) в направлении, параллельном главной диагонали массива 

Номер 3 
Для реализации алгоритма заполнения Магического квадрата размерностью math методом "Террас" необходимо заполнить двумерный массив размерностью math, где math равно:

Ответ:

 9 



Главная / Алгоритмы и дискретные структуры / Решение олимпиадных задач по информатике / Тест 9