Решение задач типа В10 ГИА по информатике

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

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

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

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

 По­яс­не­ние.

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

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

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

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

 По­яс­не­ние.

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

 

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

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

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.