Make your own free website on Tripod.com

יסודות מדעי המחשב. יסודות- 1. מחבר ד"ר דוד גינת.

צוות הפיתוח: פרופ' מרדכי בן-ארי, דר' דוד גינת, ארנה הרשקוביץ ,

דר' ארנה ליכטנשטיין, חנה מחלב, אלה צור, יפעת קוליקנט, נורית רייך

מהדורה ניסויית, 1998

Основания компьютерных наук. Основания-1

Разработчики: проф. Мордехай Бен-Ари, д-р Давид Гинат, Орна Гершкович,

д-р Орна Лихтенштейн, Хана Махлев, Эла Цур, Ифат Куликант, Нурит Райх

Пробное издание, 1998

 

Продолжение главы 7

?Вопрос 7.22. Разработай и реализуй алгоритм, на вводе которого целое положительное число, а на выводе - наименьшая степень 2-х, которая больше числа, заданного на вводе. Например, для ввода 7 на выводе будет 8(23 = 8), а для ввода 8 на выводе будет 16(24 = 16). В ходе разработки алгоритма сформулируй подзадание тела цикла и условие его исполнения. Обрати внимание на то, что в алгоритме надо использовать накопитель для умножения.

В цикл while, который мы рассматривали до сих пор, включалось условие вхождения в цикл - сравнение между переменной, значение которой возрастало в ходе повторных исполнений цикла, и значением границы, которая хранилась в

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

следующую задачу, мы увидим другой пример.

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

Задача 4. Разработай и реализуй алгоритм, на вводе которого положительное целое число, а на выводе число цифр в нем. Например, для ввода 31 вывод будет 2, а для ввода 15568 вывод будет 5.

?! На секунду задумаемся ... В предыдущих главах мы познакомились с разложением целого числа на цифры при известном числе цифр в нем. В данной задаче число цифр не известно. Какими будут подзадания тела цикла для подсчета количества цифр у числа? И каким будет условие возвращения к исполнению этих подзаданий?

Мы можем обрезать цифры числа одно задругим и подсчитывать их число. Делать это будут подзадания тела цикла, обрезающих по одной цифре от числа и наращивающих счетчик на 1. Обрезание цифры будет осуществляться делением(целым) числа на 10. Такое деление приведет к обрезанию самой правой цифры числа. Сформулируем эти подзадания в теле цикла:

Обрезание самой правой цифры числа

Добавление 1 к счетчику цифр

Надо выполнять эти подзадания, пока есть, что обрезать, т.е. пока число(то, что от него остается в ходе программы) больше 0. Поэтому условие повторного исполнения будет таким: число(то, что осталось от него) больше 0 .

Эти подзадания и условие реализуют идею решения задачи. Приступим теперь к назначению переменных и написанию алгоритма:

Num - будет хранить заданное число и его цифры после обрезаний.

Digits - счетчик, содержащий число обрезанных цифр

Алгоритм решения нашей задачи будет таким:

Введи целое положительное число в Num

Обнули переменную Digits

До тех пор, пока значение Num больше нуля выполняй

Обрежь правую цифру в Num посредством ее деления на 10

Увеличь на 1 значение Digits

Выведи значение Digits

Программа, решающая задачу, будет такой:

program DigitCount; {Ввод: целое положительное число}

{Вывод: число цифр в заданном числе}

var

Num: integer; {заданное число и его цифры после обрезаний}

Digits: integer; {счетчик числа цифр заданного числа}

begin

writeln('Введи целое положительное число: ');

readln(Num);

Digits := 0;

while Num > 0 do

begin

Num := Num div 10;

Digits := Digits + 1

end;

writeln('Число цифр у введенного числа: ',Digits);

end.

Проверим программу с помощью таблицы слежения за ее ходом для ввода 153:

Следующий исполнимый оператор

Num

Digits

Num > 0

Вывод

...........

?

?

 

 

readln(Num);

 

 

 

 

 

153

 

 

Digits := 0;

 

 

 

 

 

0

 

 

while Num > 0 do

 

 

 

 

 

true

 

Num := Num div 10;

 

 

 

 

 

15

 

 

Digits := Digits + 1;

 

 

 

 

 

1

 

 

while Num > 0 do

 

 

 

 

 

true

 

Num := Num div 10;

 

 

 

 

 

1

 

 

Digits := Digits + 1;

 

 

 

 

 

2

 

 

while Num > 0 do

 

 

 

 

 

true

 

Num := Num div 10;

 

 

 

 

 

0

 

 

Digits := Digits + 1;

 

 

 

 

 

3

 

 

while Num > 0 do

 

 

 

 

 

 

false

 

writeln('Число.....: ',Digits);

 

 

 

 

 

 

... 3

Конец решения задачи 4

?Вопрос 7.23. Измени программу DigitCount из задачи 4 так, чтобы вывод содержал число нечетных цифр в заданном числе. Например, для ввода 150 вывод будет 2.

?Вопрос 7.24. Дан следующий отрезок программы, на вводе которого положительное целое число:

readln(Num);

while abs(Num) > 0 do

begin

write(Num);

Num := (abs(Num - 1)*(Num div Num)*(-1);

end;

a).Каким будет вывод для ввода 1? А для ввода 5? b).Какая связь между величиной числа на вводе и числом данных вывода? c).Каково назначение этого отрезка программы?

?Вопрос 7.25. Дан неполный отрезок программы, на вводе которого два целых положительных числа Х и У, а его целью является вывод остатка от деления Х на У(т.е. результата вычисления Х mod Y). В этом фрагменте необходимое вычисление осуществляется посредством действия вычитания. Дополни фрагмент.

readln(X, Y);

while __________ do

X := X - Y;

writeln(__);

?Вопрос 7.26. Разработай и реализуй алгоритм, ввод которого есть два целых положительных числа Х и У, а вывод есть частное от деления Х на У(Х div Y) и остаток от деления Х на У(Х mod Y). Использовать в алгоритме можно только действия сложения и вычитания.

?Вопрос 7.27. Два ученика, играющих один против другого, проводят в начале игры линию длиной N > 1 (см). Игроки играют по очереди. Каждый игрок в свою очередь сокращает линию вдвое. Выигрывает тот игрок, после хода которого длина линии окажется меньше 1 см. Например, если начальная длина линии

была 8.0 см, то первый игрок сократит ее до 4.0 см, второй - до 2.0 см, первый - до 1.0 см, а второй, сократив линию до 0.5 см, - выигрывает. Разработай и реализуй алгоритм, ввод которого есть начальная длина линии, а вывод - сообщение о том, кто выиграл(например: первый выиграл или второй выиграл).

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

Задача 5. Дана следующая программа:

program Odds; {Ввод: целое положительное число}

{Вывод: нечетные положительные числа меньше заданного}

var

Limit: integer; {заданное число}

OddN: integer; {нечетное число}

begin

writeln('Введи целое положительное число: ');

readln(Limit);

writeln('Нечетные числа, которые меньше заданного числа: ');

OddN := 1;

while OddN <> Limit do

begin

write(OddN:5);

OddN := OddN + 2

end;

writeln;

end.

Цель программы дана в примечаниях к вводу и выводу следом за заголовком. Вычисли, сколько раз отработает цикл этой программы для заданного ввода L .

Чтобы выразить в общей форме(для заданного L) сколько раз выполнится цикл этой программы, вычислим сперва число исполнений цикла для разных конкретных примеров ввода. Для ввода 1 тело цикла не выполнится ни разу, т.к. значения OddN и Limit оба равны 1 при первом же вычислении значения выражения OddN <> Limit (условие вхождения в цикл). Для ввода 5 исследуем число повторений цикла с помощью таблицы слежения:

Следующий исполнимый оператор

OddN

Limit

OddN <> Limit

Вывод

...........

.....

.....

 

 

OddN := 1;

 

 

 

 

 

1

5

 

 

while OddN <> Limit do

 

 

 

 

 

true

 

write(OddN:5);

 

 

 

1

 

 

 

OddN := OddN + 2;

 

 

 

 

 

3

 

 

while OddN <> Limit do

 

 

 

 

 

true

 

write(OddN:5);

 

 

 

3

 

 

 

OddN := OddN + 2;

 

 

 

 

 

5

 

 

while OddN <> Limit do

 

 

 

 

 

false

 

Для ввода 5 цикл исполнится дважды и выведет 1 3 .

Аналогично мы можем увидеть, что для ввода 15 тело цикла исполнится 7 раз,

будет выведено 1 3 5 7 9 11 13.

?! На секунду задумаемся ... Попытаемся обобщить согласно рассмотренных примеров число повторений цикла для нечетного ввода, равного L . Каким будет общее выражение?

Выражение числа повторений цикла для нечетного L таково: (L - 1)/2.

?! На секунду задумаемся ... Получили формулу общего выражения числа повторений цикла для нечетных вводов. А существует ли подобное выражение

для вводов четных?

Исследуем число повторений цикла для ввода 5 с помощью таблицы слежения:

Следующий исполнимый оператор

OddN

Limit

OddN <> Limit

Вывод

...........

.....

.....

 

 

OddN := 1;

 

 

 

 

 

1

2

 

 

while OddN <> Limit do

 

 

 

 

 

true

 

write(OddN:5);

 

 

 

1

 

 

 

OddN := OddN + 2;

 

 

 

 

 

3

 

 

while OddN <> Limit do

 

 

 

 

 

true

 

write(OddN:5);

 

 

 

3

 

 

 

OddN := OddN + 2;

 

 

 

 

 

5

 

 

while OddN <> Limit do

 

 

 

 

 

true

 

........................................

............

........

...................

 

Мы прервали заполнение таблицы до полного завершения слежения. Мы видим, что для ввода 2 после числа 1 выведено число 3, которого не должно быть на выводе: это нечетное число не меньше введенного. Но можно увидеть нечто большее. При вычислении во второй раз булева выражения OddN <> Limit (условие вхождения в цикл) значение OddN равно 3, а значение Limit равно 2, поэтому значение булева выражения есть true и на печать выводится 3. Значение OddN увеличивается на 2 в теле цикла, цикл будет выполнен в третий раз (и будет выведено число 5). На самом деле цикл будет выполняться вновь и вновь, а значение булева выражения всегда будет true, поскольку значение OddN будет только возрастать. Т.е. цикл будет исполняться бесконечное число раз.

Цикл будет исполняться бесконечное число раз и для ввода 4, и для ввода 6, а на самом деле для любого четного ввода. И все потому, что для четного ввода условие вхождения в цикл будет исполняться вновь и вновь и ни разу Limit и OddN не сравняются. А т.к. цикл будет выполняться бесконечное число раз для четного ввода, то будут выведены нечетные числа, которые не следовало выводить. Значит программа ошибочная!

?! На секунду задумаемся ... А как исправить программу, чтобы цикл исполнялся верное число раз и для любого четного ввода?

Можно изменить условие вхождения в цикл на OddN < Limit, и тогда выполнение цикла будет завершаться после вывода наибольшего нечетного числа, какое нужно вывести.

program Odds; {Ввод: целое положительное число}

{Вывод: нечетные положительные числа меньше заданного}

var

Limit: integer; {заданное число}

OddN: integer; {нечетное число}

begin

writeln('Введи целое положительное число: ');

readln(Limit);

writeln('Нечетные числа, которые меньше заданного числа: ');

OddN := 1;

while OddN < Limit do

begin

write(OddN:5); OddN := OddN + 2

end;

writeln;

end.

Конец решения задачи 5

 

Представим новинку из решения примера - задачи 5. Программа этой задачи содержит цикл, который исполняется как положено для любого нечетного ввода, но он будет исполняться бесконечное число раз для любого четного вывода. Цикл, выполняющийся бесконечное число раз для какого-либо ввода, называется бесконечным циклом. В учебном материале Оснований компьютерных наук программы, которые будут включать бесконечные циклы, являются ошибочными. Не раз случается при разработке алгоритма бесконечный цикл. Такой цикл обычно выполняется бесконечное число раз только для части вводов. Поэтому очень важно проверять цикл алгоритма для исчерпывающего набора представительных примеров ввода, как мы это делали решая задачу 5. Там мы сперва проверили цикл для примера нечетного ввода и увидели, что для него цель достигается; а затем проверили пример четного ввода и показали, что этот цикл - бесконечный.

?Вопрос 7.28. Оцени каждый из следующих вводов - является ли он бесконечным. Если цикл конечный(т.е. не бесконечный), то оцени число его повторений. Воспользуйся таблицей слежения за ходом требуемых вычислений.

a

b

c

I := 0;

while I < 30 do

I := I + 4;

J := 0;

while J < 50 do

J := J - 10;

J := 0;

while abs(J) < 50 do

J := J - 10;

d

e

f

K := 0;

for J := 1 to 10 do

k := k + 11;

Для ввода N - любого целого положительного числа:

readln(N);

while N <> 10 do

begin

write(N);

N := N + 1;

end ;

Для ввода N - любого целого положительного числа:

readln(N);

while N <> 0 do

begin

write(N);

N := N - 1;

end ;

?Вопрос 7.29. Дан фрагмент программы, вводящей произвольное целое число:

readln(X);

while X <> 0 do

begin

X := X mod 3;

write(X);

end;

Цикл программы выполняется конечное число раз для части возможных вводов и бесконечное число раз - для остальных. Поэтому цикл в этой программе является бесконечным. a).Дай пример ввода, для которого цикл исполнится конечное число раз. Какова особенность вводов, которые исполняются конечное число раз? И сколько раз будут они выполняться для этих вводов? b).Дай пример ввода, для которого цикл исполняется бесконечное число раз. Какова особенность вводов, которые исполняются бесконечное число раз? c).Измени условие вхождения в цикл так, чтобы он выполнялся для всех вводов конечное число раз.

?Вопрос 7.30. На вводе у следующего фрагмента программы два целых числа:

readln(X, Y);

while X <> Y do

begin

Y := Y - 1;

X := X + 1;

write(X);

end;

writeln(X);

a).Дай два различных примера ввода, для которых тело цикла не исполнится ни разу. b). Дай два различных примера ввода, для которых тело цикла исполнится точно один раз. c). Дай два различных примера ввода, для которых тело цикла исполняется точно пять раз. d). Дай два различных примера ввода,

 

для которых тело цикла исполняется бесконечное раз. c). Пусть первое данное на вводе(т.е. Х) равно 0. Для каких значений второго данного на вводе тело цикла будет исполняться бесконечное число раз?

?Вопрос 7.31. Играют в жетоны так: игрок выкладывает 2 жетона первым своим ходом, 4 жетона вторым ходом, 8 жетонов на третьем ходу и т.д. - игорок выкладывает жетонов вдвое больше, чем в предыдущую очередь. Дан фрагмент программы, на вводе которой начальное число жетонов у игрока, а на выводе - порядковый номер его очереди, когда он не сможет продолжить игру по указанному правилу (например, для начального числа жетонов 9 вывод должен быть 3, поскольку после потери 2 жетонов на первом ходу и еще 4-х жетонов на втором у него останется только 3 жетона(а не 8 как надо) для третьего хода).

.......................................

var

Turn: integer; {порядковый номер очереди(хода)}

Put: integer; {число жетонов для очередной игры}

Total: integer; {сумма жетонов, вычисленных для сделанных ходов}

Cupons: integer; {начальное число жетонов}

begin

writeln(Введи начальное число жетонов: );

readln(Cupons);

Turn := 0;

Put := 0;

Total := 0;

while Total <= Cupons do

begin

Turn := Turn + 1;

Put := Put*2;

Total := Total + Put;

end;

writeln(Очередь, когда нельзя продолжить игру описанным способом, есть , Turn);

end.

Фрагмент этот ошибочен. Найди ошибку и исправь ее.

Мы рассматривали до сих пор структуры выполни количество раз ... и до тех пор, пока ... выполняй ... для повторного исполнения подзадания. Принято называть первую структуру циклом for, а вторую - циклом while. Есть задачи, которые можно решать и с помощью цикла for, и с помощью цикла while. А есть задачи, которые можно решать только посредством цикла while. Когда можно до выполнения цикла вычислить число его повторений, допустимо пользоваться и циклом for и циклом while. В таких случаях мы предпочтем(как правило) цикл for не while), поскольку указанное написание проще. Когда же нельзя вычислить число повторений до цикла, надо писать цикл while.

?Вопрос 7.32. Надо написать цикл вывода 50 звездочек. a).Напиши цикл for для требуемого вывода. b).Напиши цикл while добавлением нужного предшествующего оператора) для требуемого вывода.

Какое из двух написанных тобой решений (a или b) проще.

?Вопрос 7.33. В роще умножения количество деревьев каждый год увеличивается в 5 раз до тех пор, пока это количество не перейдет некий порог умножения. Необходимо разработать алгоритм, на вводе которого два данных: начальное число деревьев и порог умножения. А на его выводе - количество деревьев в роще в тот год, когда их количество перейдет порог умножения. a).В алгоритме решения задачи пользоваться только циклом while и нельзя пользоваться циклом for. Почему? b).Разработай (без реализации) требуемый алгоритм.

В цикле for в теле цикла можно использовать значение управляющей переменной, но нельзя заносить в него значения.

Примеры

Целью следующего цикла for является вывод чисел 1 2 3 ... 50:

for I := 1 to 50 do

write(I, );

Целью следующего цикла for является вывод суммы 1+ 2 + 3 + ... + N, где N задается на вводе:

readln(N);

Sum := 0;

for I := 1 to 50 do

Sum := Sum + I;

writeln(Sum);

Цель следующего цикла for есть вывод четных чисел от 2 до 20:

for I := 1 to 10 do

write(I*2, );

Следующая форма записи запрещена, т.к. в теле цикла for есть оператор присвоения значения переменной управления I :

for I := 1 to 10 do

I := I*2;

 

Обрати внимание на то, что в цикле while нет переменной управления, поэтому запрещение, касающееся цикла for, не имет отношения к циклу while.

?Вопрос 7.34. a).Напиши цикл while необходимым добавлением перед ним) для достижения цели, описанной выше в первом примере цикла for. b).Напиши сперва цикл for, а затем цикл while необходимым добавлением перед ним) для вывода 20 первых положительных произведений на 5(т.е. 5 10 ...)

?Вопрос 7.35. Оцени для решения каждой из следующих задач, какой из операторов цикла for или while подходит больше. Кратко аргументируй свои ответы. a).На вводе целое положительное число N , а на выводе список целых положительных чисел от 1 до N. b).На вводе целое положительное число N , а на выводе список целых отрицательных чисел от -1 до -N. c).На вводе целое положительное число N , а на выводе список целых положительных чисел от 1 до наименьшего числа K, для которого выполняется 1 + 2 + ... + K > N .

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

Задача 6. Разработай и реализуй алгоритм, на вводе которого слово на английском(в конце - звездочка), а на выводе - слово, закодированное так, что каждая буква заменяется на следующую букву АВС в циклической форме (т.е. любая буква, кроме Z, заменяется на следующую букву, а буква Z заменяется на А). Например для ввода ZEBRA* вывод будет AFCSB.

?Вопрос 7.36. Опиши вывод для следующих вводов: a).JERUSALEM* b).ZIV*

При первоначальном анализе задачи можно видеть, что необходимо в цикле исполнять два подзадания:

Ввод буквы

Определение и вывод следующей за введенной(циклически) буквы

?! На секунду задумаемся ... Если бы ввод сначала задавал число букв в заданном слове, то следовало бы разработать алгоритм, аналогичный тому, что в параграфе 7.1 с использованием команды Выполни число раз ... Но число букв

не дается в начале ввода. Вместо этого числа в конце ввода появляется знак * (звездочка), обозначающая конец ввода. Как использовать этот знак в команде повторного исполнения?

Мы будем использовать знак * для решения о завершении повторных исполнений описанных подзаданий. Т.е. после ввода символа он сравнивается со знаком *. Если введенный символ не есть *, то это - буква, а потому надо определить и выдать следующую(в АВС) букву. Иначе - цикл завершается.

Сформулируем описанную идею:

До тех пор, пока последний введенный символ не * выполняй {введена буква}

Определи и выдай следующую(циклически) за введенной букву

?! На секунду задумаемся ... В описанный цикл мы еще не включили команду ввода символа. Как ее подключить?

Надо вводить символ перед сравнением с *. Т.е. придется подключать команду

ввода в двух местах: непосредственно перед циклом и в конце тела цикла. Команда перед циклом введет первый символ, а команда в конце тела цикла будет вводить следующие(вплоть до ввода знака конца ввода). Т.о. получается:

Введи символ

До тех пор, пока последний введенный символ не * выполняй {введена буква}

Определи и выдай следующую(циклически) за введенной букву

Введи символ

Обрати внимание на то, что в описанной команде цикла с условием символ вводится в конце одного его исполнения, а обрабатывается в ходе следующего исполнения цикла.

Определим переменную Ch символьного типа для хранения введенного символа и сформулируем подробный алгоритм решения задачи:

Введи символ в Ch

До тех пор, пока Ch <> * выполняй

Если Ch <> Z то

выведи идущий следом за Ch символ

иначе

выведи символ A

Введи символ в Ch

Следующая программа на Паскале реализует алгоритм решения этой задачи:

program EncodeWord; {Ввод: слово на английском, за которым '*'}

{Вывод: закодированное слово, буквы заменены следующими в ABC(циклически)}

var

Ch: char; {вводимый символ}

begin

writeln('Вводи буквы английского слова, а в конце - звездочку: ');

readln(Ch);

while Ch <> '*' do

begin

if Ch <> 'Z' then

writeln(succ(Ch))

else

writeln('A');

readln(Ch)

end

end.

Проследим за ходом программы EncodeWord для ввода ZIV*

Следующий исполнимый оператор

Ch

Ch <> *

Ch <> Z

Вывод

...........

 

 

 

readln(Ch);

 

 

 

 

 

Z

 

 

 

while Ch <> '*' do

 

 

 

 

 

true

 

 

if Ch <> 'Z' then

 

 

 

 

 

 

 

false

 

writeln('A');

 

 

 

 

 

 

 

А

readln(Ch)

 

 

 

 

 

I

 

 

 

while Ch <> '*' do

 

 

 

 

 

true

 

 

if Ch <> 'Z' then

 

 

 

 

 

 

 

true

 

writeln(succ(Ch));

 

 

 

 

 

 

 

J

readln(Ch)

 

 

 

 

 

V

 

 

 

 

while Ch <> '*' do

 

 

 

 

 

true

 

 

if Ch <> 'Z' then

 

 

 

 

 

 

 

true

 

writeln(succ(Ch));

 

 

 

 

 

 

 

W

readln(Ch)

 

 

 

 

 

*

 

 

 

while Ch <> '*' do

 

 

 

 

 

false

 

 

Конец решения задачи 6

Представим новинку из решения-примера задачи 6. Структура цикла, которую мы сформулировали в решении задачи, отличается от структуры циклов, которые мы рассматривали прежде в этой главе. В тех циклах читался список данных ввода, команда ввода была в теле цикла, сразу за вводом шла его обработка. Структура тела цикла соответствовала задачам, в которых не содержался ввод специального знака, обозначающего конец ввода.

В задачах типа задачи 6, где конец списка данных ввода обозначается специальным знаком и необходимо формулировать цикл, выполнение которого будет завершаться по прочтении этого знака, будем использовать две команды ввода, как это продемонстрировано в решении задачи: одна - до цикла и вторая - в конце тела цикла. Общая структура цикла будет такой:

Введи данное

До тех пор, пока введенное данное не есть знак конца ввода, выполняй

Обработай введенное данное

Введи данное

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

?Вопрос 7.37. Дан фрагмент программы, в нем I - целая переменная, а Ch - типа символ. На вводе - английское слово, в конце постовой *. Какова цель фрагмента?

I := 0;

read(Ch);

while Ch <> * do

begin

I := I + 1;

read(Ch)

end;

writeln;

write(I);

?Вопрос 7.38. Разработай и реализуй алгоритм, на вводе которого список оценок - целых чисел от 0 до 100, в конце которого постовой -1, а на выводе число отметок, которые больше или равны 60.

?Вопрос 7.39. В выборах из двух кандидатов, А и В, побеждает тот, за которого проголосуют больше половины избирателей. Надо разработать и реализовать алгоритм, на вводе которого последовательность символов А и В, выражающих голосование избирателей, а на выводе сообщение о том, выиграл ли А большинством голосов(больше половины голосов избирателей). Конец ввода отмечается постовым *. Например для ввода:

АВВААВВАА* вывод будет А победил большенством голосов

И для ввода АВВАВВАА* вывод будет А не победил большенством голосов

Следующая неполная программа есть реализация алгоритма решения задачи:

program Majority; {Ввод: последовательность голосов за А и за В, в конце - *}

{Вывод: сообщение - победил ли А большинством голосов}

var

Vote: char;

Balance: integer;

begin

Balance := 0;

writeln(Вводи последовательность голосов за А и за В, в конце звездочка: );

read(Vote);

while Vote <> * do

begin

if Vote = A then

Balance := ______________

else

Balance := ______________ ;

read(Vote)

end;

writeln;

if Balance > 0 then

write победил большинством голосов)

else

write не победил большинством голосов)

Программа использует переменную Balance, в которой накапливаются голоса за А и не за А. Дополни эту программу.

?Вопрос 7.40. Выбирают комитет, есть три кандидата: кандидат номер 1, кандидат номер 2 и кандидат номер 3. Разработай и реализуй алгоритм, на вводе которого список голосов(т.е. каждый голос это одно из чисел 1, 2 или 3). В конце списка - 0. А на выводе - процент голосов, которых удостоился кандидат номер 2.

Назначение следующей задачи и ее решения. Представление способа вычисления наибольшего данного в списке данных.

Задача 7. Одна из основных задач компьютерных наук состоит в определении наибольшего данного в списке данных. Разработай и реализуй алгоритм, на вводе которого список(не пустой) целых чисел, завершающийся на 0 (все числа списка отличаются от 0), а на выводе наибольшее число в списке.

?! На секунду задумаемся ... Если бы список содержал три данных, то ввели бы сперва два первых данных и определили наибольшее из них. Затем ввели бы третье данное и сравнили его с наибольшим из двух первых. Можно ли обобщить эту идею на список с произвольным числом данных?

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

Сравнение последнего введенного данного с наибольшим данным среди всех введенных до него и в зависимости от результата сравнения - установление наибольшего данного среди всех введенных данных

?! На секунду задумаемся ... Как мы выразим в алгоритме указанную идею подзадания для повторных исполнений?

Определим следующие переменные:

Num - целого типа, будет хранить введенное число.

Max - целого типа, будет хранить наибольшее число из тех, которые уже введены.

Начальным значением Max будет первое в списке число. После ввода каждого дополнительного числа оно сравнивается с числом, хранимым в Max. И если введенное число больше числа, хранящегося в Max, то значение Max заменяется на новое введенное число. Алгоритм решения задачи будет таким:

Введи первое число в Max

Введи следующее число в Num

До тех пор, пока Num <> 0 выполняй

Если Num > Max то

помести значение Num в Max

Введи следующее число в Num

Выведи значение Max

Программа, реализующая алгоритм, будет такой:

program FindMax; {Ввод: список целых чисел, за которым постовой 0}

{Вывод: наибольшее в списке число}

var

Num: integer; {вводимое число}

Max: integer; {наибольшее число из всех до сих пор введенных}

begin

writeln('Введи список целых чисел, а за последним числом - 0: ');

read(Max);

read(Num);

while Num <> 0 do

begin

if Num > Max then

Max := Num;

read(num)

end;

writeln;

writeln('Наибольшее число в списке: ',Max)

end.

Конец решения задачи 7

?Вопрос 7.41. Построй таблицу слежения за ходом программы FindMax, решающей задачу 7, для ввода 1 2 -6 5 4 5 0 . Сколько раз будет заноситься значение в переменную Max в ходе исполнения прогрраммы.

?Вопрос 7.42. В решении задачи 7 начальным значением Max было первое значение в списке. Будет ли решение верным, если начальным значением Мах будет какая-нибудь постоянная, например, 0?

?Вопрос 7.43. Дан неполный фрагмент программы для вычисления наименьшего значения в списке отрицательных чисел, длина которого N задается до списка. Дополни фрагмент программы(добавь переменную(-ые), если нужно). В первом операторе придай переменной Min начальное значение в виде постоянной.

Min := _______

readln(N);

for I := 1 to N do

............................

writeln(Min);

?Вопрос 7.44. Разработай и реализуй алгоритм, на вводе которого последовательность букв алфавита АВС, которая завершается на *, а вывод ее - наибольшая из букв от B до I, которые есть на вводе. Например, для ввода SCHOOL* вывод будет Н. В действительности на вводе есть буквы больше, чем Н, например, S, но эти буквы не входят в последовательность от В до I. Среди букв на вводе из интервала от B до I наибольшей является Н. Положим, что на вводе хотя бы одна буква будет принадлежать интервалу от B до I.

?Вопрос 7.47. Оцени для решения каждой из следующих задач, какой из операторов цикла for или while подходит больше. Кратко аргументируй свои ответы. a).На вводе последовательность букв со звездочкой в конце, а на выводе - наибольшая буква из появившихся на вводе. b).На вводе целое положительное число, задающее длину последовательности, и следом последовательность букв этой длины; на выводе - наименьшая буква из представленных на вводе. c).Ввод из вопроса b, а вывод - порядковый номер первого появления наибольшей буквы на вводе(возможно таких букв не одна). Для задачи c разработай(без реализации) алгоритм ее решения.

 

Резюме

В этой главе мы видели, как организовать многократное исполнение подзадания. Это делается посредством команды управления повторным исполнением, называемой циклом. Команда эта управляет повторным исполнением группы команд. Мы познакомились с двумя структурами команд цикла: в одной число повторений определяется заранее, а во второй задается условием.

Команда цикла, число повторений которого определено заранее, записывается так:

Исполни число раз

.................

Команда цикла, число повторений которого задается условием, записывается так:

До тех пор пока .... исполни

...................................

При написании команды цикла группа повторяющихся команд сдвигается внутрь.

Команда повторных исполнений назывется циклом(loop). Группа команд, которая повторяется в цикле, назывется телом цикла, а условие повторного исполнения (в команде до тех пор пока .... исполни ... ) называется условием вхождения в цикл. Команда цикла используется, среди прочего, для действий накопления и подсчета. Накопление осуществляется в накопителе, а подсчет - в счетчике. Накопитель это переменная, которая предназначается для накопления данных или результатов вычисления. Т.е. накопитель используется для суммирования значений. Счетчик это переменная, которая предназначается для подсчета числа появлений данных или числа осуществленных вычислений. Т.е. счетчик используется для подсчета числа явлений. А потому он, обычно, имеет целый тип.

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

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

Введи данное

До тех пор, пока введенное данное не есть знак конца ввода, выполняй

Обработай введенное данное

Введи данное

В таком цикле данное, введенное в конце одного исполнения цикла, обрабатывается в ходе следующего его исполнения.

Как и в предыдущих главах здесь мы разрабатывали и реализовывали алгоритмы строго по этапам. В ходе разработки мы подчеркивали формулирование подзадания(-ий) тела цикла и условия вхождения в него.

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

Паскаль главы 7

Команда цикла исполни число раз ... в Паскале реализуется с помощью оператора for. Общая структура оператора for такова:

for переменная_управления := начальное_значение to конечное_значение do

оператор

Оператор в составе оператора for может быть простым или составным. В начале исполнения оператора for начальное_значение заносится в переменную_управления и исполняется оператор . По завершении оператора значение управляющей переменной увеличивается на 1 и снова выполняется оператор. И так до тех пор, пока значение управляющей переменной не станет равным конечному_значению. Оператор исполнится в последний раз при значении управляющей переменной, равной конечному значению. Но после завершения оператора for значение управляющей переменной не известно.

Оператор for называется циклом for, а оператор , исполняющийся повторно в операторе for называется телом цикла. Переменная управления в операторе for , с которой мы познакомились сначала, имеет целый тип. Ее необходимо объявлять подобно любой другой переменной.

Команда цикла с условием до тех пор пока ... исполни ... в Паскале реализуется с помощью оператора while. В этом операторе условие повторения цикла задается булевым выражением. Общая структура оператора while такова:

while булево_выражение do

оператор

Оператор в составе оператора while может быть простым или составным. Исполнение оператора while начинается вычислением значения булева_выражения. Если его значение есть true, то выполняется оператор. По завершении исполнения оператора снова вычисляется значение булева выражения. Если его значение есть true, оператор выполняется снова. Этот процесс продолжается до тех пор, пока значение булева выражения остается true. Когда его значение оказывается false, выполнение оператора while завершается. Оператор while называется циклом while. Оператор именуется телом цикла, а булево выражение - условием вхождения в цикл.

 

Глава 8. Эффективность алгоритмов

Ключевые слова: Эффективность алгоритма, основные операции, время выполнения алгоритма.

Алгоритмы различаются по ряду параметров. Самым важным параметром является правильность алгоритма, т.е. достижение цели для любого законного ввода. Еще одним параметром алгоритма является эффективность. Эффективность алгоритма(программы) измеряется ресурсами компьютера, которые нужны для осуществления алгоритма. Эти ресурсы суть размер места (в памяти) и время, необходимое для исполнения алгоритма. Размер памяти измеряется, можно сказать, числом переменных алгоритма. Время исполнения устанавливается числом основных операций, которые осуществляются в ходе исполнения алгоритма. Основными действиями являются: операция ввода, операция вывода и операция вычисления. Для простоты будем считать, что любая команда алгоритма содержит одну основную операцию; а отсюда - измерение времени выполнения алгоритма ведется по числу команд, которые будут исполнены в ходе его исполнения.

Обрати внимание на то, что указанная мера есть число исполненных команд, а не число команд в алгоритме! Это число команд не обязательно свидетельствует о числе команд, которые будут исполнены в ходе осуществления алгоритма. Алгоритм может содержать цикл, в котором немного команд, а число исполняемых команд - велико. Это обстоятельство детализируем далее в главе.

Измерение времени исполнения не осуществляется по времени работы программы, реализующей алгоритм. Тому есть несколько причин. Одна причина состоит в том, что исполнение одной программы на двух разных компьютерах может продолжаться различное время, поскольку основные операции на разных компьютерах требуют различного времени. Еще одна причина состоит в том, что на компьютере, допускающем параллельную работу нескольких программ, время исполнения программы может быть одним в одно время и другим - в другое. Это связано с тем, что на компьютере в разное время возможна разная нагрузка (можно это сравнить со временем ожидания в ресторане - оно короче, когда в ресторане меньше посетителей. Аналогично, время ожидания завершения прогона программы короче, когда параллельно на компьютере запущено немного(или вовсе нет других) программ). Третья причина в том, что компиляция программы разными компиляторами приводит к созданию различных программ на машинном языке, и у каждой из этих программ время прогона будет немного отличаться, даже если они будут запущены на одном компьютере и в то же время.

В этой главе мы сосредоточимся на времени исполнения алгоритма и познакомимся с разными алгоритмами решения одной задачи, которые отличаются друг от друга, иногда очень значительно, по времени исполнения. Продемонстрируем разницу между временами исполнения двух разных алгоритмов решения одной задачи, с которой мы часто сталкиваемся в повседневной жизни. Эта задача - поиск в упорядоченном списке - также является фундаментальной в компьютерных науках. Когда дан список имен, упорядоченный в алфавитном порядке, и нужно проверить находится ли в списке определенное имя, поиск можно вести разными методами. Одна такая возможность заключается в последовательном поиске, т.е в проходе по списку, имя за именем, вплоть до нахождения искомого имени или выяснения, что такого имени в списке нет. Ясно, что это не способ поиска имени в упорядоченном длинном списке вроде телефонной книги. Другой путь, более похожий на поиск в телефонной книге, есть следующий непоследовательный поиск: выбор имени , которое находится посередине списка, и сравнение его с разыскиваемым именем; если имена оказались идентичными, то процесс поиска завершается, иначе он продолжается в первой половине списка(если срединное имя находится после искомого по алфавиту) или во второй половине списка(если срединное имя находится по алфавиту перед искомым); поиск в оставшейся половине будет выполняться аналогично, т.е. выбирается имя посредине оставшейся половины, его сравнивают с искомым именем и поиск продолжается согласно результатов сравнения.

Описанный непоследовательный поиск называется бинарным, поскольку он основан на сокращении всякий раз области поиска вдвое после каждого сравнения искомого и избранного имен. Когда список имен длинный, очень важно выбрать такой путь, который позволит выполнять задание поиска за самое короткое время. Время поиска устанавливается, в основном, по числу сравнений(искомого и выбранного имени), которые выполняются в ходе поиска, а потому мы предпочтем остановиться на таком способе, где будет выполняться меньше сравнений. Для списка длиной 1000 имен, например, возможное число сравнений при последовательном поиске может приближаться к 1000, т.к. искомое имя может находиться в конце списка. А вот число сравнений бинарным поиском в том же списке в любом случае не превысит 10(в следующих главах мы познакомимся с бинарным поиском более детально). Поэтому в данной задаче бинарный поиск значительно эффективнее.

Некоторые люди считают, что скорость прогона компьютерных программ сейчас так велика, что нет смысла в понятии время исполнения алгоритма (программы) и в сравнении времен исполнения различных алгоритмов. Для такого мнения нет оснований. Существуют задачи, для которых время исполнения программ может составлять многие минуты, часы и даже дни(например, программа прогноза погоды). А для задачи поиска, которую мы представили, время исполнения программы последовательного поиска в списке длиной 10000000 имен может составить несколько минут. А время работы программы бинарного поиска с тем же списком и на том же компьютере не превысит нескольких секунд.

Время исполнения алгоритма измеряется, как было сказано, числом команд, исполненных в ходе его работы. Это число зависит (как правило) от ввода алгоритма. Например, в задаче поиска ввод алгоритма есть список упорядоченных имен и разыскиваемое имя. Число команд, которые будут выполнены, зависит от длины списка имен: чем он длиннее, тем больше нужно будет сравнений, т.е. больше будет исполнено команд сравнения.

В решении следующей задачи мы увидим пример алгоритма, время исполнения которого зависит от значения ввода.

Назначение следующей задачи и ее решения. Представление двух разных алгоритмов решения задачи, один из которых менее эффективен, а второй - более точки зрения времени исполнения). В более эффективном алгоритме хорошо используются особенности ввода-вывода.

Задача 1. Разработай и реализуй алгоритм, на вводе которого целое число больше 1, а на выводе - делители данного числа. Опиши время исполнения алгоритма с помощью оценки числа исполняемых алгоритмом команд. Делитель целого положительного числа есть целое положительное число, на которое данное делится без остатка. Для ввода, например, 6 вывод будет 1 2 3 6.

?Вопрос 8.1. Оцени вывод для следующих вводов: a).12 b).29 c).30

Область целых чисел, в которой находятся выводимые делители находится между 1 и заданным на вводе числом. Надо выдать каждое число этой области, на которое заданное число делится без остатка.

?! На секунду задумаемся ... Как можно определить нужные на выводе числа?

Представим сперва первую пришедшую на ум идею. Можно прочесать интервал от 1 до заданного числа, проверяя каждое число интервала является ли оно делителем заданного числа. Дадим первую формулировку решения:

Проход по всем положительным числам от 1 до заданного числа и вывод таких, на которые оно делится без остатка

?! На секунду задумаемся ... Описанная идея в действительности содержит подзадание с циклом. Что это за подзадание?

Описанная идея содержит для каждого числа интервала от 1 до заданного числа исполнение в цикле следующего подзадания:

Выведи число, если на него делится без остатка заданное число

Сформулируем алгоритм, выражающий описанную идею. Его переменные:

N - целого типа, хранит заданное на вводе число

I - целого типа, переменная управления цикла в алгоритме

Алгоритм 1

Введи в N целое положительное число

Выполни для I от 1 до N

если N делится на I без остатка то

выведи на печать значение I

Обрати внимание , мы пользуемся не формулировкой выполни число раз ... , а формулировкой выполни для I от ... , подобной циклу for в Паскале. Это сделано для того, чтобы детализировать интервал значений, который пробегает переменная управления цикла.

В алгоритме имеет место использование переменной управления в теле цикла. Последний содержит проверку, является ли значение управляющей переменной делителем для N. Поскольку в ходе исполнения цикла управляющая переменная пробегает от 1 до N, проверке подвергается каждое целое число от 1 до N.

Программа, реализующая алгоритм 1, будет такой:

program Divisors_1; {Ввод: целое положительное число}

{Вывод: список делителей заданного числа}

var

N: integer; {заданное число}

I: integer; {переменная управления}

begin

writeln('Введи целое положительное число: ');

readln(N);

writeln('Делители заданного числа: ');

for I := 1 to N do

if (N mod I) = 0 then {I - делитель заданного числа}

write(I,' ');

writeln

end.

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

?! На секунду задумаемся ... Какая основная компонента алгоритма свидетельствует о числе исполняемых команд?

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

Поскольку цикл может исполняться много раз, число команд, которые будут осуществляться по ходу алгоритма, может быть много больше числа написанных в нем команд. Например, при осуществлении алгоритма 1 для ввода 1000 комада исполнения с условием в теле цикла выполнится 1000 раз. Это число во много раз больше числа команд в алгоритме. Как правило число повторений цикла будет различным для разных вводов. Поэтому, чтобы описать в общей форме число исполнений цикла, надо выразить это число соответственно вводу.

?! На секунду задумаемся ... Каково число исполнений цикла в алгоритме 1 для ввода, значение которого есть N?

В алгоритме 1 для ввода, значение которого есть N, цикл будет исполнен N раз. Цикл будет исполняться по одному разу для каждого из значений 1, 2, 3, ... , N управляющей переменной I. Поскольку цикл является основной компонентой алгоритма, свидетельствующей о числе исполняемых операций, принято считать число повторений цикла мерой времени его исполнения. Поэтому скажем, что результатом определения времени исполнения алгоритма 1 является то, что цикл алгоритма исполнится N раз для ввода, значение которого N.

Посмотрим, есть ли у нас возможность разработать алгоритм, в котором цикл будет исполняться меньше чем N раз для ввода, значение которого N?

Да! Можно разработать алгоритм, в котором цикл будет более эффективным.

Одна из особенностей деления целых чисел состоит в том, что делители целого положительного числа N не могут быть больше N/2 , кроме самого числа N. Это можно видеть в ответах на вопросы 8.1(примеры ввода-вывода). Поэтому в действительности надо прогонять в алгоритме управляющую переменную цикла только до N/2. Выразим эту идею в алгоритме 2, который более эффективен.

Алгоритм 2

Введи в N целое положительное число

Выполни для I от 1 до N/2

если N делится на I без остатка то

выведи на печать значение I

Выведи на печать значение N

Здесь мы вывели на печать N за пределами цикла, но основная работа выполняется в цикле. В алгоритме 2 цикл будет выполняться только N/2 раз для ввода, значение которого N. Это существенное улучшение, в особенности для больших значений ввода(например, для 1000).

Программа, реализующая алгоритм 2, будет такой:

program Divisors_2; {Ввод: целое положительное число}

{Вывод: список делителей заданного числа}

var

N: integer; {заданное число}

I: integer; {переменная управления}

begin

writeln('Введи целое положительное число: ');

readln(N);

writeln('Делители заданного числа: ');

for I := 1 to (N div 2) do

if (N mod I) = 0 then {I - делитель заданного числа}

write(I,' ');

writeln(N)

end.

Конец решения задачи 1

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

Решеная задачу 1 сначала мы разрработали один алгоритм. А затем - второй, который оказался эффективнее по критерию числа повторений цикла, т.е. - по времени исполнения. При разработке более эффективного алгоритма мы воспользовались тем, что выводимые делители данного на вводе N не могут быть больше N/2, кроме самого N. Эта особенность позволила нам написать цикл, исполняющийся только N/2 раз, вместо цикла, который будет выполняться N раз. Разработка более эффективного алгоритма осуществлена в результате анализа и рационального использования особенностей ввода-вывода. Такое использование особенностей ввода-вывода важно для написания цикла, который будет исполняться минимальное из возможных число раз. В ходе решения алгоритмической задачи мы будем стараться разрабатывать алгоритм с наибольшей эффективностью с точки зрения времени исполнения. Т.е. алгоритм, цикл которого будет выполняться наименьшее из возможных число раз(эффективный цикл).

?Вопрос 8.2. Оцени вывод для следующих вводов числа повторений цикла в алгоритме 1 и алгоритме 2: a).1000 b).2000

?Вопрос 8.3. В следующем фрагменте вычисляется произведение двух целых положительных данных ввода с использованием только действия сложения:

writeln(Введи два целых положительных числа: );

readln(Х, У);

Sum := 0;

for I := 1 to Х do

Sum := Sum + Y;

writeln(Произведение двух этих чисел есть , Sum);

Известно, что одно из данных ввода существенно больше второго, но неизвестно - какое из них. Воспользуйся этой особенностью ввода для изменения данного фрагмента программы, чтобы он стал наиболее эффективным. Намек. Обрати внимание на то, что важным является выбор переменной, устанавливающей число повторений цикла. Чему равняется число повторений цикла в заданном фрагменте, а чему оно равно в новом фрагменте?

?Вопрос 8.4. Разработай наиболее эффективный алгоритм(без реализации), на вводе которого два целых числа больше 1, которые не делятся одно на другое, а на выводе все целые положительные числа, на которые делятся оба введенных числа. Опиши согласно значений ввода число повторений цикла этого фрагмента.

?Вопрос 8.5(продвинутый). Пусть в задаче 1 требуется такой вывод: все целые положительные числа, на которые не делится заданное значение N. Сколько раз будет повторяться цикл в алгоритме, решающем новую задачу?

?Вопрос 8.6. Надо разработать алгоритм, на вводе которого целое положительное число N, а на выводе все положительные целые числа меньше N, квадратный корень из которых есть целое число. Например для ввода 50 вывод будет 1 4 9 16 25 36 49 . Следующий алгоритм, содержащий перременные целого типа, есть возможное решение:

Введи в N целое положительное число

Выполни для I от 1 до N

если корень из I есть целое число то

выведи на печать значение I

a).Сколько раз повторится цикл данного алгоритма? b).Реализуй посредством булева выражения в Паскале условие корень из I есть целое число . c).Можно написать алгоритм, время исполнения которого будет существенно короче времени исполнения заданного алгоритма, В нем числа вывода производятся возведением во вторую степень всех целых чисел, квадрат которых меньше числа на вводе. Следующий неполный алгоритм базируется на описанной идее:

Введи в N целое положительное число

Выполни для I от 1 до ____

выведи на печать значение I2

Дополни алгоритм и опиши число повторений его цикла.

Все алгоритмы, которые мы анализировали до сих пор в этой главе, содержали цикл for, но есть много алгоритмов, в которых используется цикл while.

В цикле for, как мы видели, переменная управления пробегает значения от 1 до некоторого числа с шагом, равным 1, при этом легко определить число повторений цикла. В цикле while переменная управления отсутствует. Число повторений цикла надо подсчитывать, следя за значениями переменных, уточняемых в теле цикла и входящих в условие вхождения в него. Поупражняемся с этим в следующей задаче.

?Вопрос 8.7. Надо разработать и реализовать алгоритм, на вводе которого два целых положительных числа(второе больше первого), а на выводе все числа, кратные первому, которые меньше или равны второму. числу. Например для ввода 200 1000 вывод будет 200 400 600 800 1000. Следующие операторы являются реализацией алгоритма решения:

writeln(Введи два целых положительных числа(второе больше первого): );

readln(Х, У);

I := X;

while I <= Y do

begin

if (I mod X) = 0 then

write(I);

I := I + 1

end;

a).Сколько раз исполнится цикл для ввода 200 1000? b).Опиши в общей форме число исполнений цикла для заданных значений ввода Х и У. c).В решении значение I наращивается на 1. Можно улучшить эффективность данного решения изменением приращения I на значение больше 1, соответствующему расстоянию между парой последовательных чисел вывода(обрати внимание на то, что это расстояние является неизменным). Напиши более эффективное решение, основанное на описанной идее, укажи число повторений цикла в новом решении.

?Вопрос 8.8. Дан следующий цикл for:

writeln(Введи два целых положительных числа(второе больше первого): );

for I = 1 to 30000 do

if (I mod 500) = 0 then

write(I);

a).Сколько раз исполнится этот цикл? b).Какова цель цикла? c).Напиши значительно более эффективный цикл достижения той же цели с помощью цикла while соответствующего предшествующего оператора). Сколько раз будет исполняться написанный тобой эффективный цикл? И во сколько раз это число меньше твоего ответа на вопрос a.

 

Резюме

В предыдущих главах мы рассматривали алгоритмы с позиций их правильности. В этой главе мы познакомились с иным аспектом - эффективностью. Эффективность алгоритма измеряется согласно компьютерных ресурсов, необходимых для его осуществления. Ресурсами являются размер места в памяти и время, необходимое для исполнения. Размер места измеряется, в основном, числом переменных алгоритма. Тему размера места мы обсудим, оценивая эффективность в 10 главе. Время исполнения определяется числом основных операций, исполняемых по ходу алгоритма. Основными являются: операция ввода, операция вывода и вычислительная операция. Упрощенно можно сказать, что любая команда алгоритма содержит одну основную оперрацию, а отсюда - измерение времени осуществления алгоритма ведется по числу команд, которые будут исполнены по ходу алгоритма.

В алгоритме, который не содержит цикла, число исполняемых команд не превышает число команд алгоритма. А в алгоритме с циклом число исполняемых команд устанавливается не по числу команд в алгоритме, а согласно числу повторений цикла. Это число можно сформулировать в общей форме согласно данным ввода.

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

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

 

Глава 9. Функции для исполнения подзаданий

Ключевые слова. Структурированный алгоритм, функция, параметр, действительный параметр, локальная переменная, предложение входа, предложение выхода.

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

один раз в разработанных нами алгоритмах мы обращал