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.