Tatu samarqand filiali

Пример  1.  В  произвольном  слове,  состоящем  из  букв 

{a, b, c}

,  все  подряд  стоящие 

одинаковые  буквы  заменить  одной  буквой  (например,  слово  «abbbcaa»  преобразовать  в 

«abca»). Схема НАМ. имеет вид:  

1. 

aa

 

→ 

 

a

 

2. 

bb

  

→ 

 

b

 

---

3. 

cc

  

→ 

 

c

 

(

загрузить в эмулятор

)  

Применение этой схемы с слову «abbbcaa» последовательно даст слова: «abbbca», «abbca» 

и  «abca»,  после  чего  выполнение  НАМ  завершится.  Для  проверки  данного  алгоритма 

загрузите его текст в эмулятор.  

Пример  2.  Удвоить  слово,  состоящее  из  одинаковых  символов  (для  определенности — 

«x»). Т.е. слово «x» надо преобразовать в «xx», слово «xx» — в «xxxx» и т.д.  

Схема НАМ для этого примера намного сложнее, чем для примера 1. Нельзя написать 

x 

→ xx

, т.к. в этом случае на каждом шаге НАМ к слову будет  добавляться символ  «x»  и 

этот процесс будет бесконечным. Необходимо контролировать удвоение каждого символа 

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

помощью которого будем обеспечивать контекст применения удваивающего правила.  

1. 

*x

 

→ 

 

xx*

 

2. 

*

  

↦ 

  

3.   

→ 

 

*

 

(

загрузить в эмулятор

)  

Последнее  правило  вводит  «маркер»  '*'  (или  «курсор»),  который  с  помощью  первого 

правила «перескакивает» через текущий символ слова и удваивает его. Применение этой 

схемы,  например,  к  слову  «xx»  последовательно  даст  слова:  (3)  «*xx»,  (1)  «xx*x»,  (1) 

«xxxx*», (2) «xxxx» (в скобках указан номер применяемой формулы подстановки).  

Пример  3.  Дано  слово  в  алфавите 

{a, b, c}

.  Упорядочить  буквы  входного  слова  в 

лексикографическом порядке  

---

FOYDALANILGAN ADABIYOTLAR 

 1. Алфред  В.  Ахо.,  Джон  Э.  Хопкрофт,  Джефри  Д.  Ульман. Структура 

данных и алгоритмы//Учеб.пос., М. : Изд.дом: "Вильямс", 2000. 

2. Бакнелл  Джулиан  М.  Фундаментальные  алгоритмы  и  структуры  

данных в Delphi//СПб: ООО «ДиаСофтЮП», 2003. 560с.  

3.  Роберт    Седжвик.    Фундаментальные    алгоритмы    на    C++.    Анализ, 

Структуры данных, Сортировка, Поиск//К.: Изд. «ДиаСофт», 2001.- 688 с.  

4. Динман М.И. С++. Освой на примерах//СПБ.:БХВ-Петербург, 2006, 384.   

5. Шилдт,  Герберт.  Полный  справочник  по  С#//М.  :  Изд.  дом "Вильямc", 

2004, 752 с.  

6. Вирт Н. Алгоритмы и структуры  программы//М., Мир, 1985.  

7.  Лойко    В.И.    Структуры    и    алгоритмы    обработки    данных.    Учебное  

пособие для вузов.- Краснодар: КубГАУ. 2000. - 261 с., ил.  

8.  Knuth,    D.    E.    (1968).    The    Art    of    Computer    Programming    Vol.    I: 

Fundamental  Algorithms,  Addison  –  Wesley,  Reading,  Mass. (Русский  перевод: 

Кнут    Д.    Искусство    программирования    для    ЭВМ.    Том    1:    Основные  

алгоритмы.    –    М.,    «Мир»,    1976.    Русский    перевод    переработанного   

издания:  Кнут    Д.    Искусство    программирования.    Том    1:    Основные  

алгоритмы.  –  М., Издательский дом «Вильямс», 2000.)  

9. Джон  Бентли.  Жемчужины  программирования.  СПб.:  Питер, 2002.-272с.  

10. Акбаралиев  Б.Б.  Конспект  лекций  по  курсу  “Маълумотлар тузилмаси  

ва  алгоритмлар”  для  студентов  по  специальности  5521900 “Информатика 

и информационные технологии”, Ташкент, 2008 г.  

11.  Акбаралиев  Б.Б.  Методические  указания  к  лабораторным  работам    по 

курсу  “Маълумотлар  тузилмаси  ва  алгоритмлар”  для  студентов  по 

специальности  5521900  “Информатика  и  информационные  технологии”, 

Ташкент, 2008 г.  

12.  Xudoyberdiyev    M.X.,    Akbaraliyev    B.B.  “Ma’lumotlat    tuzilmasi    va 

algoritmlar”    fanidan    amaliy    mashg’ulotlar    uchun    topshiriqlar    (uslubiy 

ko’rsatmalari bilan). Toshklent, 2013 y.