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

Упражнение 1:

---

Номер 1

Использование дополнительного массива флажков ("отмечающих" выбранные элементы в соответствующих флажкам позициях исходного массива) предполагает, что:

Ответ:

---

Номер 2

В решениях приведенных ниже задач:
А."В строке, содержащей арифметическое выражение проверить, правильно ли расставлены скобки";
В."В картинной галерее работают сторожа. Для каждого сторожа известно время прихода на работу и время ухода. Определить, всегда ли галерея охраняется";
С."N отрезков на координатной прямой заданы координатами своих концов. Определить количество связных областей"
элементы массива флажков, отмечающих наступление-окончание события, на этапе заполнения начальных значений примут такие значения:

Ответ:

---

Номер 3

Можно ли "отмечать" начало и конец какого-либо события (пример задачи: "В картинной галерее работают сторожа. Для каждого сторожа известно время прихода на работу и время ухода. Определить, всегда ли галерея охраняется") не флажками "1" и "-1", а любыми символами (например, "*" и "/")?

Ответ:

---

Упражнение 2:

---

Номер 1

В результате выполнения программы на Паскале, фрагмент которой приведен ниже, массив Flag будет содержать:
…
readln (n);
for i:=1 to n do a[i]:=i;
for i:=2 to n div 2 do 
 if flag[i]=0 then
  for j:=i+1 to n do
   if (a[j] mod a[i]=0) then flag[j]:=1;
…

Ответ:

---

Номер 2

В результате выполнения программы на Паскале, фрагмент которой приведен ниже, массив Flag будет содержать:
…
n:=5;
for i:=1 to n do a[i]:=i;
for i:=2 to n div 2 do 
 if flag[i]=0 then
  for j:=i+1 to n do
   if (a[j] mod a[i]=0) then flag[j]:=1;
…

Ответ:

---

Номер 3

В результате выполнения программы на Паскале, фрагмент которой приведен ниже, на экран выведутся:
…
readln (n);
for i:=1 to n do a[i]:=i;
for i:=2 to n div 2 do 
 if flag[i]=0 then
  for j:=i+1 to n do
   if (a[j] mod a[i]=0) then flag[j]:=1;
for i:=2 to n do
 if flag[i]=0 then writeln (a[i])
… 

Ответ:

---

Номер 4

В результате выполнения программы на Паскале, фрагмент которой приведен ниже, массив Flag будет содержать:
…
for i:=1 to 10 do 
begin
  a[i]:=i;
  flag[i]:=0;
end
for i:=2 to 10 div 2 do 
 if flag[i]=0 then
  for j:=i+1 to 10 do
   if (a[j] mod a[i]=0) then flag[j]:=1;
…

Ответ:

---

Упражнение 3:

---

Номер 1

В решениях приведенных ниже задач:
А."В строке, содержащей арифметическое выражение проверить, правильно ли расставлены скобки";
В."В картинной галерее работают сторожа. Для каждого сторожа известно время прихода на работу и время ухода. Определить, всегда ли галерея охраняется";
С."N отрезков на координатной прямой заданы координатами своих концов. Определить количество связных областей"
используются типовые алгоритмы:
 

Ответ:

---

Номер 2

Для решения приведенных ниже задач:
- В строке, содержащей арифметическое выражение проверить, правильно ли расставлены скобки;
- В картинной галерее работают сторожа. Для каждого сторожа известно время прихода на работу и время ухода. Определить, всегда ли галерея охраняется;
- N отрезков на координатной прямой заданы координатами своих концов. Определить количество связных областей.
необходимо воспользоваться типовыми алгоритмами:

Ответ:

---

Номер 3

Что выведется на экран в результате работы программы, фрагмент которой приведен ниже:
…
 stroka:='(5+y)*(x-4)'; n:=length (stroka); s:=0;
 for i:=1 to n do
  begin a[i]:=copy(stroka, i, 1); flag[i]:=0; end;
 for i:=1 to n do
  begin
  if a[i]="(" then flag [i]:=1;
  if a[i]=")" then flag [i]:=-1;
  end;
 for i:=1 to n do
  begin
  s:=s+flag [i];
  if s<0 then x:=1;
  end;
 if (s=0) and (x=0) then writeln ('верно')
 else writeln ('неверно');
…

Ответ:

---

Упражнение 4:

---

Номер 1

Какие шаги необходимо включить в словесный алгоритм для решения задачи: "В строке, содержащей арифметическое выражение проверить, правильно ли расставлены скобки" из предложенного набора:
A. исходные данные вводим в массив
B. массив Flag заполняется "1" (если имеющий такой же порядок элемент массива исходных данных соответствует началу события, связанного с этим данным), "-1" (соответствует окончанию события) 
C. сортируем массив исходных данных, одновременно переставляя элементы массива Flag
D. суммируем элементы массива Flag. Анализируем сумму.

Ответ:

---

Номер 2

В результате работы программы, фрагмент которой приведен ниже, идет проверка правильности расстановок скобок в арифметическом выражении. Что будет результатом работы программы, если в данном выражении (например:  избыточное количество скобок: 
…
 n:=length (stroka); s:=0;
 for i:=1 to n do
  begin a[i]:=copy(stroka, i, 1); flag[i]:=0; end;
 for i:=1 to n do
  begin if a[i]="(" then flag [i]:=1; if a[i]=")" then flag [i]:=-1; end;
 for i:=1 to n do
  begin s:=s+flag [i]; if s<0 then x:=1; end;
 if (s=0) and (x=0) then writeln ('верно')
 else writeln ('неверно');
…

Ответ:

---

Номер 3

В результате работы программы, фрагмент которой приведен ниже, идет проверка правильности расстановок скобок в арифметическом выражении. Что будет результатом работы программы, если в данном выражении (например: ) избыточное количество скобок: 
…
 n:=length (stroka); s:=0;
 for i:=1 to n do
  begin a[i]:=copy(stroka, i, 1); flag[i]:=0; end;
 for i:=1 to n do
  begin if a[i]="(" then flag [i]:=1; if a[i]=")" then flag [i]:=-1; end;
 for i:=1 to n do
  begin s:=s+flag [i]; if s<0 then x:=1; end;
 if (s=0) and (x=0) then writeln ('верно')
  else writeln ('неверно');
…

Ответ:

---

Упражнение 6:

---

Номер 1

Какие шаги необходимо включить в словесный алгоритм для решения задачи: "В картинной галерее работают сторожа. Для каждого сторожа известно время прихода на работу и время ухода. Определить, всегда ли галерея охраняется" из предложенного набора:
A. исходные данные вводим в массив
B. массив Flag заполняется "1" (если имеющий такой же порядок элемент массива исходных данных соответствует началу события, связанного с этим данным), "-1" (соответствует окончанию события) 
C. сортируем массив исходных данных, одновременно переставляя элементы массива Flag
D. суммируем элементы массива Flag. Анализируем сумму.

Ответ:

---

Номер 2

Ниже приведен фрагмент программы, реализующий алгоритм решения задачи: "В картинной галерее работают сторожа. Для каждого сторожа известно время прихода на работу и время ухода. Определить, всегда ли галерея охраняется":
…
//заполнение массива a (временем прихода и ухода сторожа), массива flag ("1" и "-1")
…
//сортировка массива а с перестановкой элементов массива flag (в соответствии с перестанавливаемыми элементами массива а) 
…
for i=1 to 2*n do
 begin
 s:=s+flag [i];
 if s=0 then k:=k+1;
 end;
if k=1 then writeln ('галерея всегда охранялась')
else writeln ('галерея оставалась без охраны', k-1,'раз');

Каков будет результат работы программы, если время ухода одного из сторожей совпадает с временем прихода его сменщика?

Ответ:

---

Номер 3

Ниже приведен фрагмент программы, реализующий алгоритм решения задачи: "В картинной галерее работают сторожа. Для каждого сторожа известно время прихода на работу и время ухода. Определить, всегда ли галерея охраняется":
…
//заполнение массива a (временем прихода и ухода сторожа), массива flag ("1" и "-1")
…
//сортировка массива а с перестановкой элементов массива flag (в соответствии с перестанавливаемыми элементами массива а) 
…
for i=1 to 2*n do
 begin
 s:=s+flag [i];
 if s=0 then k:=k+1;
 end;
writeln ('количество случаев неохраняемости галереи')
writeln (k-1);
…
Какое количество случаев неохраняемости галереи выдаст программа, если время ухода одного из сторожей совпадает с временем прихода его сменщика?

Ответ:

---

Упражнение 7:

---

Номер 1

Какие шаги необходимо включить в словесный алгоритм для решения задачи: "N отрезков на координатной прямой заданы координатами своих концов. Определить количество связных областей" из предложенного набора:
A. исходные данные вводим в массив
B. массив Flag заполняется "1" (если элемент массива исходных данных соответствует началу события), "-1" (соответствует окончанию события) 
C. сортируем массив исходных данных, одновременно переставляя элементы массива Flag
D. суммируем элементы массива Flag. Анализируем сумму.

Ответ:

---

Номер 2

Ниже приведен фрагмент программы, реализующий алгоритм решения задачи: "N отрезков на координатной прямой заданы координатами своих концов. Определить количество связных областей":
…
//заполнение массива a (координаты концов отрезка), массива flag ("1" и "-1")
…
//сортировка массива а с перестановкой элементов массива flag (в соответствии с перестанавливаемыми элементами массива а) 
…
for i=1 to 2*n do
 begin
 s:=s+flag [i];
 if s=0 then k:=k+1;
 end;
writeln ('количество связных областей', k);
…
Сколько связных областей дадут два отрезка, имеющие одну общую координату (начало одного совпадает с концом другого)?

Ответ:

---

Номер 3

Укажите количество связных областей для n (n вводится с клавиатуры) отрезков, пары координат которых также вводятся с клавиатуры. Входные данные:

Ответ:

---