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

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

Упражнение 1:
Номер 1

Правила формирования комбинаторных групп:

  • А - считать разными выборки, в которых один и тот же элемент занимает разные позиции.
  • Б - считать одинаковыми выборки, в которых один и тот же элемент занимает разные позиции.
  • В - в выборке участвуют все элементы исходного множества (math).
  • соответствуют основным типам комбинаторных групп:


    Ответ:

     (1) А - Размещения; Б - Сочетания; В - Перестановки 

     (2) А - Размещения; Б - Перестановки; В - Сочетания 

     (3) А - Сочетания; Б - Размещения; В - Перестановки 

     (4) А - Перестановки; Б - Размещения; В - Сочетания 

     (5) А - Сочетания; Б - Перестановки; В - Размещения 

     (6) А - Перестановки; Б - Сочетания; В - Размещения 


    Номер 2
    Комбинаторные группы, в которых есть повторяющиеся элементы свидетельствуют о:

    Ответ:

     (1) наличии повторяющихся элементов в исходном множестве (для перестановок) 

     (2) многократном обращении к одному и тому же элементу исходного множества при формировании комбинаторной группы (для сочетаний) 

     (3) многократном обращении к одному и тому же элементу исходного множества при формировании комбинаторной группы (для размещений) 

     (4) наличии повторяющихся элементов в исходном множестве (для размещений) 

     (5) наличии повторяющихся элементов в исходном множестве (для сочетаний) 

     (6) многократном обращении к одному и тому же элементу исходного множества при формировании комбинаторной группы (для перестановок) 


    Номер 3

    Фрагменты программ на Паскале реализуют алгоритмы формирования таких комбинаторных групп, как:

  • ... for i:=1 to n-1 do for j:=i+1 to n do writeln (A[i], A[j]);
  • ... for i:=1 to n do for j:=i to n do writeln (A[i], A[j]);
  • … for i:=1 to n do for j:=1 to n do if i<>j then writeln (A[i], A[j]);
  • … for i:=1 to n do for j:=1 to n do writeln (A[i], A[j]);

  • Ответ:

     (1) 1. сочетания без повторений, 2. сочетания с повторениями, 3. размещения без повторений, 4. размещения с повторениями 

     (2) 1. сочетания с повторениями, 2. сочетания без повторений, 3. размещения с повторениями, 4. размещения без повторений 

     (3) 1. размещения с повторениями, 2. размещения без повторений, 3. сочетания с повторениями, 4. сочетания без повторений 

     (4) 1. размещения без повторений, 2. размещения с повторениями, 3. сочетания без повторений, 4. сочетания с повторениями 


    Упражнение 2:
    Номер 1
    Три населенных пункта math и math соединены дорогами, по которым курсируют такие автобусные маршруты math. К какому типу комбинаторных групп принадлежат эти маршруты:

    Ответ:

     (1) размещения без повторений 

     (2) размещения с повторениями 

     (3) сочетания без повторений 

     (4) сочетания с повторениями 

     (5) перестановки без повторений 

     (6) перестановки с повторениями 


    Номер 2

    В результате выполнения программы на Паскале, фрагмент которой приведен ниже, произойдет выборка элементов из исходного массива, соответствующая размещениям с повторениями. Что нужно изменить в алгоритме, чтобы из набора выбираемых элементов исключить повторяющиеся:

    … for i:=1 to n do for j:=1 to n do if i<>j then writeln (A[i], A[j]); …

    Ответ:

     (1) не обращаться к одному и тому же элементу дважды при формировании одной группы 

     (2) проверить на равенство счетчики внутреннего и внешнего циклов 

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

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


    Номер 3
     

    В результате выполнения программы на Паскале, фрагмент которой приведен ниже, произойдет выборка элементов из исходного массива math. На печать выйдет:

    … for i:=1 to n do for j:=1 to n do if i<>j then write (A[i], A[j]); …

    Ответ:

     121321233132 


    Упражнение 3:
    Номер 1
    Три населенных пункта math и math соединены дорогами. Стоимость бавтобусного билета зависит от расстояния между населенными пунктами math. К какому типу комбинаторных групп принадлежат эти выбранные населенные пункты

    Ответ:

     (1) сочетания без повторений 

     (2) сочетания с повторениями 

     (3) размещения без повторений 

     (4) размещения с повторениями 

     (5) перестановки без повторений 

     (6) перестановки с повторениями 


    Номер 2

    В результате выполнения программы на Паскале, фрагмент которой приведен ниже, произойдет выборка элементов из исходного массива, соответствующая такому основному типу комбинаторных групп:

    ... for i:=1 to n-1 do for j:=i+1 to n do writeln (A[i], A[j]); …

    Ответ:

     (1) сочетания без повторений 

     (2) сочетания с повторениями 

     (3) размещения без повторений 

     (4) размещения с повторениями 


    Номер 3

    В результате выполнения программы на Паскале, фрагмент которой приведен ниже, произойдет выборка элементов из исходного массива math. На печать выйдет:

    … for i:=1 to n-1 do for j:=i+1 to n do writeln (A[i], A[j]); …

    Ответ:

     121323 


    Упражнение 4:
    Номер 1
    К каким основным типам формирования комбинаторных групп относятся выборки точек по условию такой задачи: "На плоскости math точек заданы своими координатами. Найти "центральную" точку (точку, сумма расстояний от которой до остальных точек максимальна)".

    Ответ:

     (1) размещения без повторений 

     (2) размещения с повторениями 

     (3) сочетания без повторений 

     (4) сочетания с повторениями 

     (5) перестановки без повторений 

     (6) перестановки с повторениями 


    Номер 2

    В результате выполнения программы на Паскале, фрагмент которой приведен ниже, произойдет выборка элементов из исходного массива, соответствующая такому основному типу комбинаторных групп:

    … for i:=1 to n do for j:=1 to n do if i<>j then writeln (A[i], A[j]); …

    Ответ:

     (1) размещения без повторений 

     (2) размещения с повторениями 

     (3) сочетания без повторений 

     (4) сочетания с повторениями 


    Номер 3

    В результате выполнения программы на Паскале, фрагмент которой приведен ниже, произойдет выборка элементов (пазмещения без повторений) из исходного массива math. Какой логический знак должен стоять вместо знака вопроса в логическом выражении:

    … for i:=1 to n do for j:=1 to n do if i ? j then write (A[i], A[j],','); …

    Ответ:

     (1) >> 

     (2) <> 

     (3) != 

     (4)


    Упражнение 5:
    Номер 1
    К каким основным типам формирования комбинаторных групп относятся выборки точек по условию такой задачи: "На плоскости math точек заданы своими координатами. Найти 2 наиболее удаленные друг от друга точки".

    Ответ:

     (1) сочетания без повторений 

     (2) сочетания с повторениями 

     (3) размещения без повторений 

     (4) размещения с повторениями 

     (5) перестановки без повторений 

     (6) перестановки с повторениями 


    Номер 2

    В результате выполнения программы на Паскале, фрагмент которой приведен ниже, произойдет выборка элементов из исходного массива, соответствующая такому основному типу комбинаторных групп:

    ... k:=1; for j:=k to m-k do for i:=j+k to m do writeln (A[i], '-', A[j]); …

    Ответ:

     (1) сочетания без повторений 

     (2) сочетания с повторениями 

     (3) размещения без повторений 

     (4) размещения с повторениями 


    Номер 3

    В результате выполнения программы на Паскале, фрагмент которой приведен ниже, произойдет выборка элементов из исходного массива math. Что напечатается на экране монитора (введите строку без пробелов)

    ... for i:=1 to n-1 do for j:=i+1 to n do writeln (A[j], A[i]); …

    Ответ:

     213132 


    Упражнение 6:
    Номер 1

    В результате выполнения программы на Паскале, фрагмент которой приведен ниже, произойдет выборка элементов из исходного массива, соответствующая такому основному типу комбинаторных групп:

    … for i:=1 to n do for j:=1 to n do writeln (A[i], A[j]); …

    Ответ:

     (1) размещения с повторениями 

     (2) размещения без повторений 

     (3) сочетания с повторениями 

     (4) сочетания без повторений 


    Номер 2
    В результате выполнения какой программы на Паскале (фрагменты приведены ниже) из исходного массива math произойдет такая выборка элементов: 11 12 13 21 22 23 31 32 33

    Ответ:

     (1) …for i:=1 to n do for j:=1 to n do writeln (A[i], A[j]);… 

     (2) …for i:=1 to n do for j:=1 to n do if i<>j then writeln (A[i], A[j]);… 

     (3) …for i:=1 to n do for j:=i to n do writeln (A[i], A[j]);… 

     (4) …for i:=1 to n-1 do for j:=i+1 to n do writeln (A[i], A[j]);… 


    Номер 3

    В результате выполнения программы на Паскале, фрагмент которой приведен ниже, произойдет выборка элементов из исходного массива math. На печать выйдет:

    … for i:=1 to n do for j:=1 to n do writeln (A[i], A[j]); …

    Ответ:

     111213212223313233 


    Упражнение 7:
    Номер 1

    В результате выполнения программы на Паскале, фрагмент которой приведен ниже, произойдет выборка элементов из исходного массива, соответствующая такому основному типу комбинаторных групп:

    ... for i:=1 to n do for j:=i to n do writeln (A[i], A[j]); …

    Ответ:

     (1) сочетания с повторениями 

     (2) сочетания без повторений 

     (3) размещения с повторениями 

     (4) размещения без повторений 


    Номер 2
    В результате выполнения какой программы на Паскале (фрагменты приведены ниже) из исходного массива math произойдет такая выборка элементов: 11 12 13 22 23 33

    Ответ:

     (1) …for i:=1 to n do for j:=1 to n do writeln (A[i], A[j]);… 

     (2) …for i:=1 to n do for j:=1 to n do if i<>j then writeln (A[i], A[j]);…  

     (3) …for i:=1 to n do for j:=i to n do writeln (A[i], A[j]);… 

     (4) …for i:=1 to n-1 do for j:=i+1 to n do writeln (A[i], A[j]);… 


    Номер 3

    В результате выполнения программы на Паскале, фрагмент которой приведен ниже, произойдет выборка элементов из исходного массива А={1, 2, 3}.

    … for i:=1 to n do for j:=i to n do writeln (A[i], A[j]); … Введите результат вывода программы без пробелов:

    Ответ:

     111213222333 


    Упражнение 8:
    Номер 1
    Метод двоичного перебора заключается в…

    Ответ:

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

     (2) разнообразных перестановках двух элементов исходного множества 

     (3) поочередный перебор элементов исходного множества: первый раз элемент "берется" (1), второй раз - "не берется" 

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


    Номер 2
    Для выбора элементов из исходного множества двоичным перебором необходимо получать последовательные двоичные коды. Способ получения нового двоичного кода (на единицу больше предыдущего):

    Ответ:

     (1) перевод счетчика цикла math из десятичной системы счисления в двоичную 

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

     (3) сдвиг влево всех единиц двоичного кода, замена последнего нулевого элемента на единицу 

     (4) циклический сдвиг элементов массива двоичных кодов 


    Номер 3
     

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

    … st:=1; for i:=1 to n do st:=st*2; for i:= 1 to (st-1) do begin for j:= 1 to n do if y[j]= 0 then x:= j; for z:= x to n do y[z]:=0; y[x]:=1; …

    Назначение данного фрагмента:


    Ответ:

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

     (2) получение нового двоичного кода путем перевода номера шага из десятичной системы счисления в двоичную 

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

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


    Упражнение 9:
    Номер 1
    Количество комбинаторных групп, сформированных двоичным перебором будет равно:

    Ответ:

     (1) math 

     (2) math 

     (3) math 

     (4) math 


    Номер 2
    Количество комбинаторных групп, сформированных троичным перебором будет равно:

    Ответ:

     (1) math 

     (2) math 

     (3) math 

     (4) math 


    Номер 3

    В результате выполнения программы, фрагмент которой приведен ниже:

    … st:=1; for i:=1 to 5 do st:=st*2; st:=st-1; …

    в переменной math будет находиться:


    Ответ:

     31 


    Упражнение 10:
    Номер 1
    Решение задачи: "Даны гири массами math. Как можно взвесить предмет массой math, при чем гири можно класть на разные чашы весов" возможно методом:

    Ответ:

     (1) троичного перебора 

     (2) math-ричного перебора 

     (3) двоичного перебора 

     (4) ни один из предложенных методов не подходит 


    Номер 2
    Решение задачи: "В игре имеется набор фишек, достоинством math. Требуется в конце игры представить количество набранных очков набором фишек" возможно методом:

    Ответ:

     (1) двоичного перебора 

     (2) троичного перебора 

     (3) math-ричного перебора 

     (4) ни один из предложенных методов не подходит 


    Номер 3
    Решение задачи: "Необходимо представить число 40 в виде суммы неповторяющихся слагаемых (одинаковые по значению, противоположные по знаку слагаемые считаются разными" возможно методом:

    Ответ:

     (1) троичного перебора 

     (2) math-ричного перебора 

     (3) двоичного перебора 

     (4) ни один из предложенных методов не подходит 


    Упражнение 11:
    Номер 1
    Перевод чисел из десятичной системы счисления в math-ричную предполагает:

    Ответ:

     (1) деление десятичного числа на основание системы счисления n до получения остатка, меньшего math, дальнейшее деление полученного частного на n также до получения остатка, меньшего math и т.д., до получения частного, равного нулю. Все полученные остатки "собираются" в обратном порядке 

     (2) сумму произведений цифр исходного десятичного числа на основание системы счисления math, возведенное в степень, соответствующую разряду десятичной цифры 

     (3) разложение десятичного числа на сумму степеней основания системы счисления math 

     (4) ни один из предложенных методов не подходит 


    Номер 2
     

    Для организации перевода числа а из десятичной в math-ричную систему счисления, программа на Паскале (начальный фрагмент которой приведен ниже)

    … readln (a, n); i:=0; while (a<>0) do begin i:=i+1; x[i]:=a mod n; a:=a div n; end; …

    должна быть продолжена так:


    Ответ:

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

     (2) нужно сложить содержимое элементов массива math размерностью math, содержащего цифры math-ричного числа 

     (3) нужно сложить произведения элементов массива math размерностью math (содержащего цифры math-ричного числа) на 10 в степенях math

     (4) из массива math необходимо удалить "неиспользованные" элементы 


    Номер 3

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

    … a:=100; n:=5; i:=0; while (a<>0) do begin i:=i+1; write (a mod n); a:=a div n; end; …

    Ответ:

     004 




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