Miško naujienos (2014)

Taškai: 12

Tolimojoje Bebrijoje laikraščio „Miško naujienos“ žinutės rašomos tik raidėmis A, B ir C. Trys korektoriai skaito žinutes iš kairės į dešinę ir ieško tam tikrų raidžių sekų.

  1. Jaunesnysis korektorius ieško sekų ABC. Radęs tokią seką pakeičia į BC ir tekstą skaito vėl nuo pradžių. Kai tokių sekų neberanda, tekstą persiunčia vyresniajam korektoriui.
  2. Vyresnysis korektorius ieško sekų BC. Radęs tokią seką pakeičia į B ir tekstą grąžina jaunesniajam korektoriui. Kai tokių sekų neberanda, tekstą persiunčia vyriausiajai korektorei.
  3. Vyriausioji korektorė ieško sekų BB. Radusi tokią seką, pakeičia į B ir tekstą grąžina jaunesniajam korektoriui. Kai tokių sekų neberanda, straipsnio koregavimas baigtas.

Duotos keturios žinutės:
A. AAABCB

B. ABCABC

C. ABABCB

D. ABCCCC

Atlikus korektūrą tris iš šių žinučių sudarys vienintelė raidė B, tačiau vieną – ne. Kuri žinutė negali sutrumpėti iki raidės B?

Paaiškinimas

Aprašytasis koregavimo procesas – tai Markovo algoritmas. Kaip ir Tiuringo mašina, Markovo algoritmai formalizuoja algoritmo aprašymo procesą. Viskam, kas gali būti suskaičiuojama kompiuteriu, galima taikyti kurį nors iš Markovo algoritmų ir atvirkščiai.

Atsakymas

Teisingas atsakymas – C.

AAABCB→AABCB→ABCB→BCB→BB→B

ABCABC→BCABC→BCBC→BBC→BB→B

ABABCBABBCBABBBABBAB

ABCCCC→BCCCC→BCCC→BCC→BC→B

 

 
Informacija atnaujinta 2015-10-16 15:36:59