Задания
Версия для печати и копирования в MS Word
Тип 12 № 40728
i

Ис­пол­ни­тель Ре­дак­тор по­лу­ча­ет на вход стро­ку цифр и пре­об­ра­зо­вы­ва­ет её. Ре­дак­тор может вы­пол­нять две ко­ман­ды, в обеих ко­ман­дах v и w обо­зна­ча­ют це­поч­ки цифр.

А)  за­ме­нить (v, w).

Эта ко­ман­да за­ме­ня­ет в стро­ке пер­вое слева вхож­де­ние це­поч­ки v на це­поч­ку w. На­при­мер, вы­пол­не­ние ко­ман­ды за­ме­нить (111, 27) пре­об­ра­зу­ет стро­ку 05111150 в стро­ку 0527150.

Если в стро­ке нет вхож­де­ний це­поч­ки v, то вы­пол­не­ние ко­ман­ды за­ме­нить (v, w) не ме­ня­ет эту стро­ку.

Б)  на­шлось (v).

Эта ко­ман­да про­ве­ря­ет, встре­ча­ет­ся ли це­поч­ка v в стро­ке ис­пол­ни­те­ля Ре­дак­тор. Если она встре­ча­ет­ся, то ко­ман­да воз­вра­ща­ет ло­ги­че­ское зна­че­ние «ис­ти­на», в про­тив­ном слу­чае воз­вра­ща­ет зна­че­ние «ложь». Стро­ка

ис­пол­ни­те­ля при этом не из­ме­ня­ет­ся.

 

Цикл

    ПОКА усло­вие

        по­сле­до­ва­тель­ность ко­манд

    КОНЕЦ ПОКА

вы­пол­ня­ет­ся, пока усло­вие ис­тин­но.

В кон­струк­ции

    ЕСЛИ усло­вие

        ТО ко­ман­да1

    КОНЕЦ ЕСЛИ

вы­пол­ня­ет­ся ко­ман­да1 (если усло­вие ис­тин­но).

В кон­струк­ции

    ЕСЛИ усло­вие

        ТО ко­ман­да1

        ИНАЧЕ ко­ман­да2

    КОНЕЦ ЕСЛИ

вы­пол­ня­ет­ся ко­ман­да1 (если усло­вие ис­тин­но) или ко­ман­да2 (если усло­вие ложно).

 

Дана про­грам­ма для ре­дак­то­ра:

НА­ЧА­ЛО

    ПОКА на­шлось (1111)

        за­ме­нить (1111, 22)

        за­ме­нить (222, 1)

    КОНЕЦ ПОКА

КОНЕЦ

 

Из­вест­но, что ис­ход­ная стро­ка со­дер­жа­ла боль­ше 200 еди­ниц и не со­дер­жа­ла дру­гих цифр. При какой наи­мень­шей длине ис­ход­ной стро­ки ре­зуль­тат ра­бо­ты дан­ной про­грам­мы будет со­дер­жать наи­боль­шее воз­мож­ное число еди­ниц?

Спрятать решение

Ре­ше­ние.

Пред­по­ло­жим, что ис­ход­ная стро­ка со­дер­жит 201 еди­ни­цу.

Дан­ный ал­го­ритм сна­ча­ла за­ме­нит во­семь пер­вых еди­ниц на че­ты­ре двой­ки, после чего пер­вые три двой­ки за­ме­нят­ся на одну еди­ни­цу. Затем ещё че­ты­ре еди­ни­цы, сле­ду­ю­щие после остав­шей­ся двой­ки, за­ме­нят­ся на две двой­ки, после чего три двой­ки за­ме­нят­ся на одну еди­ни­цу, и оста­нет­ся стро­ка из 191 еди­ни­цы. То есть каж­дую такую ите­ра­цию из стро­ки уби­ра­ют­ся 10 еди­ниц.

Далее ал­го­ритм 17 раз уберёт из стро­ки по 10 еди­ниц и оста­нет­ся стро­ка из один­на­дца­ти еди­ниц. После этого про­изойдёт за­ме­на вось­ми еди­ниц на че­ты­ре двой­ки, а затем пер­вые три двой­ки за­ме­нят­ся на одну еди­ни­цу, и оста­нет­ся стро­ка 12111. Всего 4 еди­ни­цы.

Если в ис­ход­ной стро­ке будет 202 еди­ни­цы, то после ра­бо­ты ал­го­рит­ма оста­нет­ся стро­ка 11. Если в ис­ход­ной стро­ке будет 203 еди­ни­цы, то после ра­бо­ты ал­го­рит­ма оста­нет­ся стро­ка 111. Если в ис­ход­ной стро­ке будет 204 еди­ни­цы, то после ра­бо­ты ал­го­рит­ма оста­нет­ся стро­ка 22. Если в ис­ход­ной стро­ке будет 205 еди­ниц, то после ра­бо­ты ал­го­рит­ма оста­нет­ся стро­ка 221. Если в ис­ход­ной стро­ке будет 206 еди­ниц, то после ра­бо­ты ал­го­рит­ма оста­нет­ся стро­ка 2211. Если про­дол­жать уве­ли­чи­вать ко­ли­че­ство еди­ниц в ис­ход­ной стро­ке, по­лу­чить ко­ли­че­ство еди­ниц боль­шее, чем 4, не по­лу­чит­ся. Зна­чит, ответ  — 201.

 

Ответ: 201.

 

При­ведём дру­гое ре­ше­ние на языке Python.

maxx = 0

for i in range(200, 1000):

s = '1' * i

while ('1111' in s):

s = s.replace('1111', '22', 1)

s = s.replace('222', '1', 1)

if maxx < s.count('1'):

maxx = s.count('1')

index = i

print(index)


Аналоги к заданию № 40728: 40987 Все

Спрятать решение · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026