Погода
Календарь
Май 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 12345
6789101112
13141516171819
20212223242526
2728293031  
Страницы сайта

Обработка символьных строк.

Решение задания требует знания следующих тем и понятий:

Работа со строками

  • строку можно представить, как одномерный массив, в котором хранятся символы;
  • для того чтобы обратиться к символу строки s с номером i (например, вывести его на экран) используется запись s[i]:
s:='лес';  
write(s[1]); {на экране буква 'л'}
  • при работе со строками используется операция конкатенации или объединения строк в одну; в качестве нее используется знак сложения (+), например:

s := ’56’ + ’78’; { получили ‘5678’ }

  • в кодовой таблице ASCII цифры имеют коды от 48(соответствует цифре 0) до 57 (соответствует цифре 9); функция Ord() служит для получения кода символа, например:

k := Ord(‘0’); { k = 48 }

  • то же самое можно сделать с помощью преобразования типа (перевод типа char к типу integer)
k := integer('0'); { k = 48 }
  • функция Chr() служит для обратного перевода: получения символа по его коду, например:
c := Chr(48);  { получили в с символ '0' }
  • то же самое можно сделать с помощью преобразования типа (привести тип integer к типу char)
c := char(48); { получили символ '0' }

Работа с записями

Запись в Паскале — это сложный тип данных, который может состоять из нескольких элементов – полей; поля могут иметь различный тип.

Сложность алгоритмов

Для определения вычислительной мощности, которая потребуется для выполнения компьютером того или иного алгоритма, вводится понятие сложности алгоритма. Существует:

  • временная сложность;
  • пространственная (емкостная) сложность (определяется количеством ячеек памяти, используемых в процессе его выполнения).

Одним из вариантов оценки сложности алгоритма является подсчет количества выполняемых в нем операций.

сложность O(N)

N — размер массива данных

если сложность алгоритма характеризуется, как O(N), это значит, что для больших N увеличение в два раза размера массива данных приведет к примерно такому же увеличению (в два раза) количества операций;

такая сложность O(N) характерна, например, для алгоритма с одним (или несколькими) простыми циклами без вложенности, в которых выполняется N итераций (проходов цикла);

примером алгоритма со сложностью O(N) может служить алгоритм поиска максимального элемента в одномерном массиве:

{поиск максимального элемента массива array из N элементов} 
...
max := array[1];
for i:=2 to N do
if array[i] < max
max := array[i];
writeln (max);
...
Подсчитаем количество операций для данного алгоритма: 
N — 1 операция присваивания счетчику цикла i очередного значения;
N — 1 операция сравнения счетчика со значением N;
N — 1 операция сравнения очередного элемента массива со значением max;
от 1 до N операций присваивания значения переменной max.

существует формула для определения количества операций для алгоритма со сложностью O(N):

p = a * N + b

где a и b – постоянные, которые имеют свои значения для определенных классов задач;

  • так, если задача решена двумя способами: в одном используется несколько циклов от 1 до N, а во втором используется только один цикл, то хотя оба алгоритма имеют сложность O(N), но эффективнее в большинстве случаев является алгоритм с одним циклом, так как постоянная a при подсчете количества операций будет больше в случае с алгоритмом с несколькими циклами.

сложность O(N2)

  • сложность алгоритма O(N2) означает, что при увеличении в два раза N количество операций возрастет примерно в четыре раза (т.е. количество операций пропорционально квадрату размера массива);
  • примером сложности O(N2) алгоритма является программа с двумя вложенными циклами, в каждом из которых N итераций (проходов); например, алгоритмы сортировки массивов методами «пузырька» или выбора.

алгоритм со сложностью O(N2)менее эффективен, чем алгоритм со сложностью O(N)

  • экспоненциальная сложность означает, что размер массива входит в показатель степени:

например сложность O(2N)

  • для больших N такие задачи не эффективны и не решаются за приемлемое время.

Типы алгоритмов в соответствии с их временной сложностью (перечислены с увеличением их сложности):

  • Постоянный тип — сложность O(1).
  • Логарифмический тип — сложность оценивается как O(log(n)).

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

  • Линейный тип — оценка равна O(n).
  • Квадратный тип — O(n2).

Свойственно алгоритмам, обрабатывающим все пары элементов данных.

  • Кубический, полиномиальный тип — O(n3), O(nm).
  • Экспоненциальный тип — O(tp(n)), t- константа,
  • p(n) — некоторая полиномиальная функция.
  • Факториальный тип — O(n!). Обладает наибольшей временной сложностью среди всех известных типов.
    Присуще алгоритмам, которые выполняют перебор всевозможных сочетаний элементов.

Решение заданий

  1. (Демонстрационный вариант ЕГЭ 2018 год). На вход программы поступает последовательность из N целых
    положительных чисел, все числа в последовательности различны.
    Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26.
    Описание входных и выходных данных.
    В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
    В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.
    Пример входных данных:
    4
    2
    6
    13
    39
    Пример выходных данных для приведённого выше примера входных данных:
    4
    Пояснение. Из четырёх заданных чисел можно составить 6 попарных произведений: 2·6, 2·13, 2·39, 6·13, 6·39, 13·39 (результаты: 12, 26, 78, 78, 234, 507). Из них на 26 делятся 4 произведения (2·13=26; 2·39=78; 6·13=78; 6·39=234).
    Требуется написать эффективную по времени и по памяти программу для решения описанной задачи.
    Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
    Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.

Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени – 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения.
Укажите использованный язык программирования и его версию.

Содержание верного ответа(допускаются иные формулировки ответа, не искажающие его смысла)
Произведение двух чисел делится на 26, если выполнено одно из следующих условий (условия не могут выполняться одновременно).
А. Оба сомножителя делятся на 26.
Б. Один из сомножителей делится на 26, а другой не делится.
В. Ни один из сомножителей не делится на 26, но один сомножитель
делится на 2, а другой – на 13.
Примечание для проверяющего. Условие делимости произведения на 26
можно сформулировать проще, например, так:
(один из сомножителей делится на 26) ИЛИ
(один сомножитель делится на 2, а другой – на 13).
Но в этом случае пара сомножителей может удовлетворять обоим условиям, что затруднит подсчёт количества пар.
При вводе чисел можно определять, делится ли каждое из них на 26, 2 и 13,
и подсчитывать следующие значения:
1) n26 – количество чисел, кратных 26;
2) n13 – количество чисел, кратных 13, но не кратных 26;
3) n2 – количество чисел, кратных 2, но не кратных 26.
Примечание для проверяющего. Сами числа при этом можно не хранить.
Каждое число учитывается не более чем в одном из счётчиков.
Количество пар, удовлетворяющих условию А, можно вычислить по
формуле n26·(n26 – 1)/2.
Количество пар, удовлетворяющих условию Б, можно вычислить по
формуле n26·(N – n26).
Количество пар, удовлетворяющих условию В, можно вычислить по
формуле n2·n13.
Поэтому искомое количество пар вычисляется по формуле
n26·(n26 – 1)/2 + n26·(N – n26) + n2·n13.
Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC)

var
N: integer; {количество чисел}
a: integer; {очередное число}
n26, n13, n2: integer;
k26: integer; {количество требуемых пар}
i: integer;
begin
readln(N);
n26:=0; n13:=0; n2:=0;
for i:=1 to N do begin
readln(a);
if a mod 26 = 0 then
n26 := n26+1
else if a mod 13 = 0 then
n13 := n13 + 1
else if a mod 2 = 0 then
n2 := n2 + 1;
end;
k26 := n26(n26-1) div 2 + n26(N-n26) + n2*n13;
writeln(k26)
end.

Top