К. Поляков, 2010 -2012 Программирование на алгоритмическом языке. Часть II Тема 4. Символьные строки. - презентация

1 К. Поляков, Программирование на алгоритмическом языке. Часть II Тема 4. Символьные строки

2 Программирование на алгоритмическом языке. Часть II К. Поляков, Задачи на обработку строк 2 Задача: с клавиатуры вводится число N, обозначающее количество футболистов команды «Шайба», а затем – N строк, в каждой из которых – информация об одном футболисте таком формате: Все данные разделяются одним пробелом. Нужно подсчитать, сколько футболистов, родившихся в период с 1988 по1990 год, не забили мячей вообще. Алгоритм (для каждой строки): 1)выделить год ( year ) и количество голов ( goal ) 2)если 1988

3 Программирование на алгоритмическом языке. Часть II К. Поляков, Программа 3 использовать Строки алг Футболисты нач цел N, i, p, year, goal, count=0 лит s ввод N нц для i от 1 до N ввод s | разобрать строку, выделить год и голы если year >= 1988 и year = 1988 и year

4 Программирование на алгоритмическом языке. Часть II К. Поляков, Разбор строки 4 Пропуск фамилии: p:= найти(" ", s) s:= s[p+1:длин(s)] p:= найти(" ", s) s:= s[p+1:длин(s)] Пропуск имени: Ввод года рождения: p:= найти(" ", s) year:= лит_в_цел(s[1:p-1],OK) s:= s[p+1:длин(s)] p:= найти(" ", s) year:= лит_в_цел(s[1:p-1],OK) s:= s[p+1:длин(s)] Ввод числа голов: Иванов Вася p Вася p:= найти(" ", s) s:= s[p+1:длин(s)] p:= найти(" ", s) s:= s[p+1:длин(s)] Вася p p 5 goal:= лит_в_цел(s,OK) лог OK

5 Программирование на алгоритмическом языке. Часть II К. Поляков, Разбор строки 5 Если фамилия нужна: p:= найти(" ", s) fam:= s[1:p-1] s:= s[p+1:длин(s)] p:= найти(" ", s) fam:= s[1:p-1] s:= s[p+1:длин(s)] лит fam Иванов Вася p Иванов Вася Если нужны ВСЕ фамилии: p:= найти(" ", s) fam[i]:= s[1:p-1] s:= s[p+1:длин(s)] p:= найти(" ", s) fam[i]:= s[1:p-1] s:= s[p+1:длин(s)] литтаб fam[1:N]

6 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания 6 «3»: Вывести фамилии всех футболистов, которые забили больше двух голов. Пример: Иванов Василий Семёнов Кузьма «4»: Вывести фамилию и имя футболиста, забившего наибольшее число голов, и количество забитых им голов. Пример: Иванов Василий 25 Информация о футболистах вводится так же, как и для приведенной задачи (сначала N, потом N строк с данными).

7 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания 7 «5»: Вывести в алфавитном порядке фамилии и имена всех футболистов, которые забили хотя бы один гол. В списке не более 100 футболистов. Пример: Васильев Иван Иванов Василий Кутузов Михаил Пупкин Василий

8 Программирование на алгоритмическом языке. Часть II К. Поляков, Рекурсивный перебор 8 Задача: Алфавит языка племени «тумба-юмба» состоит из букв Ы, Ц, Щ и О. Вывести на экран все слова из К букв, которые можно составить в этом языке, и подсчитать их количество. Число K вводится с клавиатуры. 1K в каждой ячейке может быть любая из 4-х букв 4 варианта Количество вариантов:

9 Программирование на алгоритмическом языке. Часть II К. Поляков, Рекурсивный перебор 9 Ы 1K Рекурсия: Решения задачи для слов из К букв сводится к 4-м задачам для слов из K-1 букв. Щ 1K О 1K Ц 1K перебрать все варианты

10 Программирование на алгоритмическом языке. Часть II К. Поляков, Процедура 10 алг Рек(цел p) нач если p > K то вывод s, нс count:= count + 1 выход все кон алг Рек(цел p) нач если p > K то вывод s, нс count:= count + 1 выход все кон ???? 1K p s p+1 рекурсивные вызовы А если букв много? ? Глобальные переменные: лит s цел count, K если p > K то вывод s, нс count:= count + 1 выход все если p > K то вывод s, нс count:= count + 1 выход все s[p]:= "Ы"; Рек(p+1) s[p]:= "Ц"; Рек(p+1) s[p]:= "Щ"; Рек(p+1) s[p]:= "О"; Рек(p+1) s[p]:= "Ы"; Рек(p+1) s[p]:= "Ц"; Рек(p+1) s[p]:= "Щ"; Рек(p+1) s[p]:= "О"; Рек(p+1) окончание рекурсии

11 Программирование на алгоритмическом языке. Часть II К. Поляков, Основная программа 11 лит s, цел count = 0, K алг Рекурсивный перебор нач вывод "Введите длину слов: " ввод K s:= "" нц K раз s:= s + " " кц Рек(1) вывод "Всего ", count, " слов" кон лит s, цел count = 0, K алг Рекурсивный перебор нач вывод "Введите длину слов: " ввод K s:= "" нц K раз s:= s + " " кц Рек(1) вывод "Всего ", count, " слов" кон s:= "" нц K раз s:= s + " " кц строка из K пробелов глобальные переменные алг Рек(цел p) нач... кон алг Рек(цел p) нач... кон

12 Программирование на алгоритмическом языке. Часть II К. Поляков, Процедура (много букв) 12 алг Рек(цел p) нач если p > K то вывод s, нс count:= count + 1 выход все кон алг Рек(цел p) нач если p > K то вывод s, нс count:= count + 1 выход все кон лит syms="ЫЦЩО", цел i нц для i от 1 до длин(syms) s[p]:= syms[i]; Рек(p+1) кц нц для i от 1 до длин(syms) s[p]:= syms[i]; Рек(p+1) кц локальные переменные все буквы цикл по всем буквам

13 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания 13 Алфавит языка племени «тумба-юмба» состоит из букв Ы, Ц, Щ и О. Число K вводится с клавиатуры. «3»: Вывести на экран все слова из К букв, в которых первая буква – Ы, и подсчитать их количество. «4»: Вывести на экран все слова из К букв, в которых буква Ы встречается более 1 раза, и подсчитать их количество. «5»: Вывести на экран все слова из К букв, в которых есть одинаковые буквы, стоящие рядом (например, ЫЩЩО), и подсчитать их количество.