• Кратность
  • . Чередование
  • Фрагмент алгоритма

  • Скачать 48.42 Kb.


    Дата09.11.2018
    Размер48.42 Kb.
    ТипЗадача

    Скачать 48.42 Kb.

    Разбор задач отборочного тура



    РАЗБОР ЗАДАЧ ОТБОРОЧНОГО ТУРА
    З-1. Длина нити (5 баллов)

    Злоумышленники варварски вбили в ни в чем неповинную плоскую поверхность N гвоздей, да так, что только шляпки остались. Мало того, они в своих подлых целях вбили все гвозди в вершины выпуклого многоугольника. После этого они... страшно сказать... они натянули ниточку вокруг всех гвоздей, так, что поверхности стало совсем грустно! Вот как, примерно, они это сделали:




    Ваша задача – составить алгоритм, который находит длину этой ниточки.

    Решение.

    Заметим, что ниточка замкнута, т.е. радиус-вектор совершил полный оборот - угол в 2pi радиан. Несложно найти длину ниточки, обходящую вокруг шляпок гвоздей - 2pi*r, где r - радиус гвоздя. Если бы все гвозди были разные, то задача была бы посложнее, а так нам осталось только найти длину ниточки, соединяющей разные шляпки. В нашем случае для этого достаточно сложить расстояния между центрами гвоздей (не забыв соединить последний гвоздь с первым). Это делается очень просто S12 = sqrt(sqr(x1-x2) + sqr(y1-y2)).

    З-2. Кратность

    Проверить данный признак делимости на 11 для всех натуральных четырехзначных чисел и вывести на экран все числа, кратные 11.



    Решение.

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


    CLS

    FOR i = 1000 TO 9999

    t = i \ 1000

    s = (i - t * 1000) \ 100

    d = (i - t * 1000 - s * 100) \ 10

    e = i - t * 1000 - s * 100 - d * 10

    IF ((d + t) - (e + s)) MOD 11 = 0 THEN PRINT i

    NEXT
    З-3. Чередование

    В массиве Z(m) найти число чередований знаков элементов.

    Решение.

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

    CLS

    INPUT "Число элементов ", m



    DIM z(m+1)

    FOR i = 1 TO m

    PRINT "Введите z("; i; ")"; : INPUT z(i)

    NEXT


    FOR i = 1 TO m

    FOR j = 1 TO m - 1

    IF z(j) = 0 THEN SWAP z(j), z(j + 1)

    NEXT


    NEXT

    FOR j = 1 TO m - 1

    IF z(j) * z(j + 1) < 0 THEN z(m+1) = z(m+1) + 1

    NEXT


    PRINT "Число чередований знака в данной последовательности равно"; z(m+1)

    END


    З-4. Друзья (35 баллов)

    В клубе N человек. Многие из них - друзья. Так же известно, что друзья друзей так же являются друзьями. Требуется выяснить, сколько всего друзей у конкретного человека в клубе. Входные данные :вводятся два числа: N и S (1 <= N <= 100; 1 <= S <= N), где N - количество человек в клубе, а S – номер конкретного человека. А также задается матрица смежности, состоящая из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что люди с номерами i и j – друзья, а 0 – выражает неопределенность.



    Решение.

    Задача может быть решена путем стандартного обхода графа в глубину. Пусть a[i][j] – матрица смежности, данные которой описаны во входных данных, а в массиве b[i] будем хранить 1, если i-й человек является другом и 0 иначе. Рекурсивная функция dfs(v) будет помечать v-го человека как друга (b[v]=1), и далее рассматривать всех его непомеченных друзей и вызывать себя с параметром этих друзей. В момент пометки друга будем увеличивать на единицу некоторый счетчик, значение которого и окажется в итоге ответом на поставленную задачу. Сложность такого алгоритма O(n2), т.к. согласно такому алгоритму не будет повторных вызовов для одной и той же вершины графа.

    Алгоритмическая реализация вышеописанного:

    //обход в глубину графа из вершины v с пометкой этой вершины

    void dfs(v){

    k=k+1; //увеличиваем счетчик

    b[v]=true; //помечаем "друга"

    for i=1..n

    if(a[v][i]=1 and b[i]=false) then dfs(i);

    }

    //чтение входных данных

    read(n,s);

    for i=1..n

    for j=1..n

    read(a[i][j]);

    k=-1; //обнуление счетчика с учетом того, что самого себя считать другом не следует

    dfs(s);

    write(k);
    З-5. Одинокий путник.

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



    Особенности задачи.

    А. Путник не может использовать свои координаты. Таким образом, для принятия решения о том, обошёл ли он всё препятствие, путник может использовать только типы пройденных стенок. Всего типов стенок 4.

    Б. Под формой препятствия подразумевается последовательность типов стенок препятствия.

    Решение. Обходя препятствие, путник записывает тип текущей стенки в массив на каждом своем шаге. Шаги путника имеют равную длину. Тип первой встречной стенки равен 1. Дальнейшие стенки препятствия имеют тип 1, 2, 3 или 4. Присвоение новой стенке очередного типа зависит от ее направленности по отношению к предыдущей. Внешний угол соответствует прибавлению 1, причем 4+1=1; внутренний угол – вычитанию 1 (с учетом 1-1=4).

    Внешний угол: Внутренний угол:



    Путник принимает решение о том, что препятствие пройдено на основании равенства сумм типов стенок в образовавшемся массиве. Если (кол-во «тип 1»-1)=кол-ву «тип 3» и кол-во «тип 2»=кол-ву «тип 4», то обход препятствия завершается. Форма определяется как последовательное перечисление из массива всех соответствующих типов стенок, за исключением последней 1. Отметим, что 1 окажется последним элементом во всех препятствиях.
    Фрагмент алгоритма.

    ...

    Текущий тип i=1, массив типов нулевой.

    Повторять до выхода

    1. Записать в массив i.

    2. Повернуть налево и см. стену.

    3. Если нет стены впереди, то делать шаг вперед,

    иначе повернуть налево и присваиваем номер стены как i=i-1 (причем 1-1 =4) и вернуться к п.3.

    1. Повернуть направо и см. стену.

    2. Если нет стены впереди, то шаг вперед, номер стены i= i +1 (причем 4+1 =1), повернуть направо.

    3. Подсчитываем количество 1,2,3 и 4 в массиве.

    Если (кол-во «1»-1)=кол-ву «3» и кол-во «2»=кол-ву «4», то выходим из цикла.

    ...

    Коьрта
    Контакты

        Главная страница


    Разбор задач отборочного тура

    Скачать 48.42 Kb.