Тип string в ТР. Тип string считается стандартным в ТР, т.е. его не надо описывать. Переменные этого типа задаются в программе, как обычно, в разделе описания. - презентация

1 Тип string в ТР. Тип string считается стандартным в ТР, т.е. его не надо описывать. Переменные этого типа задаются в программе, как обычно, в разделе описания переменных: var name: string [15]; fam: string; Значения типа string задаются последовательностью литер, заключенных в апострофы name:= 'Турбо Паскаль'; При объявлении переменной (в нашем случае name) в нее ничего не записывается. Длину значения переменной типа string можно не указывать при описании, тогда по умолчанию она считается равной 255. Следующая таблица поясняет, что происходит, когда переменной типа string присваиваются значения различной длины: длина значения = длине в описании происходит присваивание значения длина значения < длины в описании происходит присваивание значения длина значения > длины в описании значение обрезается до длины, указанной в описании и происходит присваивание

2 Примеры: name:= 'Турбо Паскаль 7; Турбо Паскаль name:= 'Турбо Паскаль' Турбо Паскаль name:='Язык программерования Турбо Паскаль' Язык программер

3 Операции над типом string Конкатенация (сцепление). Операция конкатенации означает сцепление одного значения типа string с другим значением. Обозначается знаком +. str := str + ' на языке ' + str1; Отношениеобоснование 'a' < 'b'ord('a') < ord('b') 'Bob' < 'bob'ord('B') < ord('b') 'cc'< 'ccc''ccc' длиннее чем 'cc' 'an'< 'an ''an ' длиннее чем 'an' 'фанера' > 'манера'ord (ф') > ord ('м') Присваивание := Пример: str2 := 'Строка'; str := 'Это пример'; str1 := 'Турбо Паскаль';

4 2.3. Функция concat Вид обращения: concat(p1, p2, p3,…,pn); Результат функции полностью аналогичен p1+p2+p3+…pn 2.4. Процедура delete Вид обращения: delete (,, ) 2.5. Процедура insert Вид обращения: insert (,, )

5 2.6. Функция copy sustring := copy (,, ); 2.7 Функция pos k := pos (, ) 2.8 Функция length size := length (str) получает один параметр - стринги и возвращает целочисленное значение, указывающее количество литер, содержащихся в данный момент в этом стрингие.

6 Пример. Пусть задан файл, содержащий текст на английском языке, в котором предложения оканчиваются точкой, а слова разделяются пробелом. Требуется подсчитать количество вхождений слова dollar в этот текст. Идея решения: читаем последовательно символы из файла (пока файл не закончится) и очередное прочитанное слово записываем в string (слово оканчивается пробелом или точкой). Сравниваем слово со строковой константой 'dollar'. Если равны, то поймали очередное вхождение и счетчик увеличиваем на 1. const wrd = 'dollar'; type file_char = file of char;

7 function num_wrd (var source_file : file_char) : integer; const empty = ' '; vars : sting [30]; k, j : integer; begin { Устанавливаем исходный файл на чтение, обнуляем счетчик вхождений } reset (source_file); j:=0; while not (eof(source_file)) do begin k:=1; { Считывается очередное слово из файла } while(source_file <> ' ')and(source_file <> '.') do begin s[k] := source_file ; get(source_file); k:=k+1 end; if s = wrd then j := j+1; get(source_file); s:=empty end; num_wrd := j end;

8 Рекурсивные функции и процедуры 1.1 Пример, особенности рекурсивных функций Рекурсия – это определение через себя. Классический пример рекурсивной функции - факториал n! (n 0): 1, если n=0 n! = n*(n-1)!, если n>0 Здесь n! определяется через (n-1)!, т.е. через себя, поэтому эта функция является рекурсивной. Описание функции факториал (дадим ей имя Ф) на Паскале выглядит так: type неотр=0..maxint; function Ф(n: неотр): неотр; begin if n=0 then Ф:=1 else Ф:=n*Ф(n-1) end;

9 Вычисление рекурсивной функции n:=3 Ф:=3*Ф(2)=... = 3*2=6 n:=2 Ф:=2*Ф(1)=... = 2*1=2 n:=1 Ф:=1*Ф(0)=... =1*1=1 n:=0 Ф:=1 Ф(3)=... =6 Ф(0) => Ф(1)=1*Ф(0)=1*1=1 => Ф(2)=2*Ф(1)=2*1=2 => Ф(3)=3*Ф(2)=3*2=6

10 Описание рекурсивной функции должно состоять из двух частей. Первая часть описания – это т.н. нерекурсивные ветви, где рассматриваются простейшие случаи, для которых ответ дается явно. Хотя бы одна нерекурсивная ветвь должна быть, иначе при вычислении функции мы зациклимся, не выйдем из рекурсии. Вторая часть описания – это рекурсивные ветви, где рассматривается общий случай. Это общий случай сводится к более простым случаям, для решения которых рекурсивно применяется сама функция, а затем из ответов этих повторных обращений строится ответ для общего случая. Рекурсия и циклы Любую рекурсивную функцию можно определить и нерекурсивно, через циклы (это строго доказано). Например, факториал можно определить так: function Ф(n: неотр): неотр; var p, i: неотр; begin p:=1; for i:=1 to n do p:=i*p; Ф:=p end;

11 Рекомендации по построению рекурсивных функций 1) Свести задачу к аналогичным подзадачам. задача для n подзадача для n –1 подзадача для n –2 ответ ответ γ => ответ для n 2) Рекурсивно применить функцию к подзадачам. 3) Из ответов подзадач построить ответ для задачи. 4) Задача не сводится к подзадачам явный ответ. 5) Считать, что функция правильно решает подзадачи.

12 Задача о ханойской башне Постановка задачи На столе имеются три колышка с номерами 1, 2 и 3. На 1-й колышек надето п дисков разного размера, причем диски меньшего размера лежат на дисках бόльшего размера (рис. а). Требуется перенести все диски с 1-го колышка на 3- й колышек (рис. г), соблюдая при этом следующие условия: 1)на каждом шаге можно переносить только один диск; 2) с каждого колышка можно снимать только верхний диск; 3) больший диск нельзя ставить на меньший б 231 а 321 г 321 в

13 При n=2 задача решается так: переносим меньший диск с 1-го колышка на 2-й, затем переносим больший диск с 1 го колышка на 3-й и в конце переносим меньший диск со 2-го колышка на 3-й: «Вылавливание» рекурсии Как видите, в постановке задачи сказано «используй рекурсию», но не сказано, откуда взять эту рекурсию. Вот и давайте «ловить» рекурсию согласно нашим рекомендациям. Прежде всего, мы должны свести задачу для n дисков к более простым аналогичным задачам. Как это сделать? Можно заметить, что на каком-то шаге решения нам придется переносить самый большой диск с 1-го колышка на 3-й. Поскольку по условиям задачи этот диск нельзя ставить ни на один другой диск, то в этот момент все остальные диски должны находиться на промежуточном 2-м колышке (рис. б). Таким образом, мы прежде всего должны перенести все диски, кроме самого большого, с 1-го колышка на 2-й колышек. Если мы сумеем это сделать, тогда мы переносим самый большой диск с 1-го колышка на 3-й колышек (рис. в), и теперь нам нужно перенести оставшиеся n-1 диск со 2-го колышка на 3-й. Таким образом, наша исходная задача сводится к следующим трем подзадачам:

14 1) перенести n-1 диск с 1-го колышка на 2-й 2) перенести больший диск с 1-го колышка на 3-й 3) перенести n-1 диск со 2-го колышка на 3-й Теперь отмечу, что решение второй из этих подзадач очевидно (просто переносим диск), а вот первая и третья подзадачи аналогичны исходной подзадаче, причем они более простые, чем исходная задача, т.к. в них надо переносить не n, а n-1 диск. Итак, мы «поймали» рекурсию. Две подзадачи несколько отличаются от исходной задачи, и не только числом переносимых дисков. Дело в том, что в исходной задаче надо переносить диски с 1-го колышка на 3-й, а в этих подзадачах надо переносить диски с 1-го на 2 й и со 2-го на 3-й, т.е. в них используются разные колышки. В обобщенном виде задача формулируется так: перенести m дисков с колышка k1 на колышек k3 через промежуточный колышек k2. Вот для решения такой обобщенной задачи мы и будем описывать нашу процедуру – обозначим ее Hanoi(m,k1,k2,k3) Для решения обеих наших подзадач мы должны просто рекурсивно обратиться к нашей процедуре: Hanoi(n,1,3,2) – для решения первой подзадачи и Hanoi(n,2,1,3) – для решения третьей подзадачи. И, наконец, вспомним рекомендацию относительно «вылавливания» нерекурсивных случаев: при каких значениях n исходную задачу не удается свести к более простым подзадачам? Очевидно, что это n=1. В данном случае надо просто перенести единственный диск с одного колышка на другой.

15 Опишем нашу процедуру на Паскале: procedure Hanoi(m, k1, k2, k3: integer); begin if m=1 then writeln(k1,, k3) else begin Hanoi(m-1,k1,k3,k2); writeln(k1,, k3); Hanoi(m-1,k2,k1,k3) end end;