Алгоритм записанный на естественном языке обрабатывающий цепочки символов или списки: Конспект по информатике "Алгоритм, записанный на естественном языке, обрабатывающий цепочки символов или списки" (9 класс)

Конспект по информатике «Алгоритм, записанный на естественном языке, обрабатывающий цепочки символов или списки» (9 класс)

Тема — «Алгоритм, записанный на естественном языке, обрабатывающий цепочки символов или списки»

Задача. Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом. Сначала вычисляется длина исходной цепочки символов; если она нечётна, то удаляется средний символ цепочки, а если чётна, то в начало цепочки добавляется символ Л. В полученной цепочке символов каждая буква заменяется буквой, следующей за ней в русском алфавите (А — на Б, Б — на В и т. д., а Я — на А). Получившаяся таким образом цепочка является результатом работы алгоритма.

Например, если исходной была цепочка РУКА, то результатом работы алгоритма будет цепочка МСФЛБ, а если исходной была цепочка СОН, то результатом работы алгоритма будет цепочка ТО.

Дана цепочка символов РОГ. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (т. е. применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм)? Русский алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.

Пояснение.

Применим алгоритм: РОГ (нечётное) → РГ → СД. Применим его ещё раз: СД (чётное) → ЛСД → МТЕ.

Задача. Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом. Сначала вычисляется длина исходной цепочки символов; если она нечётна, то дублируется средний символ цепочки символов, а если чётна, то в середину цепочки добавляется буква А. В полученной цепочке символов каждая буква заменяется буквой, следующей за ней в русском алфавите (А — на Б, Б — на В и т. д., а Я — на А). Получившаяся таким образом цепочка является результатом работы алгоритма.

Например, если исходной была цепочка КОТ, то результатом работы алгоритма будет цепочка ЛППУ, а если исходной была цепочка ВАНЯ, то результатом работы алгоритма будет цепочка ГББОА.

Дана цепочка символов САН. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (т. е. применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм)? Русский алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.

Пояснение.

Применим алгоритм: САН (нечётное) → СААН →

ТББО. Применим его ещё раз:ТББО (чётное) → ТБАБО → УВБВП.

Ответ: УВБВП.

Задача. Автомат получает на вход два двузначных десятичных числа. По полученным числам строится новое десятичное число по следующим правилам.

1. Вычисляются два числа — сумма цифр первого числа и сумма цифр второго числа.

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

Пример. Исходные числа: 73 и 45. Сумма цифр первого числа: 10, сумма цифр второго числа: 9. Результат: 910.

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

211 1717 1817 1718 1719 219 21 10

В ответе запишите только количество чисел.

Пояснение.

Проанализируем каждое число. Число 211 может быть результатом работы автомата, в этом случае исходное чисоа могли быть 20 и 56. Число 1717 может быть результатом работы автомата, в этом случае исходные числа могли быть 89 и 98. Число 1817 не может быть результатом работы автомата, поскольку числа записываются в порядке неубывания. Число 1718 может быть результатом работы автомата, в этом случае исходное числа могли быть 89 и 99. Число 1719 не может быть результатом работы автоматаа, поскольку невозможно получить число 19 как сумму двух цифр десятичного числа. Число 219 не может быть результатом работы автомата, поскольку если предположить, что это числа 2 и 19, записанные в порядке неубывания, видим что число 19 нельзя получить как как сумму двух цифр десятичного числа, а если это числа 21 и 9, то возникает противоречие, потому что числа должны записываться в порядке неубывания. Число 21 не может быть результатом работы автомата, поскольку числа записываются в порядке неубывания. Число 10 может быть результатом работы автомата,в этом случае исходное число могло быть 6400.

Ответ: 4.

Задача. Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом. Сначала вычисляется длина исходной цепочки символов. Если она нечётна, то в исходной цепочке символов удаляется средний символ, а если чётна, то в конец цепочки добавляется символ 2. В полученной строке каждая цифра заменяется на следующую (0 заменяется на 1, 1 — на 2, и т. д., а 9 заменяется на 0).

Получившаяся таким образом цепочка является результатом работы алгоритма.

Например, если исходной цепочкой была цепочка 234, то результатом работы алгоритма будет цепочка 35, а если исходной цепочкой была 56, то результатом работы алгоритма будет цепочка 673. Дана цепочка символов 562341. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (то есть применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм)?

Пояснение.

Применим алгоритм: 562341 (чётное) → 5623412 → 6734523.

Применим его ещё раз: 6734523 (нечётное) → 673523 → 784634.

Ответ: 784634.

Задача. Автомат получает на вход четырёхзначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.

1. Вычисляются два числа — сумма первой и второй цифр и сумма третьей и четвертой цифр заданного числа.

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

Пример. Исходное число: 2177. Поразрядные суммы: 3, 14. Результат: 314.

Определите, сколько из приведённых ниже чисел может получиться в результате работы автомата.

1915 10 110 1516 1211 316 1519 116 1515

В ответе запишите только количество чисел.

Пояснение.

Проанализируем каждое число.

Число 1915 не может быть результатом работы автомата, поскольку числа записываются в порядке неубывания.

Число 10 может быть результатом работы автомата, в этом случае исходное число могло быть 5500.

Число 110 может быть результатом работы автомата, в этом случае исходное число могло быть 5601.

Число 1516 может быть результатом работы автомата, в этом случае исходное число могло быть 7888.

Число 1211 не может быть результатом работы автомата, поскольку числа записываются в порядке неубывания.

Число 316 может быть результатом работы автомата,в этом случае исходное число могло быть 3088.

Число 1519 не может быть результатом работы автомата, поскольку невозможно получить число 19 как сумму двух цифр десятичного числа.

Число 116 может быть результатом работы автомата,в этом случае исходное число могло быть 1088.

Число 1515 может быть результатом работы автомата,в этом случае исходное число могло быть 7878.

Ответ: 5.

Задача: Цепочка из трёх бусин, помеченных латинскими буквами, формируется по следующему правилу:

в конце цепочки стоит одна из бусин D, B, A;

на первом месте – одна из бусин C, B, A, F, которой нет на третьем месте;

на втором месте–одна из бусин C, D, F не стоящая на первом месте.

Определите, сколько из перечисленных цепочек созданы по этому правилу?

CCB FDA ABD ADD BCB CFA BCA BFA BDC

В ответе запишите только количество цепочек.

Задача4: Автомат получает на вход четырёхзначное десятичное число, в котором есть как чётные, так и нечётные цифры. По полученному числу строится новое десятичное число по следующим правилам.

1. Вычисляются два числа – сумма чётных цифр и сумма нечётных цифр заданного числа.

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

Пример. Исходное число: 2177. Сумма чётных цифр — 2, сумма нечётных цифр — 15. Результат: 215.

Определите, сколько из приведённых ниже чисел могут получиться
в результате работы автомата.

419 1319 2014 1811 1212 205 322 294 55

В ответе запишите только количество чисел.

Задача: Цепочка из трёх бусин, помеченных латинскими буквами, формируется по следующему правилу:

в середине цепочки стоит одна из бусин B, E, C, H;

в конце – одна из бусин D, H, B, которой нет на втором месте;

на первом месте – одна из бусин D, H, E, C, не стоящая в конце.

Определите, сколько из перечисленных цепочек созданы по этому правилу?

HEH CHD EBB EED EDH HCD BEH HEB DBH

В ответе запишите только количество цепочек.

Задача: Автомат получает на вход пятизначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.

1. Вычисляются два числа – сумма первой, третьей и пятой цифр и сумма второй и четвёртой цифр заданного числа.

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

Пример. Исходное число: 15177. Поразрядные суммы: 9, 12. Результат: 912.

Определите, сколько из приведённых ниже чисел могут получиться
в результате работы автомата.

1220 120 210 2012 1920 2019 212 2919 1929

В ответе запишите только количество чисел.

Задача 5: Автомат получает на вход пятизначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.
1. Вычисляются два числа – сумма первых трёх цифр и сумма последних трёх цифр.
2. Полученные два числа записываются друг за другом в порядке неубывания (без разделителей).
Определите, сколько из приведённых ниже чисел могут получиться
в результате работы автомата.
2828 2512 2518 2524 2425 1825 1225 123

Решение:

Порядок неубывания,значит порядок возрастания.
2828 не может,так как если мы введём максимальное число 99999,то будет 2727
2512 не может, так как порядок возрастания,а 25>12
2518 не может, так как порядок возрастания,а 25>18
2524 не может, так как порядок возрастания,а 25>24
2425 может(число 78997)
1825 может(число 72979)
1225 может(число 12979)
123 не может,существует 2 варианта записи этого числа:
1)12 и 3,но такого быть не может,так как 12>3
2)1 и 23,но такого быть не может,так как чтобы получилось 23 должны быть числа хх599,а 1 получается слева, значит среднее число максимум 1,но нам оно не подходит
Итак,подходят 2425,1825,1225
Ответ: 3

Задача: Автомат получает на вход пятизначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.
1. Вычисляются два числа – сумма первой, третьей и пятой цифр и сумма второй и четвертой цифр заданного числа.
2. Полученные два числа записываются друг за другом в порядке неубывания (без разделителей). Пример. Исходное число: 15177. Поразрядные суммы: 9, 12. Результат: 912.
Определите, сколько из приведённых ниже чисел могут получиться
в результате работы автомата.
40 1030 130 1320 2019 1920 2013 213 3010
В ответе запишите только количество чисел.

Решение:

1. Отметим, что оба получающихся числа независимы друг от друга,

2. Первое число — сумма трех цифр, следовательно его величина может быть в пределах от 0+0+0=0 до 9+9+9=27. Второе число — сумма двух цифр, поэтому его величина может быть в пределах от 0+0=0 до 9+9=18. На этом основании бракуем все числа, у которых вторая цифра больше 27 и/или первая цифра больше 18.

40 — не подходит (4,0), нарушен порядок неубывания, 130 — не подходит (13,0), 1320 — (13,20) — подходит, нарушен порядок неубывания, 2013 — не подходит (20,13), нарушен порядок неубывания, 213 — подходит (2,13).
Ответ: 2 числа

1) первое число это 40. Делим число 40 на два числа это 4 и 0. 4 и 0 мы можем использовать по условию задачи по первому пункту,но ко второму пункту он не подходит,потому что записан в порядке убывания,а как мы уже поняли по условию,числа должны быть записаны в порядке не убывания(2 пункт задачи)
2) смотрим второе число 1030 ,делим его на два числа 10 и 30, это число нам не подходит,потому что в нём присутствует число 30,а число 30 нам нельзя использовать по условию задачи (1 пункт)
3) смотрим на 3 число 130,разделили его на два числа( мы его можем разделить двумя способами первый способ это 1 и 30,в этом случае он нам не подойдёт, второй способ (13 и 0) в этом случае он нам подойдёт по первому пункту, но нужно проверит второй пункт число 13 и 0 записаны по убыванию, по второму пункту это число не подходит так как в условии говорится что числа должны быть записаны непоубыванию(а если не по убыванию ,то следовательно это или по возрастанию либо должны быть равны друг другу(например 1616,1515,1414 и тд.).

Задача: Автомат получает на вход трёхзначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.

1. Вычисляются два числа – сумма старшего и среднего разрядов, а также сумма среднего и младшего разрядов заданного числа.

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

Пример. Исходное число: 277. Поразрядные суммы: 9, 14. Результат: 914.

Определите, сколько из приведённых ниже чисел могут получиться
в результате работы автомата.

1414 148 145 142 214 514 814 114

В ответе запишите только количество чисел.

Задание 16 № 874. Автомат получает на вход четырёхзначное десятичное число. Новое десятичное число строится по следующим правилам.

1. Вычисляются два числа — сумма «крайних» цифр четырёхзначного числа и сумма «средних» цифр четырёхзначного числа.

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

Пример. Исходное число: 7345. Сумма «крайних» цифр: 12, сумма «средних» цифр числа: 7. Результат: 127.

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

211 1717 1817 1718 1916 219 21 10

В ответе запишите только количество чисел.

Пояснение.

Проанализируем каждое число.

Число 211 не может быть результатом работы автомата, поскольку поскольку если предположить, что это числа 21 и 1, записанные в порядке невозрастания, видим что число 21 нельзя получитсь как как сумму двух цифр десятичного числа, а если это числа 2 и 11, то возникает противоречие, потому что числа должны записываться в порядке невозрастания.

Число 1717 может быть результатом работы автомата, в этом случае исходное число могло быть 9988.

Число 1817 может быть результатом работы автомата, в этом случае исходное число могло быть 8999.

Число 1718 не может быть результатом работы автомата, поскольку числа записываются в порядке невозрастания.

Число 1916 не может быть результатом работы автомата, поскольку невозможно получить число 19 как сумму двух цифр десятичного числа. Число 219 не может быть результатом работы автомата, поскольку если предположить, что это числа 21 и 2, записанные в порядке неневозрастания, видим что число 21 нельзя получитсь как как сумму двух цифр десятичного числа, а если это числа 2 и 19, то возникает противоречие, потому что числа должны записываться в порядке невозрастания.

Число 21 может быть результатом работы автомата, в этом случае исходное число могло быть 2010.

Число 10 может быть результатом работы автомата,в этом случае исходное число могло быть 5005.

Ответ: 4.

Задание 16 № 1067. Автомат получает на вход трёхзначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.

1. Вычисляются два числа — сумма старшего и среднего разрядов, а также сумма среднего и младшего разрядов заданного числа.

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

Пример. Исходное число: 277. Поразрядные суммы: 9, 14. Результат: 149.

Определите, сколько из приведённых ниже чисел может получиться в результате работы автомата.

1515 159 153 1915 1519 315 915 115

В ответе запишите только количество чисел.

Пояснение.

Проанализируем каждое число.

Число 1515 может быть результатом работы автомата, в этом случае исходное число могло быть 787.

Число 159 может быть результатом работы автомата, в этом случае исходное число могло быть 872.

Число 153 не может быть результатом работы автомата, поскольку в таком случае необходимо чтобы сумма первой и второй цифры была 15, а второй и третьей — 3, что невозможно, поскольку минимальное значение второй цифры — 6.

Число 1915 не может быть результатом работы автомата, поскольку число 19 невозможно получить сложением двух цифр.

Число 1519 не может быть результатом работы автомата, поскольку полученные два числа записываются друг за другом в порядке невозрастания.

Число 315 не может быть результатом работы автомата, поскольку число 31 невозможно получить сложением двух цифр.

Число 115 может быть результатом работы автомата, в этом случае исходное число могло быть 650.

Ответ: 3.

Задание 16 № 1087. Автомат получает на вход пятизначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.

1. Вычисляются два числа — сумма первой, третьей и пятой цифр и сумма второй и четвёртой цифр заданного числа.

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

Пример. Исходное число: 15177. Поразрядные суммы: 9, 12. Результат: 912.

Определите, сколько из приведённых ниже чисел может получиться в результате работы автомата.

30 1528 116 1519 2019 1920 1915 316 2815

В ответе запишите только количество чисел.

Пояснение.

Проанализируем каждое число.

Число 30 не может быть результатом работы автомата, поскольку числа записываются в порядке неубывания.

Число 1528 не может быть результатом работы автомата, поскольку число 28 невозможно получить сложением двух цифр.

Число 116 может быть результатом работы автомата, в этом случае исходное число могло быть 18080.

Число 1519 может быть результатом работы автомата, в этом случае исходное число могло быть 57589.

Число 2019 не может быть результатом работы автомата, поскольку числа записываются в порядке неубывания.

Число 1920 не может быть результатом работы автомата, поскольку число 20 невозможно получить сложением двух цифр, а число 192 — сложением трёх цифр.

Число 1915 не может быть результатом работы автомата, поскольку числа записываются в порядке неубывания.

Число 316 может быть результатом работы автомата, в этом случае исходное число могло быть 18181.

Число 2815 не может быть результатом работы автомата, поскольку числа записываются в порядке неубывания.

Ответ: 3.

Задание 16 № 1130. Цепочка из четырёх бусин, помеченных латинскими буквами, формируется по следующему правилу:

– на третьем месте цепочки стоит одна из бусин H, E;

– на втором месте — одна из бусин D, E, C, которой нет на третьем месте;

– в начале стоит одна из бусин D, H, B, которой нет на втором месте;

– в конце — одна из бусин D, E, C, не стоящая на первом месте.

Определите, сколько из перечисленных цепочек созданы по этому правилу?

DEHD HEHC DCEE DDHE DCHE HDHD BHED EDHC DEHE

В ответе запишите только количество цепочек.

Пояснение.

Первая цепочка DEHD не удовлетворяет четвёртому условию правила, четвёртая DDHE — третьему. Седьмая цепочка BHED не удовлетворяет второму условию правила. Восьмая цепочка EDHC не удовлетворяет третьему условию правила.

Таким образом, имеем пять цепочек, удовлетворяющих условию.

Ответ: 5.

Задание 16 № 1150. Автомат получает на вход четырёхзначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.

1. Вычисляются два числа — сумма четных цифр и сумма нечетных цифр заданного числа.

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

Пример. Исходное число: 2177. Сумма четных цифр — 2, сумма нечетных цифр — 15. Результат: 152.

Определите, сколько из приведённых ниже чисел могут получиться в результате работы автомата.

194 1913 1420 1118 1212 205 420 294 55

В ответе запишите только количество чисел.

Пояснение.

Результатом работы автомата могут быть числа 194 (исходное число — 9554), 1212 (исходное число — 6765), 205 (исходное число — 8845).

Таким образом, имеем три числа.

Ответ: 3.

задание 16 № 1269. Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу:

– в середине цепочки стоит одна из бусин B, E, C, H;

– в конце – одна из бусин D, H, B, которой нет на втором месте;

– на первом месте – одна из бусин D, H, E, C, не стоящая в конце.

Определите, сколько из перечисленных цепочек созданы по этому правилу?

HEH CHD EBB EED EDH HCD BEH HEB DBH

В ответе запишите только количество цепочек.

Пояснение.

Первому условию правила не соответствует последняя цепочка EDH. Второму условию не соответствует цепочка EBB. Третьему условию не соответствуют цепочки BEH, HEH.

Таким образом, пять цепочек (CHD, EED, HCD, HEB, DBH) сформированы по предложенному правилу.

Ответ: 5.

Решение 16 задания огэ информатика про цепочки символов

На уроке рассмотрен материал для подготовки к ОГЭ (ГИА) по информатике, разбор 16 задания. Объясняется тема об алгоритмах, записанных на естественном языке и обрабатывающих цепочки символов или списки.

ОГЭ по информатике 16 задания объяснение

16-е задание: «Алгоритм, записанный на естественном языке, обрабатывающий цепочки символов или списки».
Уровень сложности — повышенный,
Максимальный балл — 1,
Примерное время выполнения — 7 минут.

ГИА и ОГЭ информатика разбор задания 16

Разбор задания 16.1:

Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом:

Сначала вычисляется длина исходной цепочки символов; если она нечётна, то удаляется средний символ цепочки, а если чётна, то в начало цепочки добавляется символ Л.
В полученной цепочке символов каждая буква заменяется буквой, следующей за ней в русском алфавите (А — на Б, Б — на В и т. д., а Я — на А).
Получившаяся таким образом цепочка является результатом работы алгоритма.

Русский алфавит:
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.

✍ Решение:

Выполним алгоритм дважды: первый раз — результаты запишем красным цветом, второй — синим цветом.


1.
РОГ → РГ → СД
^{нечетное;  Р - С, Г - Д}


2.
СД → ЛСД → МТЕ
^{четное;  Л - М, С - Т, Д - Е}

Получили результат МТЕ.

Результат: МТЕ

Разбор задания 16.2:

Автомат получает на вход два двузначных десятичных числа. По полученным числам строится новое десятичное число последующим правилам:

Вычисляются два числа — сумма цифр первого числа и сумма цифр второго числа.
Полученные два числа записываются друг за другом в порядке неубывания (без разделителей).

Пример. Исходные числа: 73 и 45. Сумма цифр первого числа: 10, сумма цифр второго числа: 9.
Результат: 910.

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


211  1717  1817  1718  1719  219  21  10

В ответе запишите только количество чисел.

✍ Решение:

Рассмотрим последовательно все числа.
Каждое число будем проверять на два основных признака:
1. Наибольшая сумма двух цифр исходного числа — это 18: так как это и есть сумма наибольших двух цифр: 9 + 9 = 18
2. Две получившихся суммы должны быть записаны в порядке неубывания: т.е. они могут быть либо одинаковыми, либо записаны в порядке возрастания — сначала меньшее, затем большее.


211
Разобьем на две отдельных суммы: 
21 и 1 - не может быть, поскольку 21 больше 18
2 и 11 - подходит (например, 1+1 и 8+3 или любые другие подходящие суммы)
2 и 11 записаны в порядке возрастания: 2 Число 211 подходит


1717
Разобьем на две отдельных суммы: 
17 и 17 - подходит (например, 8+9 и 8+9)
17 и 17 записаны в порядке неубывания, т.к. они равны (не убывают): 17 = 17

Число 1717 подходит


1817
Разобьем на две отдельных суммы: 
18 и 17 - подходит (например, 9+9 и 8+9)
18 и 17 не записаны в порядке неубывания: 18 > 17

Число 1817 не подходит


1718
Разобьем на две отдельных суммы: 
17 и 18 - подходит (например, 8+9 и 9+9)
17 и 18 записаны в порядке возрастания: 17 Число 1718 подходит


1719
Разобьем на две отдельных суммы: 
17 и 19 - не подходит (19 больше, чем 18 - наибольшего числа сложения двух цифр)

Число 1719 не подходит


219
Разобьем на две отдельных суммы: 
2 и 19 - не может быть, поскольку 19 больше 18 (наибольшего числа сложения двух цифр)
21 и 9 - не может быть, поскольку 21 больше 18 (наибольшего числа сложения двух цифр)

Число 219 не подходит


21
Разобьем на две отдельных суммы: 
2 и 1 - подходит (например, 1+1 и 1+0)
2 и 1 не записаны в порядке возрастания: 2 > 1

Число 21 не подходит


10
Разобьем на две отдельных суммы: 
1 и 0 - не может быть, поскольку 0 - не может быть суммой цифр двузначного числа.

Число 10 не подходит

Итого получаем 3 подходящих числа.

Результат: 3

Разбор задания 16.3:

Автомат получает на вход трёхзначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам:

Вычисляются два числа — сумма старшего и среднего разрядов, а также сумма среднего и младшего разрядов заданного числа.
Полученные два числа записываются друг за другом в порядке невозрастания (без разделителей).

Пример. Исходное число: 277. Поразрядные суммы: 9, 14.
Результат: 149.

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


1616   169   163   1916   1619   316   916   116

В ответе запишите только количество чисел.

✍ Решение:

Рассмотрим последовательно все числа.
Каждое число будем проверять на три основных признака:
1. Наибольшая сумма двух цифр исходного числа — это 18: так как это и есть сумма наибольших двух цифр: 9 + 9 = 18
2. Две получившихся суммы должны быть записаны в порядке невозрастания: т.е. они могут быть либо одинаковыми, либо записаны в порядке убывания — сначала большее, затем меньшее.
3. Одно из слагаемых двух сумм должно быть общим.


1616
Разобьем на две отдельных суммы: 
16 и 16 - по второму признаку подходит, поскольку 16 = 16
16 и 16 - по третьему признаку подходит (например, 7 + 9 и 9 + 7: цифра 9 - общая)

Число 1616 подходит


169
Разобьем на две отдельных суммы: 
16 и 9 - по второму признаку подходит, поскольку 16 > 9
16 и 9 - по третьему признаку подходит (например, 8 + 8 и 8 + 1: цифра 8 - общая)

Число 169 подходит


163
Разобьем на две отдельных суммы: 
16 и 3 - по второму признаку подходит, поскольку 16 > 3
16 и 3 - по третьему признаку НЕ подходит; возьмем наибольшую возможную для этого числа общую цифру 3: 
16 не может получиться из суммы двух цифр, одной из которых является 3.

Число 163 НЕ подходит


1916
Разобьем на две отдельных суммы: 
19 и 16 - по первому признаку НЕ подходит, поскольку наибольшая возможная сумма 18 (9+9), а в примере 19

Число 1916 НЕ подходит


1619
Разобьем на две отдельных суммы: 
16 и 19 - по второму признаку НЕ подходит, поскольку 16 Число 1619 НЕ подходит


316
Разобьем на две отдельных суммы: 
3 и 16 - по второму признаку НЕ подходит, поскольку 3 Число 316 НЕ подходит


916
Разобьем на две отдельных суммы: 
9 и 16 - по второму признаку НЕ подходит, поскольку 9 Число 916 НЕ подходит


116
Разобьем на две отдельных суммы. Получим два варианта: 1 и 16, 11 и 6. Нам подходит 11 и 6: 
11 и 6 - по второму признаку подходит, поскольку 11 > 6
11 и 6 - по третьему признаку подходит (например, 7 + 4 и 4 + 2: цифра 4 - общая)

Число 116 подходит

Итого получаем 3 подходящих числа.

Результат: 3

Разбор задания 16.4: «Информатика и ИКТ: Типовые экзаменационные варианты», 2018, С.С. Крылов, Т.Е. Чуркина. ВАРИАНТ № 1

Автомат получает на вход двухзначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам:

Вычисляются два числа — сумма квадратов старшего и младшего разрядов, а также квадрат суммы старшего и младшего разрядов.
Полученные два числа записываются друг за другом в порядке неубывания (без разделителей).

Пример. Исходное число: 52. Вычисленные числа: 29, 49.
Результат: 2949.

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


10 11 25 59 95 2036 3264 6581

В ответе запишите только количество чисел.

✍ Решение:

Каждое число будем проверять на четыре основных признака, исходя из условия задания:
1. Общее число можно разделить на два числа, расположенных в порядке возрастания или равные друг другу.
2. Одно из чисел является квадратом какого-либо числа (можно извлечь корень).
3. Наибольшая сумма квадратов двух цифр исходного числа — это 162: так как это и есть сумма квадратов наибольших двух цифр: 9² + 9² = 162. Наименьшая сумма квадратов двух цифр исходного числа — это 1 (1² + 0² = 1)
4. Наибольший квадрат суммы двух цифр исходного числа — это 324: так как это и есть квадрат суммы наибольших двух цифр: (9 + 9)² = 324. Наименьший квадрат суммы двух цифр исходного числа — это 1 ((1 + 0)² = 1)
10


10
1. Разобьем на два отдельных числа в порядке неубывания: 1 | 0 
2. 1 и 0 - по второму признаку: 1 может являться квадратом единицы
⛔ 3. 1 и 0 - по третьему признаку: 1 может являться суммой квадратов двух цифр, а 0 - нет.

Число 10 не подходит


11
1. Разобьем на два отдельных числа в порядке неубывания: 1 | 1 
2. 1 и 1 - по второму признаку: 1 может являться квадратом единицы
3. 1 и 1 - по третьему признаку: 1 может являться суммой квадратов двух цифр.
   1² + 0² = 1
4. 1 и 1 - по четвертому признаку: 1 может являться наименьшим квадратом суммы двух цифр:
   (1 + 0)² = 1 

Число 11 подходит (для исходного числа 10)


25
1. Разобьем на два отдельных числа в порядке неубывания: 2 | 5 
⛔ 2. 2 и 5 - по второму признаку: ни число 2, ни число 5 не может являться квадратом числа

Число 25 не подходит


59
1. Разобьем на два отдельных числа в порядке неубывания: 5 | 9 
2. 5 и 9 - по второму признаку: 9 может являться квадратом числа 3
4. 5 и 9 - по четвертому признаку:
  из предыдущ пункта:  3 = 2+1; 5 = 2² + 1²
3. 5 и 9 - по третьему признаку: 9 может являться квадратом числа 3, а 3 = 2 + 1
   9 = (2 + 1)²

Число 59 подходит (например, для исходного числа 21)


95
⛔ 1. Невозможно разбить на два отдельных числа в порядке неубывания: 9 | 5 

Число 95 не подходит

2036


2036
1. Разобьем на два отдельных числа в порядке неубывания: 20 | 36 
2. 20 и 36 - по второму признаку: 36 может являться квадратом числа 6
4. 20 и 36 - по четвертому признаку:
   из предыдущ пункта:  6 = 4+2; 20 = 4² + 2²
3. 20 и 36 - по третьему признаку: 36 может являться квадратом числа 6, а 6 = 2 + 4
   36 = (2 + 4)²

Число 2036 подходит (например, для исходного числа 24)

3264


3264
1. Разобьем на два отдельных числа в порядке неубывания: 32 | 64  или 3 | 264
2. 32 и 64 - по второму признаку: 64 может являться квадратом числа 8
4. 32 и 64 - по четвертому признаку:
   из предыдущ пункта:  8 = 4+4; 32 = 4² + 4²
3. 32 и 64 - по третьему признаку: 64 может являться квадратом числа 8, а 8 = 4 + 4
   64 = (4 + 4)²

Число 3264 подходит (например, для исходного числа 44)

6581


6581
1. Разобьем на два отдельных числа в порядке неубывания: 65 | 81
2. 65 и 81 - по второму признаку: 81 может являться квадратом числа 9
4. 65 и 81 - по четвертому признаку:
   из предыдущ пункта:  9 = 8+1; 65 = 8² + 1²
3. 65 и 81 - по третьему признаку: 81 может являться квадратом числа 9, а 9 = 8 + 1
   81 = (8 + 1)²

Число 6581 подходит (например, для исходного числа 81)

Итого получаем пять подходящих чисел:

10 11 25 59 95 2036 3264 6581

Ответ: 5

МБОУ СОШ №7: Главная

05.08.2020 Новости

29.07.2020 Новости

14.07.2020 Новости

09.07.2020 Новости

07.07.2020 Новости

10.06.2020 Новости

27.05.2020 Новости

21.05.2020 Новости

18.05.2020 Новости

23.04.2020 Новости

02.04.2020 Новости

18.03.2020 Новости

15.02.2020 Новости

14.02.2020 Новости

24.01.2020 Новости

10.01.2020 Новости

10.12.2019 Новости

28.11.2019 Новости

20.11.2019 Новости

15.11.2019 Новости

14.11.2019 Новости

12.11.2019 Новости

11.10.2019 Новости

10.10.2019 Новости

18.09.2019 Новости

16.09.2019 Новости

04.09.2019 Новости

27.06.2019 Новости

07.06.2019 Новости

30.05.2019 Новости

17.05.2019 Новости

07.05.2019 Новости

30.04.2019 Новости

25.04.2019 Новости

17.04.2019 Новости

12.04.2019 Новости

04.04.2019 Новости

20.03.2019 Новости

14.03.2019 Новости

07.03.2019 Новости

06.03.2019 Новости

26.02.2019 Новости

20.02.2019 Новости

08.02.2019 Новости

31.01.2019 Новости

22.01.2019 Новости

10.01.2019 Новости

26.12.2018 Новости

25.12.2018 Новости

15.12.2018 Новости

12.12.2018 Новости

06.12.2018 Новости

04.12.2018 Новости

29.11.2018 Новости

20.11.2018 Новости

16.11.2018 Новости

09.10.2018 Новости

24.09.2018 Новости

05.09.2018 Новости

04.09.2018 Новости

29.08.2018 Новости

27.06.2018 Новости

25.06.2018 Новости

14.06.2018 Новости

31.05.2018 Новости

13.04.2018 Новости

06.03.2018 Новости

01.03.2018 Новости

15.02.2018 Новости

13.02.2018 Новости

23.01.2018 Новости

16.01.2018 Новости

26.12.2017 Новости

23.12.2017 Новости

05.12.2017 Новости

24.11.2017 Новости

14.11.2017 Новости

26.10.2017 Новости

16.10.2017 Новости

29.09.2017 Новости

21.09.2017 Новости

13.06.2017 Новости

26.05.2017 Новости

23.05.2017 Новости

12.05.2017 Новости

Решение ОГЭ по информатике Задача №16

Решение ГИА по информатике 16 задание из демоверсии 2017 года. Задание на умение исполнить алгоритм, записанный на естественном языке, обрабатывающий цепочки символов или списки.

Давайте познакомимся с условием задачи.

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

Я сначала взял и отбросил все четырехзначные числа. Мне показалось что это исходные числа, на самом деле нет это результирующие числа.

Наша цель понять какие числа нам давали на вход что бы получились такие значения, а точнее нас интересует количество вот таких чисел.

Давайте перейдем к решению, но сначала разберем некие краткие теоретические положения.

Пусть abc – математическая запись трехзначного числа, где

a – старший разряд это самый левый;

b – средний разряд;

с – младший разряд это самый правый.

Разряды a, b, c – могут принимать значения от 0 до 9.

Следовательно, сумма двух любых разрядов находится в диапазоне от 0 до 18. Почему так потому что мы говорили, что разряды у нас от 0 до 9. Если мы к нулю прибавим нуль получим тоже нуль, а 9+9=18.

В соответствии с условиями задачи получается:

a + b – 1 число

b + c – 2 число

Сейчас уже можно приступать непосредственно к анализу этих восьми чисел, но еще есть фундаментальный момент.

1 число от 2 числа не может отличаться более чем на 9 единиц. Это очень важно.

Итак, я предлагаю как всегда использовать процессинговые таблицы.

Вообще табличная структура крайне удобна для анализа информации.

1616 наша цель разбить на 2 числа. Это 16 и 16.

Проверяем:
от нуля до 18 принадлежит – да
невозрастание – да
Отличие более чем на 9 единиц – нет
Пример – 888
Число подходит – да

Это означает что, подав трехзначное число, например, 888 мы сможем получить 1616 т. е. данную комбинацию можно получить.

169 разбиваем на 2 числа 16 и 9.

невозрастание – да
Отличие более чем на 9 единиц – нет
Пример – 972
Число подходит – да

163 разбиваем на 2 числа 16 и 3.

невозрастание – да
Отличие более чем на 9 единиц – да
Пример – нет
Число подходит – нет

1916 разбиваем на 2 числа нет.

невозрастание – нет
Отличие более чем на 9 единиц – нет
Пример – нет
Число подходит – нет

1619 разбиваем на 2 числа нет.

невозрастание – нет
Отличие более чем на 9 единиц – нет
Пример – нет
Число подходит – нет

316 разбиваем на 2 числа 3 и 16.

невозрастание – нет
Отличие более чем на 9 единиц – нет
Пример – нет
Число подходит – нет

916 разбиваем на 2 числа 9 и 16.

невозрастание – нет
Отличие более чем на 9 единиц – нет
Пример – нет
Число подходит – нет

116 разбиваем на 2 числа 11 и 6.

невозрастание – да
Отличие более чем на 9 единиц – нет
Пример – 924
Число подходит – да

Вывод: Из приведенных чисел только 3 могут получится в результате работы автомата. Нас просили в ответ выписать количество таких чисел.

Ответ: 3

Материал для подготовки к ЕГЭ (ГИА) по информатике и икт (9 класс): Самостоятельная работа по информатике «Алгоритм, записанный на естественном языке, обрабатывающий цепочки символов или списки» (для подготовки к ОГЭ)

Самостоятельная работа по информатике

«Алгоритм, записанный на естественном языке, обрабатывающий цепочки символов или списки»

(для подготовки к ОГЭ)

№ 1

Автомат получает на вход четырёхзначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.

1. Вычисляются два числа — сумма первой и второй цифр и сумма третьей и четвёртой цифр заданного числа.

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

Определите, сколько из приведённых ниже чисел могут получиться в результате работы автомата.

2110 10 1617 1513 518 1414 119

В ответе запишите только количество чисел.

№2

Автомат получает на вход два двузначных десятичных числа. По полученным числам строится новое десятичное число по следующим правилам.

1. Вычисляются два числа — сумма цифр первого числа и сумма цифр второго числа.

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

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

312 1515 1614 1216 517 31

В ответе запишите только количество чисел.

№3

Автомат получает на вход четырёхзначное десятичное число. Новое десятичное число строится по следующим правилам.

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

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

313 1818 1514 2016 31 11

В ответе запишите только количество чисел.

№4

1. Вычисляются два числа — сумма первой и второй цифр и сумма третьей и четвертой цифр заданного числа.

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

Определите, сколько из приведённых ниже чисел может получиться в результате работы автомата.

1916 10 120 1617 1310 417 1414

В ответе запишите только количество чисел.

№5

Автомат получает на вход трёхзначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.

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

Определите, сколько из приведённых ниже чисел может получиться в результате работы автомата.

1717 148 164 1913 1218 418 118

В ответе запишите только количество чисел.

«Конспект по информатике «Алгоритм, записанный на естественноо языке, обрабатывающий цепочки символов или списки» (9 класс)»

Тема — «Алгоритм, записанный на естественном языке, обрабатывающий цепочки символов или списки»
Задача. Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом. Сначала вычисляется длина исходной цепочки символов; если она нечётна, то удаляется средний символ цепочки, а если чётна, то в начало цепочки добавляется символ Л. В полученной цепочке символов каждая буква заменяется буквой, следующей за ней в русском алфавите (А — на Б, Б — на В и т. д., а Я — на А). Получившаяся таким образом цепочка является результатом работы алгоритма.
Например, если исходной была цепочка РУКА, то результатом работы алгоритма будет цепочка МСФЛБ, а если исходной была цепочка СОН, то результатом работы алгоритма будет цепочка ТО.
Дана цепочка символов РОГ. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (т. е. применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм)? Русский алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.
Пояснение.
Применим алгоритм: РОГ (нечётное) → РГ → СД. Применим его ещё раз: СД (чётное) → ЛСД → МТЕ.
Задача. Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом. Сначала вычисляется длина исходной цепочки символов; если она нечётна, то дублируется средний символ цепочки символов, а если чётна, то в середину цепочки добавляется буква А. В полученной цепочке символов каждая буква заменяется буквой, следующей за ней в русском алфавите (А — на Б, Б — на В и т. д., а Я — на А). Получившаяся таким образом цепочка является результатом работы алгоритма.
Например, если исходной была цепочка КОТ, то результатом работы алгоритма будет цепочка ЛППУ, а если исходной была цепочка ВАНЯ, то результатом работы алгоритма будет цепочка ГББОА.
Дана цепочка символов САН. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (т. е. применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм)? Русский алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.
Пояснение.
Применим алгоритм: САН (нечётное) → СААН → ТББО. Применим его ещё раз:ТББО (чётное) → ТБАБО → УВБВП.

Ответ: УВБВП.
Задача. Автомат получает на вход два двузначных десятичных числа. По полученным числам строится новое десятичное число по следующим правилам.
1. Вычисляются два числа — сумма цифр первого числа и сумма цифр второго числа.
2. Полученные два числа записываются друг за другом в порядке неубывания (без разделителей).

Пример. Исходные числа: 73 и 45. Сумма цифр первого числа: 10, сумма цифр второго числа: 9. Результат: 910.

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

211 1717 1817 1718 1719 219 21 10

В ответе запишите только количество чисел.
Пояснение.
Проанализируем каждое число. Число 211 может быть результатом работы автомата, в этом случае исходное чисоа могли быть 20 и 56. Число 1717 может быть результатом работы автомата, в этом случае исходные числа могли быть 89 и 98. Число 1817 не может быть результатом работы автомата, поскольку числа записываются в порядке неубывания. Число 1718 может быть результатом работы автомата, в этом случае исходное числа могли быть 89 и 99. Число 1719 не может быть результатом рабо

Решение задачи 16 «Алгоритм, записанный на естественном языке, обрабатывающий цепочки символов или списки» Информатика ОГЭ 9 класс

Задание 16. Обработка цепочки символов

Задание 16. Обработка цепочки символов (повышенный уровень, время 7 мин) Задания для самостоятельного решения: 1) Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим середину

Подробнее 6-1 (базовый уровень, время 4 мин)
6-1 (базовый уровень, время 4 мин) Тема: Выполнение и анализ простых алгоритмов. Что нужно знать: сумма двух цифр в десятичной системе счисления находится в диапазоне от 0 до 18 (9+9) в некоторых задачах
Подробнее Работа по информатике для 9 класса.
Работа по информатике для 9 класса. 1.Вид работы: итоговая работа по информатике в 9 классе Цель работы: оценка уровня достижения учащимися 9 класса планируемых результатов обучения информатике 2.Перечень
Подробнее Задания А5 по информатике
Задания А5 по информатике 1. Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность
Подробнее Задание 3. Информационное моделирование
Задание. Информационное моделирование (базовый уровень, время мин) Задания для самостоятельного решения: ) На схеме нарисованы дороги между пятью городами,,,, и указаны протяжённости дорог. Определите,
Подробнее B7 (повышенный уровень, время 2 мин)
К Поляков, 009-01 B7 (повышенный уровень, время мин) Тема: Кодирование чисел Системы счисления Что нужно знать: принципы кодирования чисел в позиционных системах счисления чтобы перевести число, скажем,
Подробнее A5 (базовый уровень, время 2 мин)
A5 (базовый уровень, время 2 мин) Тема: Проверка закономерностей методом рассуждений. Что нужно знать: в общем-то, никаких знаний из курса информатики здесь не требуется, эту задачу можно давать детям
Подробнее B8 (повышенный уровень, время 10 мин)
B8 (повышенный уровень, время 10 мин) Тема: Анализ алгоритма построения последовательности. Что нужно знать: в некоторых задачах (на RLE-кодирование, см. далее) нужно знать, что такое бит и байт, что байт
Подробнее B8 (повышенный уровень, время 2 мин)
К. Поляков, 009-011 B8 (повышенный уровень, время мин) Тема: Кодирование чисел. Системы счисления. Что нужно знать: принципы кодирования чисел в позиционных системах счисления чтобы перевести число, скажем,
Подробнее m := 0; for k := 6 to 12 do s := s+10;
Вариант 1. 1 ( 573) В одной из кодировок Unicode каждый символ кодируется 16 битами. Определите размер следующего предложения в данной кодировке в байтах. Я к вам пишу чего же боле? Что я могу ещё сказать?
Подробнее 16 (повышенный уровень, время 2 мин)
К. Поляков, 009-016 16 (повышенный уровень, время мин) Тема: Кодирование чисел. Системы счисления. Что нужно знать: принципы кодирования чисел в позиционных системах счисления чтобы перевести число, скажем,
Подробнее B8 (повышенный уровень, время 10 мин)
B8 (повышенный уровень, время 10 мин) Тема: Анализ алгоритма построения последовательности. Что нужно знать: в некоторых задачах (на RLE-кодирование, см. далее) нужно знать, что такое бит и байт, что байт
Подробнее A5 (базовый уровень, время 2 мин)
A5 (базовый уровень, время 2 мин) Тема: Проверка закономерностей методом рассуждений. Что нужно знать: в общем-то, никаких знаний из курса информатики здесь не требуется, эту задачу можно давать детям
Подробнее A5 (базовый уровень, время 2 мин)
A5 (базовый уровень, время 2 мин) Тема: Проверка закономерностей методом рассуждений. Что нужно знать: в общем- то, никаких знаний из курса информатики здесь не требуется, эту задачу можно давать детям
Подробнее А1 (базовый уровень, время 1 мин)
А1 (базовый уровень, время 1 мин) Тема: Системы счисления и двоичное представление информации в памяти компьютера. Что нужно знать: перевод чисел между десятичной, двоичной, восьмеричной и шестнадцатеричной
Подробнее ЕГЭ Н. В. Потехин
ЕГЭ 2017 Н. В. Потехин 1. Сколько существует натуральных чисел x, для которых выполнено неравенство 11011100 2 < x < DF 16? В ответе укажите только количество чисел, сами числа писать не нужно. 2. Логическая
Подробнее А1 (базовый уровень, время 1 мин)
А1 (базовый уровень, время 1 мин) Тема: Системы счисления и двоичное представление информации в памяти компьютера. Что нужно знать: перевод чисел между десятичной, двоичной, восьмеричной и шестнадцатеричной
Подробнее Тема: Системы счисления
Коротко о главном Тема: Системы счисления Системы счисления — это способ представления чисел и соответствующие ему правила действия над числами. Разнообразные системы счисления, который существовали раньше
Подробнее А1 (базовый уровень, время 1 мин)
А1 (базовый уровень, время 1 мин) Тема: Системы счисления и двоичное представление информации в памяти компьютера. Что нужно знать: перевод чисел между десятичной, двоичной, восьмеричной и шестнадцатеричной
Подробнее B13 (повышенный уровень, время 7 мин)
B13 (повышенный уровень, время 7 мин) Задачи для тренировки 1 : 1) У исполнителя Калькулятор две команды, которым присвоены номера: Сколько есть программ, которые число 1 преобразуют в число 16? 2) У исполнителя
Подробнее А1 (базовый уровень, время 2 мин)
А1 (базовый уровень, время 2 мин) Тема: Системы счисления и двоичное представление информации в памяти компьютера. Что нужно знать: перевод чисел между десятичной, двоичной, восьмеричной и шестнадцатеричной
Подробнее 1 (базовый уровень, время 1 мин)
1 (базовый уровень, время 1 мин) Тема: Системы счисления и двоичное представление информации в памяти компьютера. Что нужно знать: перевод чисел между десятичной, двоичной, восьмеричной и шестнадцатеричной
Подробнее Вариант КР105 Логика C:\Школа\Уроки\Химия
$Вариант КР105 Логика C:\Школа\Уроки\Химия$ Вариант КР105 1 Рассказ, набранный на компьютере, содержит 2 страницы, на каждой странице 60 строк, в каждой строке 64 символа. Определите информационный объѐм рассказа в байтах в кодировке KOI8-R, в которой
Подробнее 8 (базовый уровень, время 3 мин)
8 (базовый уровень, время 3 мин) Тема: Анализ программы. Что нужно знать: основные конструкции языка программирования: o объявление переменных o оператор присваивания o оператор вывода o циклы уметь выполнять
Подробнее ID_649 1/8 neznaika.pro
Вариант 7 Часть 1. При выполнении заданий 1 6 укажите только одну цифру, которая соответствует номеру правильного ответа. 1 Реферат, набранный на компьютере, содержит 24 страницы. Половина из этих страниц
Подробнее X Y Z F ) X Y Z 2) X Y Z 3) X Y Z 4) X Y Z
Программа вступительных испытаний в Академическую гимназию им. Д. К. Фаддеева Санкт-Петербургского государственного университета на программы среднего общего образования Информатика 10 класс Вступительные
Подробнее Алгоритм построения последовательности
Алгоритм построения последовательности Пример задания: Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа латинской буквы «А». Каждая из последующих
Подробнее nlp — частотный алгоритм для обработки естественного языка
Переполнение стека
Около
Товары
Для команд
Переполнение стека Общественные вопросы и ответы
Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
работы Программирование и связанные с ним технические возможности карьерного роста
Талант Нанимайте технических специалистов и создавайте свой бренд работодателя
реклама Обратитесь к разработчикам и технологам со всего мира
О компании
Загрузка…
Авторизоваться зарегистрироваться
Текущее сообщество
.
Оптимальный алгоритм сравнения для поиска совпадений строк в списке строк C #
Переполнение стека
Около
Товары
Для команд
Переполнение стека Общественные вопросы и ответы
Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
работы Программирование и связанные с ним технические возможности карьерного роста
Талант Нанимайте технических специалистов и создавайте свой бренд работодателя
реклама Обратитесь к разработчикам и технологам со всего мира
.Алгоритм
— генерирует все уникальные подстроки для данной строки
Переполнение стека
Около
Товары
Для команд
Переполнение стека Общественные вопросы и ответы
Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
работы Программирование и связанные с ним технические возможности карьерного роста
Талант Нанимайте технических специалистов и создавайте свой бренд работодателя
реклама Обратитесь к разработчикам и технологам со всего мира
О компании
Загрузка…
.
Обработка естественного языка: от основ до использования RNN и LSTM | by vibhor nigam
Подробное введение во все концепции, распространенные в мире обработки естественного языка

Одним из самых захватывающих достижений в мире машинного обучения является развитие способностей научить машину понимать человеческое общение , Сама эта часть машинного обучения называется обработкой естественного языка.
Этот пост представляет собой попытку объяснить основы обработки естественного языка и то, как в ней был достигнут быстрый прогресс с развитием глубокого обучения и нейронных сетей.
Прежде чем мы углубимся в это, необходимо понять основы
Что такое язык?
Язык, по сути, представляет собой фиксированный словарь слов, который используется сообществом людей для выражения и передачи своих мыслей.
Этот словарь преподается людям в процессе их взросления и в основном остается неизменным с небольшими добавлениями каждый год.
Поддерживаются сложные ресурсы, такие как словари, так что, если человек встречает новое слово, он или она может ссылаться на словарь, чтобы узнать его значение.Как только человек знакомится со словом, оно добавляется в его или ее словарный запас и может использоваться для дальнейшего общения.
Как компьютеры понимают язык?
Компьютер — это машина, работающая по математическим правилам. Ему не хватает сложных интерпретаций и понимания, которые люди могут сделать с легкостью, но он может выполнять сложные вычисления за секунды.
Для того, чтобы компьютер мог работать с любой концепцией, необходимо, чтобы существовал способ выразить указанную концепцию в виде математической модели.
Это ограничение сильно ограничивает объем и области естественного языка, с которыми компьютер может работать. До сих пор машины успешно выполняли задачи классификации и перевода.
Классификация — это, по сути, отнесение фрагмента текста к категории, а при переводе этот фрагмент преобразуется на любой другой язык.
Что такое обработка естественного языка?
Обработка естественного языка, или сокращенно NLP, в широком смысле определяется как автоматическая обработка естественного языка, такого как речь и текст, с помощью программного обеспечения.
Изучение обработки естественного языка существует уже более 50 лет и выросло из области лингвистики с появлением компьютеров. [1]
Подробное руководство по основам НЛП можно найти на сайте
Базовые преобразования
Как упоминалось ранее, для того, чтобы машина могла понимать естественный язык (язык, используемый людьми), ее необходимо преобразовать в своего рода математический каркас, который можно смоделировать. Ниже приведены некоторые из наиболее часто используемых техник, которые помогают нам в этом.
Токенизация, стемминг и леммитизация
Токенизация — это процесс разбиения текста на слова. Токенизация может произойти для любого символа, однако наиболее распространенный способ токенизации — это сделать это для символа пробела.
Основание — это грубый способ обрезки конца для получения основного слова и часто включает удаление деривационных аффиксов. Производный аффикс — это аффикс , с помощью которого одно слово образуется (происходит) от другого.Производное слово часто принадлежит к классу слов, отличному от исходного. Наиболее распространенным алгоритмом, используемым для этой цели, является алгоритм Портера.
Лемматизация выполняет словарный и морфологический анализ слова и обычно направлена только на удаление флективных окончаний. Флективное окончание — это группа букв, добавленных в конец слова, чтобы изменить его значение. Примерно флективных окончаний : -s. летучая мышь. летучие мыши.
Поскольку выделение корней происходит на основе набора правил, корневое слово, возвращаемое при выделении корней, не всегда может быть словом английского языка.С другой стороны, лемматизация сокращает флексивные слова должным образом, гарантируя, что корневое слово принадлежит английскому языку.
N-граммы
N-граммы относятся к процессу объединения соседних слов вместе для целей представления, где N представляет количество слов, которые должны быть объединены вместе.
Например, рассмотрим предложение: « Обработка естественного языка необходима для информатики. ”
Модель 1-грамм или unigram преобразует предложение в однословные комбинации и, таким образом, на выходе будет« Natural, Language, Processing, is, essential, to, Computer, Science »
Модель биграммы , с другой стороны, будет токенизировать ее в комбинацию из 2 слов каждое, и на выходе будет « Natural Language, Language Processing, Processing is, is, essential, important to, Computer, Computer Science »
Точно так же модель триграммы разбивает его на «Обработка естественного языка, Обработка языка есть, Обработка необходима, необходима, необходима для компьютера, для информатики», и модель n-грамм, таким образом, токенизирует предложение в комбинацию n слова вместе.
Разбиение естественного языка на n-граммы имеет важное значение для подсчета слов, встречающихся в предложениях, которые составляют основу традиционных математических процессов, используемых в обработке естественного языка.
Одним из наиболее распространенных методов достижения этого в представлении пакета слов является tf-idf
TF-IDF
TF-IDF — это способ оценки словарного запаса, чтобы обеспечить адекватный вес для слово пропорционально влиянию, которое оно оказывает на значение предложения.Оценка представляет собой произведение двух независимых оценок: частоты термина (tf) и обратной частоты в документе (idf).
Изображение предоставлено — Google
Частота термина (TF): Частота термина определяется как частота слова в текущем документе. ,
Частота обратного документа (IDF): это мера того, сколько информации предоставляет слово, т. Е. Является ли оно общим или редким во всех документах. Он рассчитывается как журнал (N / d), где N — общее количество документов, а d — количество документов, в которых встречается это слово.
Горячее кодирование
Горячее кодирование — это еще один способ представления слов в числовой форме. Длина вектора слов равна длине словаря, и каждое наблюдение представлено матрицей со строками, равными длине словаря, и столбцами, равными длине наблюдения, со значением 1, где слово словарный запас присутствует в наблюдении и нулевое значение там, где его нет.
Изображение предоставлено — Джон Крон (выбрано через поиск в Google)
Вложения слов
Встраивание слов — это собирательное название для набора методов языкового моделирования и изучения особенностей, в которых слова или фразы из словаря сопоставляются с векторами реальных чисел.Этот метод в основном используется с моделями нейронных сетей .
Концептуально это включает в себя проецирование слова из измерения, эквивалентного длине словарного запаса, в пространство более низкого измерения, с идеей, что похожие слова будут проецироваться ближе друг к другу.
Для понимания мы можем представить себе вложения как каждое слово, проецируемое в пространство характеристик, как показано на изображении ниже.
Каждое слово представлено в пространстве характеристик (Пол, Королевство, Возраст, Еда) и т. Д.
Однако на самом деле эти измерения не так ясны или легко понятны.Это не является проблемой, поскольку алгоритмы тренируются на математических отношениях между измерениями. То, что представлено измерением, не имеет смысла для нейронной сети с точки зрения обучения и прогнозирования.
Если кто-то хочет получить визуальное представление о линейной алгебре, проекциях и преобразованиях, которые являются основными математическими принципами, лежащими в основе ряда алгоритмов машинного обучения, я настоятельно рекомендую им посетить « Сущность линейной алгебры » от 3Blue1Brown ,
Мешок слов
Для алгоритма установления взаимосвязей между текстовыми данными он должен быть представлен в четком структурированном формате.
Пакет слов — это способ представления данных в табличном формате со столбцами, представляющими общий словарь корпуса, и каждой строкой, представляющей отдельное наблюдение. Ячейка (пересечение строки и столбца) представляет собой количество слов, представленных столбцом в этом конкретном наблюдении.
Он помогает машине понять предложение в простой для интерпретации парадигме матриц и, таким образом, позволяет применять к данным различные линейные алгебраические операции и другие алгоритмы для построения прогнозных моделей.
Ниже приведен пример модели мешка слов для выборки статей из медицинских журналов
Pictrue Credit -Google
Это представление работало очень хорошо и отвечало за создание моделей для некоторых из наиболее часто используемых машин. обучающие задачи, такие как обнаружение спама, классификатор настроений и другие.
Однако у этого представления есть два основных недостатка:
Он игнорирует порядок / грамматику текста и, таким образом, теряет контекст, в котором используется слово
Матрица, сгенерированная этим представлением, очень sparse и более тяготеют к наиболее употребительным словам.Подумайте об этом, алгоритмы в первую очередь работают над подсчетом слов, тогда как в языке важность слова на самом деле обратно пропорциональна частоте их появления. Слова с более высокой частотой встречаемости — это более общие слова, такие как, is, an, которые существенно не меняют значение предложения. Таким образом, становится важным правильно взвесить слова, чтобы отразить их адекватное влияние на значение предложения.
Матрица вложения
Матрица вложения — это способ представления вложений для каждого слова, присутствующего в словаре.Строки представляют размеры пространства для вложения слов, а столбцы представляют слова, присутствующие в словаре.
Чтобы преобразовать образец в его форму вложения, каждое слово в его одной горячей закодированной форме умножается на матрицу встраивания, чтобы получить встраивание слов для образца .
Следует иметь в виду, что здесь горячая кодировка просто относится к n-мерному вектору со значением 1 в позиции слова в словаре, где n — длина словаря.Эти горячие кодировки взяты из словаря, а не из серии наблюдений.
Рекуррентные нейронные сети или RNN, как их вкратце называют, являются очень важным вариантом нейронных сетей, активно используемых в обработке естественного языка.
Концептуально они отличаются от стандартной нейронной сети, поскольку стандартным вводом в RNN является слово, а не весь образец, как в случае стандартной нейронной сети. Это дает сети возможность работать с различной длиной предложений, что, , не может быть достигнуто в стандартной нейронной сети из-за ее фиксированной структуры.Это также обеспечивает дополнительное преимущество функций совместного использования, изученных в разных позициях текста , которые не могут быть получены в стандартной нейронной сети.
RNN обрабатывает каждое слово предложения как отдельный ввод, происходящий во время «t», и также использует значение активации в «t-1» в качестве ввода в дополнение к вводу в момент «t». На схеме ниже показана подробная структура архитектуры RNN.
Описанная выше архитектура также называется архитектурой «многие ко многим» с (Tx = Ty) i.е. количество входов = количество выходов. Такая структура весьма полезна при моделировании последовательности.
Помимо архитектуры, упомянутой выше, существуют три других типа архитектур RNN, которые обычно используются.
Многие к одному RNN : Архитектура «многие к одному» относится к архитектуре RNN, в которой много входов (Tx) используются для получения одного выхода (Ty). Подходящим примером использования такой архитектуры будет задача классификации .
Изображение предоставлено — Google
На изображении выше H представляет результат функции активации.
2. Один ко многим RNN : Архитектура «один ко многим» относится к ситуации, когда RNN генерирует серию выходных значений на основе одного входного значения. Ярким примером использования такой архитектуры будет задача создания музыки , где вводом является jounre или первая нота.
Изображение предоставлено — Google
3. Архитектура «Многие ко многим» (Tx не равно Ty): эта архитектура относится к тому, где многие входные данные считываются для получения множества выходных данных, где длина входов не равна длине выходных данных.Ярким примером использования такой архитектуры является машинного перевода задач.
Picture Credit — Google
Encoder относится к части сети, которая читает предложение для перевода, а Decoder — это часть сети, которая переводит предложение на желаемый язык.
Ограничения RNN
Помимо всей своей полезности, RNN имеет определенные ограничения, главными из которых являются:
Примеры архитектуры RNN, указанные выше, способны фиксировать зависимости только в одном направлении языка.В основном в случае обработки естественного языка предполагается, что слово, идущее после, не влияет на значение слова, идущего до него. Имея опыт общения с языками, мы знаем, что это, конечно, неправда.
RNN также не очень хороши в захвате долгосрочных зависимостей, и проблема исчезающих градиентов снова появляется в RNN.
Оба эти ограничения приводят к появлению новых типов архитектур RNN, которые обсуждаются ниже.
Стробируемый рекуррентный блок
Это модификация базового рекуррентного модуля, которая помогает улавливать дальнодействующие зависимости, а также очень помогает в решении проблемы исчезающего градиента.
Изображение предоставлено Google
GRU состоит из дополнительного блока памяти, обычно называемого вентилем обновления или вентилем сброса. Помимо обычного нейронного блока с сигмоидной функцией и softmax для вывода, он содержит дополнительный блок с tanh в качестве функции активации . Tanh используется, поскольку его выход может быть как положительным, так и отрицательным, следовательно, может использоваться как для увеличения, так и для уменьшения. Выходные данные этого устройства затем объединяются с входом активации для обновления значения ячейки памяти.
Таким образом, на каждом шаге обновляются значения как скрытого блока, так и блока памяти. Значение в блоке памяти играет роль в принятии решения о передаче значения активации следующему блоку.
Для более подробного объяснения можно обратиться к https://towardsdatascience.com/understanding-gru-networks-2ef37df6c9be
LSTM
В архитектуре LSTM вместо одного шлюза обновления, как в GRU, есть ворота обновления и ворота забыть.
Эта архитектура дает ячейке памяти возможность сохранить старое значение в момент времени t-1 и добавить к нему значение в момент времени t.
Более подробное объяснение LSTM доступно по адресу http://colah.github.io/posts/2015-08-Understanding-LSTMs/
Двунаправленный RNN
В приведенных выше архитектурах RNN эффекты появления только в предыдущие отметки времени могут быть приняты во внимание. В случае НЛП это означает, что он учитывает влияние слова, написанного только перед текущим словом. Но это не относится к языковой структуре, и поэтому на помощь приходит двунаправленная RNN.
Двунаправленная RNN состоит из прямой и обратной рекуррентной нейронной сети, и окончательное прогнозирование выполняется с объединением результатов обеих сетей в любой момент времени t, как можно увидеть на изображении.
.