Занятие Циклические операторы. Символьный тип icon

Занятие Циклические операторы. Символьный тип



НазваниеЗанятие Циклические операторы. Символьный тип
Дата конвертации24.05.2012
Размер156 Kb.
ТипДокументы

Занятие 3. Циклические операторы. Символьный тип.


Все программы, которые мы писали до сих пор, выполняли некоторое небольшое количество операций. По крайней мере, каждый оператор, который мы писали в тексте программы, выполнялся не более одного раза. Вместе с тем, широко известно, что компьютер используется для организации сложных объемных вычислений. Достаточно очевидно, что с помощью описанных нами алгоритмических средств будет затруднительно организовать продолжительные вычисления. Следовательно, возникает необходимость в некоторых конструкциях, которые позволяют выполнять некоторые последовательности операторов более одного раза. Обычно такие конструкции называют циклическими. Изучение циклических операторов и будет главной целью нашего занятия. Кроме этого мы обсудим тип данных Char, который используется для хранения символов. В конце занятия мы рассмотрим несколько примеров решения задач и покажем, что скорость работы программы существенно зависит от того, как она написана.


Начнем мы с циклических операторов. Язык Паскаль располагает как минимум тремя такими операторами:

1) While

2) Repeat .. Until

^ 3) For

Оператор While имеет следующую структуру:


While логическое выражение do

оператор;


Работает этот оператор очень просто. Вычисляется значение логического выражения. Если получается истина (True), то выполняется оператор, а затем снова вычисляется значение логического выражения. Если снова получается истина, то опять выполняется оператор, и т.д. Так продолжается до тех пор, пока при вычислении логического выражения не получится ложь (False). После этого оператор While заканчивает свою работу и передает действие следующему оператору.

В частности, если в самом начале работы While при вычислении логического выражения получается ложь, то оператор не выполнится ни разу. Как обычно, в качестве оператора может выступать некоторый составной оператор. Может показаться странным, что оператор While вообще когда-нибудь заканчивает свою работу. В самом деле, почему одно и то же логическое выражение сначала было истинным, а потом, после нескольких выполнений оператора, стало ложным? Ответ таков: логическое выражение зависит от нескольких переменных, значение которых меняется во время выполнения оператора, что влечет за собой изменения значения логического выражения. В принципе, это вовсе не означает, что каждый оператор While когда-нибудь заканчивает работу. То есть, не исключена ситуация, когда логическое выражение всегда будет истинным, и оператор While будет работать вечно. Такая ситуация называется зацикливанием.
Таким образом, при использовании оператора While и вообще других циклических операторов нужно быть аккуратным и стараться избегать зацикливаний. Это значит, что при программировании любого цикла нужно стараться всегда объяснить самому себе, почему этот цикл не будет вечным, а когда-нибудь закончит свою работу. Самым простым примером вечного цикла может быть следующий:


While True do




Проиллюстрируем работу оператора While на примере.

Пример. По числу X (1?X?2000000000) определить количество знаков в этом числе.

Решение этой задачи может иметь следующий вид:


program DigitCount;

var

X, Y: LongInt;


begin

ReadLn(X);

Y:= 0;

While X <> 0 do begin

X:= X div 10;

Y:= Y+1;

end;

WriteLn(Y);

end.


Цикл While в данной программе не является вечным. Это следует, к примеру, из того, что после каждого выполнения этого цикла число X уменьшается в 10 раз, что не может продолжаться вечно. Более того, программа работает правильно. Это следует из того, что число X div 10 имеет ровно на один знак меньше, чем число X (если считать, что число 0 состоит из нуля знаков).


Напомним еще раз, что оператор в теле цикла While может, в принципе, не выполниться ни разу. Иногда возникает необходимость в написании цикла, тело которого выполняется хотя бы один раз. Язык Паскаль располагает конструкцией Repeat..Until для организации подобных циклов. Оператор Repeat..Until имеет следующую структуру:


Repeat

оператор1;

оператор2



операторN

Until логическое выражение;


Работает этот оператор достаточно похоже на While. Существенных отличий два:

1) Группа операторов в теле цикла выполняется хотя бы один раз (в самом начале цикла).

2) Цикл заканчивает свою работу, когда при вычислении логического выражения получается истина (True).

Опишем работу цикла Repeat..Until более точно. Сначала выполняются все операторы в теле цикла. Далее вычисляется логическое выражение. Если оно ложно, то снова выполняются все операторы из цикла. Затем опять вычисляется логическое выражение и т.д. Цикл заканчивает свою работу, как только при вычислении логического выражения получается истина (True).


Циклы While и Repeat..Until достаточно похожи друг на друга и использование того или другого является, наверное, делом вкуса. Хотя, в принципе, встречаются ситуации, когда один из этих циклов использовать гораздо удобнее, чем другой. Однако, как правило, оба этих цикла используются тогда, когда неизвестно, сколько раз понадобится выполнять тело цикла (точнее, затруднительно вычислить, сколько раз нужно выполнять тело цикла). В случаях, когда число повторений тела цикла известно (или может быть вычислено), очень часто оказывается более удобным использовать цикл For. Этот цикл имеет несколько более сложную структуру.


For переменная:= начальное значение to конечное значение do

оператор;


Под переменной в этой записи подразумевает произвольная переменная перечислимого типа. ^ Начальное и конечное значения – произвольные выражения, тип которых совпадает с типом переменной.

Прежде чем объяснять работу этого оператора, вспомним, что на предыдущем занятии перечислимые типы определялись как типы, принимающие конечное число различных значений. Такое определение, в принципе, является правильным, но совсем удобным. Мы будем далее предполагать, что перечислимые типы – типы, которые принимают конечное число значений, и на которых введен порядок, то есть все значения данного типа выписаны в некотором порядке. Это означает, что каждому значению данного типа можно поставить в соответствие некоторое натуральное число – его номер среди всех выписанных значений. В свою очередь это позволяет сравнивать значения перечислимых типов (вместо этого нужно сравнивать их номера), находить следующее и предыдущее значения (нужно соответственно увеличить/уменьшить номер). На предыдущем занятии мы неявно предполагали введение порядка, говоря, что каждое значение каждого перечислимого типа на самом деле хранится в памяти как целое число.

Для целочисленных переменных порядок вводится просто выписыванием значений по возрастанию. Переменные логического типа упорядочиваются так: False, True.


Объясним теперь работу цикла For. Сначала вычисляется начальное значение (обозначим результат вычислений A), а затем – конечное значение (обозначим его B). Если оказывается, что A > B, то тело цикла не выполняется ни разу, и управление передается следующему после For оператору. Иначе выполняются следующие действия: в переменную помещается значение A, выполняется оператор, в переменную помещается следующее после A значение, выполняется оператор, …, в переменную помещается предыдущее перед B значение, выполняется оператор, в переменную помещается значение B, выполняется оператор. Таким образом, оператор выполняется B-A+1 раз, при этом каждый раз с разными значениями переменной.

Заметьте, что начальное и конечное значение вычисляются ровно один раз в начале цикла. Например, рассмотрим следующий фрагмент программы:


n:= 1;

For i:= 1 to n do

n:= n+1;


Цикл For здесь вовсе не является вечным, как может показаться на первый взгляд. На самом деле он выполняется только для i = 1.

Строго говоря, все сказанное выше о работе цикла For верно только в том случае, когда переменная не меняется внутри тела цикла. Для того, чтобы рассмотреть, что произойдет в этом случае, цикл For можно переписать в следующем эквивалентном виде:


переменная:= начальное значение;

While переменная ? конечное значение do begin

оператор;

Inc(переменная)

end;


Здесь используется незнакомая вам операция ^ Inc(перечислимый тип), которая возвращает следующее значение для аргумента и имеет такой же тип, как и аргумент. Аналогичная операция Dec(перечислимый тип) возвращает предыдущее значение для аргумента и имеет такой же тип, как и аргумент.

После описания цикла For в таком все вопросы снимаются. Можно рассмотреть, к примеру, следующий фрагмент программы:


For i:= 1 to 10 do begin

WriteLn(i);

i:= i+1;

end;


Нетрудно видеть, что данная программа выведет на экран числа 1, 3, 5, 7, 9.


Иногда бывает полезным перебирать переменную не в порядке увеличения ее значений, а в порядке уменьшения. Для этого можно использовать следующую структуру:


For переменная:= начальное значение downto конечное значение do

оператор;


Чтобы долго не описывать, как работает оператор For в данной записи, перепишем ее в эквивалентном виде:


переменная:= начальное значение;

While переменная ? конечное значение do begin

оператор;

Dec(переменная)

end;


В заключение рассмотрим пример использования цикла For.

Пример. Для заданного N (1?N?1000) вычислить сумму квадратов всех чисел от 1 до N.

Решение может выглядеть следующим образом:


Program SumSqr;

var

N, S, i: LongInt;

begin

ReadLn(N);

S:= 0;

For i:= 1 to S do

S:= S+Sqr(i);

WriteLn(S);

end.


Иногда бывает полезным либо «насильно» завершить работу некоторого цикла, либо «насильно» перейти к следующей его итерации, не заканчивая текущую. Для этого служат операторы языка Паскаль break и continue. Операторы эти могут быть написаны только в теле циклов While, Repeat..Until и For. Если в теле некоторого цикла есть оператор Break и до него доходит выполнение, то этот цикл сразу автоматически заканчивает свою работу и управление передается следующему после цикла оператору. Если в теле некоторого цикла есть оператор Continue и до него доходит выполнение, то текущая итерация этого цикла автоматически заканчивается и сразу начинается следующая итерация цикла (под итерацией мы понимаем одноразовое выполнение тела цикла). Как мы увидим дальше, данные операторы иногда бывают очень удобными.

Отметим также еще два полезных оператора – Exit и Halt. Дальше мы скорректируем работу этих операторов, но пока Вы можете считать, что они делают одно и то же – просто заканчивают работу программы, что тоже очень часто бывает полезным. Эти операторы могут быть написаны в произвольном месте программы.


Опишем теперь новый тип данных – символьный. Для описания переменной A символьного типа достаточно написать:


var

A: Char;


Логично, что в переменных символьного типа хранятся символы. Чтобы поместить в переменную символьного типа конкретный символ, можно воспользоваться оператором присваивания. При этом этот символ должен быть заключен в одинарные кавычки. Например, допустима запись A:= ‘a’. Конечно, переменные символьного типа можно вводить и выводить с помощью операторов ввода-вывода.

Переменные типа Char занимают один байт памяти. Это связано с тем, что стандартный набор символов ASCII состоит из 256 символов. Каждый символ имеет свой собственный код – число от 0 до 255. Операция Ord(символьный тип) возвращает код символа и имеет целочисленный тип результата. Например, Ord(‘a’) = 48. Операция Chr(целочисленный тип) возвращает символ по коду и имеет символьный тип результата. Например, Chr(48) = ‘a’. То же самое делает операция #. Следующие три записи ‘a’, Chr(48), #48 эквивалентны.

Тип Char является перечислимым. Порядок на этом типе устанавливается перечислением символов в порядке возрастания их кодов. Следовательно, когда мы пишем A < B для символьных типов, это эквивалентно записи Ord(A) < Ord(B).

Полезно знать, что набор ASCII включает в себя некоторые специальные символы. В частности, символ #10 является символов перевода строки, а символ #13 – символом конца строка.

Заметим, что операция Ord является на самом деле более общей. Она принимает значения любого перечислимого типа и возвращает его номер. Например, Ord(False) = 0, Ord(True) = 1.

Рассмотрим пример работы с переменными символьными типа.

Пример. Ввести с экрана символ X, который является большой или маленькой латинской буквой или цифрой. Вывести сообщение о том, какого типа символ был введен.


program WhatChar;

var

X: Char;


Begin

ReadLn(X);

Case X of

‘A’..’Z’: WriteLn(‘Большая буква’);

‘a’..’z’: WriteLn(‘Маленькая буква’);

‘0’..’9’: WriteLn(‘Цифра’);

end;

end.


В данном решении существенно используется тот факт, что символы от ‘A’ до ‘Z’ нумеруются последовательными числами в порядке возрастания. То же самое обстоит с символами от ‘a’ до ‘z’ и от ‘0’ до ‘9’.

Полезно иметь в виду, что с русскими буквами все обстоит не совсем так.

Упражнение. Протестировать, как связаны между собой коды символов от ‘а’ до ‘я’ и от ‘А’ до ‘Я’.

Отметим еще одну полезную операцию UpCase(символьный тип), которая преобразует маленькие латинские символы в соответствующие большие, а остальные символы оставляет без изменения.


Теперь мы рассмотрим применение циклических операторов на примере достаточно сложной задачи. Разбирая ее решение, мы увидим, что в общем случае недостаточно просто написать программу, правильно решающую поставленную задачу, а очень часто нужно написать ее так, чтобы она работала быстро.


^ Важный пример.

Заданы 2 натуральных числа N1 и N2. Необходимо вычислить сумму цифр всех чисел от N1 до N2 (N1, N2 – натуральные числа ? 2000000000, N1?N2).

Числа N1 и N2 вводятся с клавиатуры (в одной строке через пробел). Результат, в виде натурального числа, выводится в следующей строке экрана.

Пример.
21 24  {1-я строка ввода: < N1> < N2>}

18       {1-я строка вывода: <Сумма цифр всех чисел от N1 до N2>}

            (Сумма цифр чисел от 21 до 24: 2+1+2+2+2+3+2+4 = 18)

Замечание. Данная задача предлагалась на региональных олимпиадах, проводившихся в 4 регионах Минской области, в 2003 году.


Сначала мы напишем программу, которая просто решает поставленную задачу (не обязательно быстро). Для начала мы научимся находить сумму цифр произвольного числа X. Для этого можно использовать два факта: выражение X mod 10 дает последнюю цифру числа X (если X > 0) и присваивание X:= X div 10 отбрасывает последнюю цифру числа X. Поэтому следующий фрагмент считает сумму цифр числа X и помещает ее в переменную S:


S:= 0;

While X <> 0 do begin

S:= S+(X mod 10);

X:= X div 10;

end;


Теперь все, что нам нужно – перебрать все числа от N1 до N2 и для каждого из них посчитать сумму цифр. Для этого можно использовать цикл For. Единственная тонкость заключается в том, что результат может получиться достаточно большим и для его хранения нужно использовать переменную типа Comp. Итак, мы получили совсем несложную программу для решения этой задачи:


program FindSumDigits;

var

N1, N2: LongInt;

i, X, S: LongInt;

Result: Comp;


begin

ReadLn(N1, N2);

Result:= 0;

For i:= N1 to N2 do begin

X:= i; S:= 0;

While X <> 0 do begin

S:= S+(X mod 10);

X:= X div 10;

end;

Result:= Result+S;

end;

WriteLn(Result:0:0);

end.


Теперь мы протестируем нашу программу (на компьютере с процессором с тактовой частотой 633 MHz) на тестах, предлагавшихся на олимпиаде.

Результаты тестирования приведены в таблице ниже:


N1

N2

Ответ нашей программы

Правильный ответ

Время работы нашей программы

25

49

205

205

0,000

56857

56857

31

31

0,000

1

100000

2250001

225001

0,220

1234567890

1234567891

91

91

0,000

25850

50123456

1677843161

1677843161

150,810

1

1987654321

???

81368770051

долго

1000000000

2000000000

???

41500000002

долго


Как видно, наша программа проходит 4 теста из 7. Остальные тесты не проходят по времени, хотя если бы времени было много, то программа выдала бы правильный ответ и на них. Таким образом, наша программа работает правильно, но долго. Естественно, те 3 теста, которые у нас не проходят, были самыми дорогими. Так что наша программа заработала бы на олимпиаде только около одной трети от максимального балла за задачу.


Причина медлительности нашей программы заключается в том, что в худшем случае ей придется считать сумму цифр целых двух миллиардов чисел. Сейчас мы разберем решение, в котором в худшем случае нужно будет посчитать сумму цифр только нескольких сотен тысяч чисел, что, конечно, гораздо меньше. Прежде всего, заметим, что нам достаточно уметь считать сумму цифр всех чисел от 1 до произвольного натурального числа X – мы уже использовали один раз такой прием (см. задача «Сумма чисел», домашнее задание, занятие №1). В самом деле, если мы умеем это делать, то для того чтобы найти ответ задачи, достаточно вычесть из суммы цифр всех чисел от 1 до N2 сумму цифр всех чисел от 1 до N1-1.

Пусть C = X div 100000. Разобьем числа от 1 до X на C+1 группу A0, A1, …, AC. В группу A0 включим числа 1, 2, …, 99999. В группу A1 включим числа 100000, 100001, …, 199999. Более точно, в группу Ai (0?iC включим все оставшиеся числа. Заметим теперь, что для всех групп Ai (0?i
1) Если у каждого числа из Ai вычеркнуть последние пять цифр, то останется 100000 чисел, равных i.

2) Если у каждого числа из Ai оставить только последние пять цифр, то независимо от i получится в точности группа чисел A0.

Теперь, если обозначить через S(X) – сумму цифр числа X, а через S(Ai) – сумму цифр чисел из группы Ai, то, как нетрудно видеть:

1) Для любого i, 0?ii) = 100000S(i)+S(A0).

2) Сумма цифр всех чисел от 1 до X равна S(A0)+…+S(AC) = 100000(S(0)+S(1)+…+S(C-1))+CS(A0)+S(AC) (1)

Посмотрим, сколько раз нужно вычислять сумму цифр чисел, если пользоваться формулой (1). Нетрудно видеть, что для вычисления S(A0) и S(AC) необходимо не более чем 200000 раз считать сумму цифр чисел. С учетом того, что C?20000, получаем, что всего для вычислений по формуле (1) необходимо считать сумму цифр чисел не более чем 220000 раз. Для решения задачи нам нужно будет дважды применять формулу (1) – при подсчете суммы цифр всех чисел от 1 до N1-1 и от 1 до N2. Поэтому всего для решения понадобится посчитать сумму цифр не более 440000 чисел. Если учесть, что вовсе не обязательно считать два раза сумму S(A0), данная оценка может быть уменьшена до 340000.

Осталось только аккуратно запрограммировать решение.


Program FindSumDigit;

var

N1, N2: LongInt;

i, T: LongInt;

X, C: LongInt;

SN1, SN2, SA0: Comp;


begin

{Input N1, N2}

ReadLn(N1, N2);


{Calculate S(A0)}

SA0:= 0;

For i:= 1 to 99999 do begin

T:= i;

While T <> 0 do begin

SA0:= SA0+(T mod 10);

T:= T div 10;

end;

end;


{Use formulae (1) for X = N2}

X:= N2;

C:= X div 100000;

SN2:= 0;

For i:= 0 to C-1 do begin

T:= i;

While T <> 0 do begin

SN2:= SN2+(T mod 10);

T:= T div 10;

end;

end;

SN2:= 100000*SN2+C*SA0;

For i:= X-(X mod 100000) to X do begin

T:= i;

While T <> 0 do begin

SN2:= SN2+(T mod 10);

T:= T div 10;

end;

end;


{Use formulae (1) for X = N1-1}

X:= N1-1;

C:= X div 100000;

SN1:= 0;

For i:= 0 to C-1 do begin

T:= i;

While T <> 0 do begin

SN1:= SN1+(T mod 10);

T:= T div 10;

end;

end;

SN1:= 100000*SN1+C*SA0;

For i:= X-(X mod 100000) to X do begin

T:= i;

While T <> 0 do begin

SN1:= SN1+(T mod 10);

T:= T div 10;

end;

end;


{Write result}

WriteLn((SN2-SN1):0:0);

end.


Программа получилась довольно большой, но, как мне кажется, достаточно понятной по своей структуре. К сожалению, в ней есть много похожих друг на друга частей. На 5-м занятии мы обсудим, как записывать такие программы в более сжатом виде. Результаты тестирования программы приведены в таблице ниже:


N1

N2

Ответ нашей программы

Правильный ответ

Время работы нашей программы

25

49

205

205

0,220

56857

56857

31

31

0,495

1

100000

2250001

225001

0,220

1234567890

1234567891

91

91

0,825

25850

50123456

1677843161

1677843161

0,385

1

1987654321

81368770051

81368770051

0,440

1000000000

2000000000

41500000002

41500000002

0,605


Как видите, программа стала работать гораздо быстрее. Теперь мы бы уже набрали полный балл на олимпиаде, сдав такое решение. Хотя, как нетрудно заметить на некоторых тестах программа стала работать дольше. Довольно очевидно, что это связано с тем, что мы, независимо от входных данных всегда считаем S(A0) для дальнейшего использования, что само по себе занимает некоторое время.




Похожие:

Занятие Циклические операторы. Символьный тип iconЗанятие Условные операторы. Переменные с плавающей точкой и операции над ними. Логический тип. Интервальный тип

Занятие Циклические операторы. Символьный тип iconЗанятие Структура программы. Переменные. Операторы ввода-вывода. Оператор присваивания. Целочисленные переменные и операции над ними

Занятие Циклические операторы. Символьный тип iconКонспект урока по информатике учителя Оганьян Э. А. Тема урока : Основные операторы языка Бейсик Тип урока: урок обобщение План урока
Каждый из них должен написать, что появится на экране при выполнении данных задач
Занятие Циклические операторы. Символьный тип iconТема урока Мутационная изменчивость
Тип урока: Урок усвоения новых знаний (лекционное занятие – школьная лекция – с элементами индивидуальной работы учащихся)
Занятие Циклические операторы. Символьный тип iconУрок в 6 классе Тип урока: учебное занятие по закреплению знаний и способов деятельности Форма: практикум. Цели: Образовательные
Я рада приветствовать вас, ребята. Возьмитесь за руки и скажите «Добрый день и назовите имя соседа»
Занятие Циклические операторы. Символьный тип iconЗанятие разработано для факультатива по математике
Разрабатываемое учебное занятие соответствует всему курсу геометрии, т к в 7 классе способ доказательства теоремы вводится и на протяжении...
Занятие Циклические операторы. Символьный тип iconПрезентация к уроку литературы в 9 классе Автор и читатель Примерный план анализа История создания стихотворения. Жанр. Размер, тип рифмы. Тип названия

Занятие Циклические операторы. Символьный тип iconСнято занятие Назначено занятие

Занятие Циклические операторы. Символьный тип iconСнято занятие Назначено занятие

Занятие Циклические операторы. Символьный тип iconУрок биологии в 7 классе по теме «Круглые черви» Тип урока: комбинированный. Цель: Изучить Тип Круглые черви. Задачи: 1 Образовательные
Реализация содержательной линии образования «Культура здоровья и охраны жизнедеятельности»
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов