Слайд 1Программирование
Часть 3
Введение в процедурное программирование
Управляющие инструкции
Слайд 24. Процедурное программирование
4.1. Парадигмы программирования
Парадигма программирования — совокупность теорий, стандартов и
методов, используемых при разработке программ.
Наиболее известные парадигмы программирования:
Процедурное программирование - парадигма программирования, отражающая традиционную архитектуру компьютера - архитектуру Фон Неймана. В соответствии с этой парадигмой программа рассматривается как последовательность инструкций, задающих процедуру решения задачи. Выполнение программы сводится к последовательному выполнению инструкций с целью преобразования исходного состояния памяти, то есть значений исходных данных, в заключительное, то есть в результаты.
Объектно-ориентированное программирование - парадигма программирования, основанная на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определенного класса, а классы образуют иерархию наследования.
Слайд 34. Процедурное программирование
4.2. Принципы структурного программирования
Структурное программирование — методология разработки программного
обеспечения, предложенная в 70-х года XX века Эдсгером Дейкстрой, разработанная и дополненная Никласом Виртом, развитие парадигмы процедурного программирования.
Цели структурного программирования:
Повышение эффективности и надежности программ (разбиение на модули с дальнейшей независимой оптимизацией модулей, простота тестирования и отладки)
Повышение производительности труда программиста (обеспечение дисциплины программирования, улучшение читабельности программ, повышение скорости программирования и возможности коллективной разработки программ)
Слайд 44. Структурное программирование
4.2. Принципы структурного программирования
Использование ограниченного числа управляющих конструкций
(структур):
следование (последовательное исполнение) – однократное выполнение инструкцийй в том порядке, в котором они записаны в тексте программы;
ветвление (выбор) – однократное выполнение одной из двух или более инструкций, в зависимости от выполнения некоторого заданного условия;
повторение (цикл) – многократное исполнение одной и той же инструкции до тех пор, пока выполняется некоторое заданное условие продолжения цикла.
В программе базовые конструкции могут быть вложены друг в друга произвольным образом, но никаких других средств управления последовательностью выполнения инструкций не предусматривается.
Слайд 54. Структурное программирование
4.2. Принципы структурного программирования
Использование ограниченного числа управляющих конструкций
(структур):
Алгоритмические конструкции могут иметь только одну точку входа и одну – выхода;
Инструкция goto не используется;
Не допускается излишняя вложенность алгоритмических структур (не более 3-х уровней вложенности инструкции if)
Не используются языковые конструкции с неочевидной семантикой и программистские «трюки»
Слайд 64. Структурное программирование
4.2. Принципы структурного программирования
Использование подпрограмм (процедур, функций) для
структурирования программ
Повторяющиеся фрагменты программы (либо не повторяющиеся, но представляющие собой логически целостные вычислительные блоки) оформляются в виде так называемых подпрограмм (процедур или функций).
При выполнении размещаемой в программе инструкции вызова подпрограммы (функции) выполняется эта подпрограмма, после чего исполнение программы продолжается с инструкции, следующей за командой вызова подпрограммы.
Каждая подпрограмма реализует только одну логическую функцию
Подпрограмма (функция) имеет одну входную и выходную точку;
Размер подпрограммы не превышает 100 инструкций;
Число других подпрограмм, вызываемых подпрограммой, не должно превышать 7.
Слайд 74. Структурное программирование
4.2. Принципы структурного программирования
Соблюдение специальных требований к оформлению
текстов программ
Каждая функция начинается с комментариев, объясняющих ее назначение, назначение входных и выходных параметров, содержащих перечень и назначение вызываемых ей функций, номер версии и дата последней модификации;
В одной строке записывается не более одной инструкции (если только группа инструкций не выполняет общее действие)
Если для записи одной инструкции требуется больше, чем одна строка, все последующие строки записываются с отступами
Тела инструкций цикла, ветвления, выбора записываются с отступами
Идентификаторы всех объектов программы должны быть смысловыми
Идентификаторы родственных объектов программы должны начинаться с одинакового префикса
Слайд 84. Структурное программирование
4.2. Принципы структурного программирования
Пошаговая детализация при написании текста
программы
На первом шаге описывается общая схема работы в обозримой линейной текстовой форме (т.е. с использованием очень крупных понятий), причем это описание не является полностью формализованным и ориентировано на восприятие его человеком.
На каждом следующем шаге производится уточнение и детализация одного из понятий, использованного (как правило, неформализованно) в каком либо описании, разработанном на одном из предыдущих шагов.
В результате такого шага создается описание выбранного уточняемого понятия либо в терминах языка программирования, либо в такой же форме, что и на первом шаге с использованием новых уточняемых понятий.
Слайд 94. Структурное программирование
4.2. Принципы структурного программирования
Пошаговая детализация при написании текста
программы
Процесс детализации завершается, когда все уточняемые понятия будут выражены в конечном счете на языке программирования.
Последним шагом является получение текста программы на языке программирования путем замены всех вхождений уточняемых понятий заданными их описаниями и выражение всех вхождений конструкций структурного программирования средствами этого языка программирования.
Слайд 104. Структурное программирование
4.2. Принципы структурного программирования
Разработка программы методом «сверху вниз»
На
первом этапе разрабатывается основная программа, в которой вместо каждого связного логического фрагмента текста вставляется вызов функции, которая будет выполнять этот фрагмент.
Вместо настоящих, работающих функций, к программе подключаются специально написанные функции - «заглушки», которые ничего не делают.
Полученная программа проверяется и отлаживается.
После того, как программист убедится, что функциивызываются в правильной последовательности (то есть общая структура программы верна), функции-заглушки последовательно заменяются на реально работающие, причём разработка каждой функции ведётся тем же методом, что и основной программы.
Слайд 114. Структурное программирование
4.2. Принципы структурного программирования
Разработка программы методом «сверху вниз»
Разработка
заканчивается тогда, когда не останется ни одной функции - «заглушки», которая не была бы удалена.
Такая последовательность гарантирует, что на каждом этапе разработки программист одновременно имеет дело с обозримым и понятным ему множеством фрагментов, и может быть уверен, что общая структура всех более высоких уровней программы верна.
При сопровождении и внесении изменений в программу выясняется, в какие именно функции нужно внести изменения, и они вносятся, не затрагивая части программы, непосредственно не связанные с ними.
Слайд 124. Структурное программирование
4.3. Базовые управляющие структуры
Компоненты конструкций структурного программирования
Действие
простая инструкция
используемого языка программирования (инструкция присваивания, ввода, вывода, обращения к процедуре и др.),
фрагмент программы, являющийся композицией основных конструкций структурного программирования.
Каждая из этих конструкций имеет по управлению только один вход и один выход. Тем самым, и обобщенный оператор имеет только один вход и один выход.
P
Условие (предикат):
выражение, результатом которого может быть true или false
В зависимости от значения выражения в программе может быть выполнена передача управления тому или иному узлу обработки
true
false
S
Слайд 134. Структурное программирование
4.3. Базовые управляющие структуры
Следование (последовательное исполнение)
S2
S1
Слайд 144. Структурное программирование
4.3. Базовые управляющие структуры
Ветвление (выбор)
[true]
[false]
S1
S2
Слайд 154. Структурное программирование
4.3. Базовые управляющие структуры
Повторение
S
[true]
[false]
Слайд 164. Структурное программирование
4.3. Базовые управляющие структуры
Правила построения структурированных программ
Диаграмма деятельности
— диаграмма, на которой показано разложение некоторой деятельности на её составные части.
Слайд 174. Структурное программирование
4.3. Базовые управляющие структуры
Вложенные структуры
Состояние действия
Слайд 184. Структурное программирование
4.3. Базовые управляющие структуры
Состояние действия
Состояние действия
Вложенные
структуры
Слайд 194. Структурное программирование
4.3. Базовые управляющие структуры
Состояние действия
Состояние действия
Вложенные
структуры
Состояние действия
Состояние действия
Слайд 204. Структурное программирование
4.3. Базовые управляющие структуры
Состояние действия
Состояние действия
Вложенные
структуры
Состояние действия
Состояние действия
Слайд 214. Структурное программирование
4.4. Ветвления
Условная инструкция if…else
if (Условие)
инструкция1;
else
инструкция2;
[true]
[false]
S1
S2
Слайд 224. Структурное программирование
4.3. Ветвления
Пример использования инструкции if…else
int main() //
determines is the entered number greater than 100 or not
{
int x;
cout << "\nEnter a number: ";
cin >> x;
if( x > 100 )
cout << "That number is greater than 100\n";
else
cout << "That number is not greater than 100\n";
return 0;
}
Слайд 234. Структурное программирование
4.3. Базовые управляющие структуры
Инструкция if
if (Условие)
инструкция;
[true]
[false]
S1
Слайд 244. Структурное программирование
4.4. Ветвления
Пример использования инструкции if
int main() //
determines is the entered number greater than 100
{
int x;
cout << "\nEnter a number: ";
cin >> x;
if( x > 100 )
cout << "That number is greater than 100\n";
return 0;
}
Слайд 254. Структурное программирование
4.3. Ветвления
Несколько инструкций в теле if
#include
#include
using namespace std;
int main() //Guess a magic number
{
unsigned int guess = 0;
unsigned int magic = time (NULL); //returns number of sec. from 01/01/1970
magic &= 0x00000007; // generates pseudo random in [0-7]
cout << "Guess the magic number: "; cin >> guess;
if(guess == magic)
{
cout << endl << "** Right ** magic " ;
cout << magic << "==" << guess << " (guess}";
}
getch ();
return 0;
}
Слайд 264. Структурное программирование
4.3. Ветвления
Несколько инструкций в теле if…else
…
int main()
// Guess a magic number (with message if guessing wasn’t success)
{
…
if (guess == magic)
{
cout << endl << "** Right ** magic " ;
cout << magic << "==" << guess << " (guess}";
}
else
{
cout << endl << "** Wrong ** magic ";
cout << magic << “!=" << guess << " (guess}";
}
…
}
Слайд 274. Структурное программирование
4.3. Ветвления
Вложенные инструкции if…else
…
int main() // more
complicated program to guess a magic number
{
…
if (guess == magic)
{
cout << endl << "** Right ** magic " ;
cout << magic << "==" << guess << " (guess}";
}
else
{
cout << endl << "** Wrong ** ";
if (guess > magic) cout << " too high " ;
else cout << " too low " ;
}
…
}
Слайд 284. Структурное программирование
4.3. Ветвления
Вложенные инструкции: соответствие if и else
…
int main()
{
…
if (i)
{
if (j) инструкция 1;
if (k) инструкция 2;
else инструкция 3;
}
else инструкция 4;
…
}
Слайд 294. Структурное программирование
4.3. Ветвления
Вложенные инструкции: соответствие if и else
…
int main()
{
…
if (i)
{
if (j) инструкция 1;
if (k) инструкция 2;
else инструкция 3;
}
else инструкция 4;
…
}
Во вложенных условных инструкциях раздел else всегда связан с ближайшим предшествующим инструкцияом if, находящимся с ним в одном блоке и не связанном с другим разделом else.
Слайд 304. Структурное программирование
4.3. Ветвления
Цепочка инструкций if-else
…
int main()
{
…
if (Выражение) инструкция;
else
if (Выражение) инструкция;
else
if (Выражение) инструкция;
…
else инструкция;
…
}
Слайд 314. Структурное программирование
4.3. Ветвления
Цепочка инструкцияов if-else (другой формат записи)
…
int main()
{
…
if (Выражение)
инструкция;
else if (Выражение)
инструкция;
else if (Выражение)
инструкция;
…
else
инструкция;
…
}
Слайд 324. Структурное программирование
4.3. Ветвления
Цепочка инструкцияов if-else
…
int main() //
another more complicated program to guess a magic number
{
…
if (guess == magic)
{
cout << endl << "** Right ** magic " ;
cout << magic << "==" << guess << " (guess}";
}
else if (guess > magic)
cout << “** Wrong ** too high " ;
else
cout << “** Wrong ** too low " ;
}
…
}
Слайд 334. Структурное программирование
4.3. Ветвления
Пример: анализ результатов тестирования
if
(grade >=90) cout << “excellent”;
else
if (grade >=70) cout << “very good”;
else
if (grade >=50) cout << “good”;
else
if (grade >=15) cout << “poor”;
else
cout << “very bad”;
if (grade>=90) cout << “excellent”;
if (grade>=70 && grade<90) cout << “very good”;
if (grade>=50 && grade<70 ) cout << “good”;
if (grade >=15 && grade<50) cout << “poor”;
if (grade<15) cout << “very bad”;
Слайд 344. Структурное программирование
4.3. Ветвления
Демонстрация многовариантности использования if … else
Задача.
Даны три вещественных числа a, b, c. Записать на языке С++ алгоритм нахождения наименьшего из этих чисел
Слайд 354. Структурное программирование
4.3. Ветвления
Демонстрация многовариантности использования if … else
Алгоритм 1 (используем цепочку if –then-else)
if ((a <= b) && (a<=c)) min = a;
else if ((b <= c) && (b<=a)) min = b;
else if ((c<=b) && (c<=a)) min = c;
if ((a<=b) && (a<=c)) min = a;
else if ((b<=c) && (b<=a)) min = b;
else min=c;
if ((a<=b) && (a<=c)) min = a;
else if (b<=c) min = b;
else min = c;
Слайд 364. Структурное программирование
4.3. Ветвления
Демонстрация многовариантности использования if … else
Алгоритм 2 (простой и надежный)
min = a;
if (b < min) min = b;
if (c < min) min = c;
Алгоритм 3 (вложенные if… else)
if (a <= b)
if (a <= c) min = a;
else min = c;
else
if (b <=c ) min = b;
else min = c;
Слайд 374. Структурное программирование
4.3. Ветвления
Демонстрация многовариантности использования if … else
Алгоритм 1 (используем цепочку if –then-else)
if (a<=b) and (a<=c) then min = a;
else if (b<=c) then min = b;
else min = c;
Алгоритм 2 (простой и надежный)
min = a;
if (b < min) min = b;
if (c < min) min = c;
Алгоритм 3 (вложенные if… else)
if (a <= b)
if (a <= c) min = a;
else min = c;
else
if (b <=c ) min = b;
else min = c;
?
Слайд 384. Структурное программирование
4.3. Ветвления
Простейший анализ вычислительной сложности алгоритмов
Слайд 394. Структурное программирование
4.3. Ветвления
Простейший анализ вычислительной сложности алгоритмов
Примерное время выполнения
операций (P-200), 10-9 с:
Слайд 404. Структурное программирование
4.3. Ветвления
int main() // Calculates min value of
a,b,c
{
float a=0, b=0,c=0, min=0;
cout << "Enter a, b, c divided by blanks:";
cin >> a >> b >> c;
if (a <= b)
if (a <= c) min = a;
else min = c;
else
if (b <=c ) min = b;
else min = c;
cout << endl << "The minimum value is " << min;
getch ();
return 0;
}
Результат: законченная программа вычисления min (a,b,c)
Слайд 414. Структурное программирование
4.3. Ветвления
Тернарный условный оператор ?
Выражение1 ?
Выражение2 : Выражение3;
вместо
x = 10;
if (x > 9) y = 100;
else y = 200;
можно
x = 10;
y = x > 9 ? 100 : 200;
[Выражение 1 true]
Вернуть значение Выражения 2
Вернуть значение Выражения 3
[Выражение 1 false]
Слайд 424. Структурное программирование
4.3. Ветвления
Тернарный условный оператор ?
#include
using namespace std;
int main() //Calculates square of float and sets it's sign to the result
{
float a = 0, sqr = 0;
cout << "Enter a:"; cin >> a;
sqr = a < 0 ? -a*a : a*a;
cout << endl << "The result is " << sqr;
getch ();
return 0;
}
Слайд 434. Структурное программирование
4.3. Ветвления
Полученное ранее решение задачи min (a,b,c)
с
помощью if…else
int main() // Calculates min value of a,b,c
{
float a=0, b=0,c=0, min=0;
cout << "Enter a, b, c divided by blanks:";
cin >> a >> b >> c;
if (a <= b)
if (a <= c) min = a;
else min = c;
else if (b <=c ) min = b;
else min = c;
cout << endl << "The minimum value is " << min;
getch ();
return 0;
}
Слайд 444. Структурное программирование
4.3. Ветвления
Решение задачи min (a,b,c) с помощью условного
оператора
int main() // Calculates min value of a,b,c using conditional operator
{
float a=0, b=0,c=0, min=0;
cout << "Enter a, b, c divided by blanks:";
cin >> a >> b >> c;
min = a<=b ? (a<=c ? a : c) : (b<=c ? b : c);
cout << endl << "The minimum value is " << min;
getch ();
return 0;
}
Слайд 454. Структурное программирование
4.3. Ветвления
Вызовы функций из условного оператора
#include
using namespace std;
int f1(int n);
int f2();
int f3 ();
int main() // Demonstrates functions' calls by the conditional operator
{
int t=0;
cout << "Enter a number: "; cin >> t;
// prints proper message:
t ? f1(t) + f2() : f3 (); // int t as boolean, ignore values to be return
getch ();
return 0;
}
Слайд 464. Структурное программирование
4.3. Ветвления
Вызовы функций из тернарного условного оператора
int f1(int n) // first message if non-zero number entered
{
cout << endl << n;
return 0;
}
int f2() // second message if non-zero number entered
{
cout <<" entered.\n";
return 0;
}
int f3() // message if zero entered
{
cout <<"\nZero entered.\n";
return 0;
}
Слайд 474. Структурное программирование
4.3. Ветвления
Инструкция switch
switch (Выражение)
{
case константа1:
последовательность инструкций;
break;
case константа2:
последовательность инструкций;
break;
case константа3:
последовательность инструкций;
break;
.
.
.
default
последовательность инструкций;
[true]
[false]
Действия для 1
break
[true]
[false]
Действия для 2
break
[true]
[false]
Действия для n
break
Default: действия по умолчанию
Слайд 484. Структурное программирование
4.3. Ветвления
Инструкция switch: пример функции «простейшее меню»
void menu()
{
cout <<"1. Check Spelling\n” << "2. Correct Spelling Errors\n” <<"3. Display Errors\n”;
cout <<"Strike Any Other Key to Skip\n” << " Enter your choice: “;
char ch = getchar(); // read the selection from the keyboard
switch (ch) {
case '1':
check_spelling(); break;
case '2':
correct_errors(); break;
case '3':
display_errors(); break;
default :
printf("No option selected");
}
}
Слайд 494. Структурное программирование
4.3. Ветвления
Инструкция switch: опускаем break
// Process a
value of i
void inp_handler(int i)
{
int flag=-1;
switch(i) {
case 1: // These cases have common
case 2: // statement sequences.
case 3:
flag = 0; break;
case 4:
flag = 1;
case 5:
error(flag); break;
default:
process(i);
}
}
Рассмотрим возможные входные значения i
Слайд 504. Структурное программирование
4.3. Ветвления
Инструкция switch: опускаем break
// Process a
value of i
void inp_handler(int i)
{
int flag = -1;
switch(i) {
case 1: // These cases have common
case 2: // statement sequences.
case 3:
flag = 0; break;
case 4:
flag = 1;
case 5:
error(flag); break;
default:
process(i);
}
}
Если i == 1
или i == 2
или i == 3
Слайд 514. Структурное программирование
4.3. Ветвления
Инструкция switch: опускаем break
// Process a
value of i
void inp_handler(int i)
{
int flag = -1;
switch(i) {
case 1: // These cases have common
case 2: // statement sequences.
case 3:
flag = 0; break;
case 4:
flag = 1;
case 5:
error(flag); break; // with flag == 1
default:
process(i);
}
}
Если i == 4
Слайд 524. Структурное программирование
4.3. Ветвления
Инструкция switch: опускаем break
// Process a
value of i
void inp_handler(int i)
{
int flag = -1;
switch(i) {
case 1: // These cases have common
case 2: // statement sequences.
case 3:
flag = 0; break;
case 4:
flag = 1;
case 5:
error(flag); break; // with flag == -1
default:
process(i);
}
}
Если i == 5
Слайд 534. Структурное программирование
4.3. Ветвления
Инструкция switch: опускаем break
// Process a
value of i
void inp_handler(int i)
{
int flag = -1;
switch(i) {
case 1: // These cases have common
case 2: // statement sequences.
case 3:
flag = 0; break;
case 4:
flag = 1;
case 5:
error(flag); break;
default:
process(i);
}
}
Если (i != 1) &
(i !=2) & (i !=3) &
(i !=4) & (i != 5)
Слайд 544. Структурное программирование
4.3. Ветвления
Заменяем switch на if …else
// Process
a value of i
void inp_handler(int i)
{
int flag = -1;
if (i == 1 || i==2 || i==3) flag = 0;
else
{
if (i==4) flag = 1;
if (i==5||i==4) error(flag);
}
if (i<0 || i >5) process (i); // it’s not so easy to simulate the default branch in switch
}
Слайд 554. Структурное программирование
4.4. Повторение
Цикл «пока» или «while»
while (Условие)
инструкция;
while (Условие)
{
инструкция1;
инструкция2;
инструкция3;
…
}
Тело цикла может не исполняться ни разу
Требует инициализации переменных условия до входа в цикл
S
[true]
[false]
Слайд 564. Структурное программирование
4.4. Повторение
Пример цикла while (вывод на экран ASCII
кода клавиши)
#include
using namespace std;
int main() // Waiting for a char and displays it's ASCII code
{
char ch = 0; // inits var that condition contains
while (ch != 27) // while not Esc pressed
{
ch=_getch(); // changes var that condition contains
cout << ch << " = " << ch+0 << endl;
}
return 0;
}
Мелкая шалость: неявное преобразование к int
Слайд 574. Структурное программирование
4.4. Повторение
Пример цикла while: цикл не выполнится ни
разу
#include
using namespace std;
int main() // Waiting for a char and displays it's ASCII code
{
char ch = 27; // inits var ch with 27 and the condition will be false !!!
while (ch != 27) // the body of the cycle can’t be executed
{
ch=_getch(); // changes var that condition contains
cout << ch << " = " << ch+0 << endl;
}
return 0;
}
Слайд 584. Структурное программирование
4.4. Повторение
Пример цикла while: иногда можно и не
инициализировать…
#include
using namespace std;
int main() // Waiting for a char and displays it's ASCII code
{
char ch=27; // or simply char ch;
while ( (ch = getch ()) != 27) // the best way to enter ch
cout << ch << " = " << static_cast (ch) << endl;
return 0;
}
устранили мелкую шалость
В отличие о первой версии значение Esc не выведется
Слайд 594. Структурное программирование
4.4. Повторение
Задача: цикл while + стратегия пошаговой детализации
Постановка задачи
Методом последовательных приближений найти решение уравнения x-cos(x)=0 с заданной точностью r.
Математическая модель .
Перепишем уравнение в виде x=f(x)
Выберем начальное приближение x0
Положим x1=f(x0);
x2=f(x1);
…
xn=f(xn-1)
Погрешность d = |xn-1-f(xn-1)| = |xn-1-xn|
Условие сходимости: |f'(x)|<1
Слайд 604. Структурное программирование
4.4. Повторение
Находим решение уравнения x-cos(x)=0
Слайд 614. Структурное программирование
4.4. Повторение
Задать начальное значение x=x0, точность r
Уточнить решение
методом последовательных приближений
Вывести значение x
Слайд 624. Структурное программирование
4.4. Повторение
Задать начальное значение x=x0, точность r
Уточнение x
[d>r]
[d
Инициализировать текущую погрешность d=2*r
Вывести значение x
Слайд 634. Структурное программирование
4.4. Повторение
Задать начальное значение x=x0, точность r
Вывести значение
x
Вычислить y=cos(x)
[d>r]
[d<=r]
Инициализировать текущую погрешность d=2*r
Положить d=|x-y|
Положить x=y
Слайд 644. Структурное программирование
4.4. Повторение
Алгоритм на псевдокоде
Псевдокод – искусственный неформальный язык,
позволяющий однозначно трактовать описываемые на нем действия.
Данные.
Заданная точность float r
Текущая погрешность float d
Текущее значение xn-1 float x
Текущее значение f(xn-1) float y
Алгоритм.
1. Задать x=x0, r
2. Уточнить решение методом последовательных приближений
3. Вывести значение x
Слайд 654. Структурное программирование
4.4. Повторение
Алгоритм на псевдокоде: уточнение
Данные.
Заданная точность
float r
Текущая погрешность float d
Текущее значение xn-1 float x
Текущее значение f(xn-1) float y
Алгоритм.
1. Задать x=x0, r
2. Инициализировать d
3. Пока d>r выполнять
3.1. Вычислить y = cos(x)
3.2. Положить d = |x-y|
3.3. Положить x = y
4. Вывести значение x
Метод последовательных приближений
Слайд 664. Структурное программирование
4.4. Повторение
Программа на С++: детализируем псевдокод
int main() //
Solves nonlinear equation x=cos (x)
{
float x=0.f, r=1e-6f, y=0.f; //start value of x, precision, value of cos(x)
cout << "Enter start value of x : "; cin >> x;
cout << "Enter required precision : "; cin >> r;
float d = 2*r; //current precision
while (d > r)
{
y = cos(x);
d = abs(x-y);
x = y;
}
cout << "The solution is x = " << x;
_getch();
return 0;
}
1. Задать x=x0, r
2. Инициализировать d
3. Пока d>r выполнить
Данные
3. 1. Вычислить y=cos(x)
3. 2. Положить d = |x-y|
3. 3. Положить x=y
4. Вывести значение x
Слайд 674. Структурное программирование
4.4. Повторение
Программа на С++
int main() // Solves nonlinear
equation x=cos (x)
{
float x=0.f, r=1e-6f, y=0.f; //start value of x, precision, value of cos(x)
cout << "Enter start value of x : "; cin >> x;
cout << "Enter required precision : "; cin >> r;
float d = 2*r; //current precision
while (d > r)
{
y = cos(x);
d = abs(x-y);
x = y;
}
cout << "The solution is x = " << x;
_getch();
return 0;
}
Слайд 684. Структурное программирование
4.4. Повторение
Программа на С++
int main() // Solves nonlinear
equation x=cos (x)
{
float x=0.f, r=1e-6f, y=0.f; //start value of x, precision, value of cos(x)
cout << "Enter start value of x : "; cin >> x;
cout << "Enter required precision : "; cin >> r;
float d = 2*r; //current precision
while (d > r)
{
y = cos(x);
d = abs(x-y);
x = y;
}
cout << "The solution is x = " << x;
_getch();
return 0;
}
Опасность :
если величина r сопоставима с погрешностью чисел float, то цикл никогда не завершится !!!
Слайд 694. Структурное программирование
4.4. Повторение
Сопровождение
int main() // Solves nonlinear equation
x=cos (x)
{
float x=0.f, r=1e-6f, y=0.f; //start value of x, precision, value of cos(x)
cout << "Enter start value of x : "; cin >> x;
cout << "Enter required precision : "; cin >> r;
if (r < 1e-6f) r=1e-6; // elementary input data checking
float d = 2*r; //current precision
while (d > r)
{
y = cos(x);
d = abs(x-y);
x = y;
}
cout << "The solution is x = " << x;
_getch();
return 0;
}
Слайд 704. Структурное программирование
4.2. Базовые управляющие структуры
Повторение (цикл «до тех пор»
или «do while»)
Тело цикла обязательно исполняется хотя бы один раз
Не требует обязательной инициализации переменных условия до входа в цикл
do
инструкция;
while (Условие)
do
{
инструкция1;
инструкция2;
…
}
while (Условие)
S
[true]
[false]
Слайд 714. Структурное программирование
4.4. Повторение
Задача: цикл do while + стратегия пошаговой
детализации
(без изменений)
Постановка задачи
Методом последовательных приближений найти решение уравнения x-cos(x)=0 с заданной точностью r.
Математическая модель .
Перепишем уравнение в виде x=f(x)
Выберем начальное приближение x0
Положим x1=f(x0);
x2=f(x1);
…
xn=f(xn-1)
Погрешность d = |xn-1-f(xn-1)| = |xn-1-xn|
Условие сходимости: |f'(x)|<1
Слайд 724. Структурное программирование
4.4. Повторение
Алгоритм на псевдокоде
(без изменений)
Данные.
Заданная точность
float r
Текущая погрешность float d
Текущее значение xn-1 float x
Текущее значение f(xn-1) float y
Алгоритм.
1. Задать x=x0, r
2. Уточнить решение методом последовательных приближений
3. Вывести значение x
Слайд 734. Структурное программирование
4.4. Повторение
Данные.
Заданная точность
float r
Текущая погрешность float d
Текущее значение xn-1 float x
Текущее значение f(xn-1) float y
Алгоритм.
1. Задать x=x0, r
2. Выполнять :
2.1. Вычислить y = cos(x)
2.2. Положить d = |x-y|
2.3. Положить x = y
пока d>r
4. Вывести значение x
Метод последовательных приближений
Предварительная инициализация d
не нужна !!!
Алгоритм на псевдокоде: уточнение с циклом do-while
Слайд 744. Структурное программирование
4.4. Повторение
Данные.
Заданная точность
float r
Текущая погрешность float d
Текущее значение xn-1 float x
Текущее значение f(xn-1) float y
Алгоритм.
Ввести x=x0
Выполнять : вводить r пока r < 10-6
3. Выполнять
3.1. Вычислить y = cos(x)
3.2. Положить d = |x-y|
3.3. Положить x = y
пока d>r
4. Вывести значение x
Здесь тоже предварительная инициализация r
не обязательна
Алгоритм на псевдокоде:
контроль величины точности с циклом do-while
Слайд 754. Структурное программирование
4.4. Повторение
Программа на С++
int main() // Solves nonlinear
equation x=cos (x)
{
float x=0.f, r=1e-6f, y=0.f, d=1.f;
cout << "Enter start value of x : "; cin >> x;
do
{ cout << "Enter required precision (not less than 1e-6): "; cin >> r; }
while (r < 1e-6f);
do
{
y = cos(x);
d=abs(x-y); x = y;
}
while (d > r);
cout << "The solution is x = " << x;
_getch();
return 0;
}
Слайд 764. Структурное программирование
4.4. Повторение
Задача:
нахождение суммы конечного числа членов ряда
Постановка
задачи.
Найти значение суммы первых 10 членов ряда
Слайд 774. Структурное программирование
4.4. Повторение
Алгоритм на псевдокоде
Данные.
Заданное число членов ряда
unsigned short n
Сумма ряда float s
Счетчик unsigned short i
Алгоритм.
Задать число суммируемых членов n
Положить s = 0
Положить значение счетчика i = 0
Пока i <= n выполнять
4.1 s = s + 1/2i
4.2 увеличить значение счетчика i = i+1
3. Вывести значение s
Слайд 784. Структурное программирование
4.4. Повторение
Программа на С++
int main()
{
const
unsigned short n=5; //number of terms
float s = 0.f;
unsigned short i = 0;
while (i <= n)
{
s=s+1.0/ pow(2.0,i); //pow calculates double raised to integer (math.h)
i++;
}
cout << "The sum is equal to " << s;
_getch();
return 0;
}
Слайд 794. Структурное программирование
4.4. Повторение
Программа на С++
int main()
{
const
unsigned short n=5; //number of terms
float s = 0.f;
unsigned short i = 0; // initialization
while (i <= n) // condition
{
s=s+1.0/ pow(2.0,i); //pow calculates double raised to integer (math.h)
i++; // increment
}
cout << "The sum is equal to " << s;
_getch();
return 0;
}
Слайд 804. Структурное программирование
4.4. Повторение
Алгоритм на псевдокоде
Данные.
Заданное число членов ряда
unsigned short n
Сумма ряда float s
Счетчик unsigned short i
Алгоритм.
Задать число суммируемых членов n
Положить s = 0
Положить значение счетчика i = 0 (Инициализация)
Пока i <= n выполнять (Условие)
4.1 s = s + 1/2i
4.2 увеличить значение счетчика i = i+1 (Приращение)
3. Вывести значение s
Слайд 814. Структурное программирование
4.4. Повторение
Цикл со счетчиком
for (Инициализация; Условие; Приращение)
инструкция;
for (Инициализация; Условие; Приращение)
{
инструкция1;
инструкция2;
…
}
S
[true]
[false]
Прира-щение
Инициализация
Тело цикла может не исполняться ни разу
Инициализация переменных условия обычно выполняется в заголовке цикла
Не следует изменять переменные условия в теле цикла
Слайд 824. Структурное программирование
4.4. Повторение
Алгоритм на псевдокоде
Данные.
Заданное число членов ряда
unsigned short n
Сумма ряда float s
Счетчик unsigned short i
Алгоритм.
Задать число суммируемых членов n
Положить s = 0
Для всех i от 0 до n выполнять
3.1 s = s + 1/2i
4. Вывести значение s
Слайд 834. Структурное программирование
4.4. Повторение
Программа на С++
int main()
{
const
unsigned short n=10; //number of terms
float s = 0.f;
for (unsigned short i=0; i <= n; i++) // it’s a good style to declare i here
s = s + 1.0 / pow(2.0,i); // i is visible and lives only into the loop body
cout << "The sum is equal to " << s;
_getch();
return 0;
}
Слайд 844. Структурное программирование
4.4. Повторение
Программа на С++
int main()
{
const
unsigned short n=10; //number of terms
float s = 0.f;
for (unsigned short i=0; i <= n; i++)
s += 1.0 / pow(2.0,i); // it’s the c-style
cout << "The sum is equal to " << s;
_getch();
return 0;
}
Время выполнения – 10,4 микросекунды
Слайд 854. Структурное программирование
4.4. Повторение
Оптимизация программы на С++
int main()
{
const unsigned short n=10; //number of terms
float s = 0.f;
unsigned int p=1; // we will optimize calculations into the loop body
for (unsigned short i=0 ; i <= n; i++)
{
s += 1.0 / p; p <<= 1; // p=p*2
}
cout << "The sum is equal to " << s;
_getch();
return 0;
}
Время выполнения – 7,2 микросекунды
Слайд 864. Структурное программирование
4.4. Повторение
Задача построения таблицы функции вещественного аргумента
Постановка
задачи.
Построить таблицу функции y=sin(x),
аргумент x изменяется от 0 до 1 с шагом 0.1
Слайд 874. Структурное программирование
4.4. Повторение
Алгоритм на псевдокоде
(если бы счетчик мог
быть только целым)
Данные.
Число рассчитываемых значений +1 unsigned short n
Текущее значение аргумента double x
Текущее значение функции double y
Приращение аргумента double delta
Счетчик unsigned short i
Алгоритм.
Задать число значений n и приращение delta
Напечатать шапку таблицы
3. Для всех i от 0 до n выполнять
3.1 Положить x = delta*i
3.2 Вычислить y = sin(x)
3.3 Вывести значения x и y
Слайд 884. Структурное программирование
4.4. Повторение
Программа на С++
int main()
{
const
unsigned short n=10; //number of terms
const double delta = 0.1f;
cout <<" x y" << endl;
cout <<"-----------------------" << endl;
for (unsigned short i=0 ; i <= n; i++)
{
double x = delta * i; //we don't need x and y outside the body
double y = sin (x);
cout << setw(8) << x << setw(15) << y << endl;
}
_getch();
return 0;
}
Слайд 894. Структурное программирование
4.4. Повторение
Модификация программы на С++ (руки оторвать!!!)
int
main()
{
const unsigned short n=10; //number of terms
const double delta = 0.1;
cout <<" x y" << endl;
cout <<"-----------------------" << endl;
for (unsigned short i= -1 ; i++-n; ) // an idiot only can write such code
{
double x = delta * i;
double y = sin (x);
cout << setw(8) << x << setw(15) << y << endl;
}
_getch();
return 0;
}
Слайд 904. Структурное программирование
4.4. Повторение
Алгоритм на псевдокоде
(в С++ счетчик может
быть не только целым)
Данные.
Начальное значение аргумента double x_beg
Конечное значение аргумента double x_end
Текущее значение аргумента double x
Текущее значение функции double y
Приращение аргумента double delta
Алгоритм.
Задать x_beg, x_end и delta
Напечатать шапку таблицы
3. Для всех x от x_beg до x_end с шагом delta выполнять
3.1 Вычислить y = sin(x)
3.2 Вывести значения x и y
Слайд 914. Структурное программирование
4.4. Повторение
Модификация программы на С++ (бесконечный цикл
!!!)
int main()
{
const double x_beg = 0, x_end = 1, delta = 0.1;
cout <<" x y" << endl;
cout <<"-----------------------" << endl;
for (double x = x_beg ; x==x_end; x += delta )
{
double y = sin (x);
cout << setw(8) << x << setw(15) << y << endl;
}
_getch();
return 0;
}
Слайд 924. Структурное программирование
4.4. Повторение
Модификация программы на С++
int main()
{
const double x_beg = 0, x_end = 1, delta = 0.1;
cout <<" x y" << endl;
cout <<"-----------------------" << endl;
for (double x = x_beg ; x<=x_end+1e-10; x += delta ) // prec. is 1e-14
{
double y = sin (x);
cout << setw(8) << x << setw(15) << y << endl;
}
_getch();
return 0;
}
Слайд 934. Структурное программирование
4.4. Повторение
Цикл for с двумя счетчиками
int main()
// Using multiple counters to show powers of 2
{
int i = 0, power = 0;
const int max = 10;
for(i = 0, power = 1; i <= max; i++, power += power)
cout << endl << setw(10) << i << setw(10) << power;
cout << endl;
return 0;
}
0 1
1 2
2 4
3 8
4 16
5 32
6 64
7 128
8 256
9 512
10 1024
Операция последовательного вычисления «запятая» может применяться в разделах инициализации и вычисления приращения. Ее применение в разделе условия бессмысленно (возвращается в качестве условия последнее значение)
Слайд 944. Структурное программирование
4.4. Повторение
Циклы for без тела
int main() // Solves
equation x=cos(x) : real perversion
{
float x =1; cout << "Enter start value of x : "; cin >> x;
for (float d=1, r=1e-5f, y=0 ; d>r ; y=cos(x), d=abs(y-x), x=y);
cout << x;
_getch();
return 0;
}
…
for (unsigned int i=0; i < 2000000; i++); // time delay for 200000 loops
…
for (unsigned int t_beg=time(NULL); time(NULL) - t_beg != 10; );
// time delay for 10 sec. Perversion? May be…
…
for ( ; ; ); //endless loop
Слайд 954. Структурное программирование
4.4. Повторение
Сравнение циклов
while (Условие)
инструкция;
do
инструкция;
while (Условие);
for (Иниц-я; Условие; Приращ-ие)
инструкция;
Слайд 964. Структурное программирование
4.4. Повторение
Сравнение циклов
while (Условие)
инструкция;
do
инструкция;
while (Условие)
for (Иниц-я; Условие; Приращ-ие)
инструкция;
Слайд 974. Структурное программирование
4.4. Повторение
Сравнение циклов
while (Условие)
инструкция;
do
инструкция;
while (Условие)
for (Иниц-я; Условие; Приращ-ие)
инструкция;
Слайд 984. Структурное программирование
4.4. Повторение
Оператор break
инструкция заголовка цикла
{
инструкция1;
инструкция2;
break;
инструкция3;
инструкция4;
…
}
инструкция, следующая за циклом
Слайд 994. Структурное программирование
4.4. Повторение
Оператор break: стандартный прием использования
инструкция
заголовка цикла
{
инструкция1;
инструкция2;
if (Условие_досрочного_выхода) break;
инструкция3;
инструкция4;
…
}
инструкция, следующая за циклом
true
Слайд 1004. Структурное программирование
4.4. Повторение
Пример, где нужен оператор break
// calculates 1./x
while x != 0
int main()
{
float x=1.f;
while (x != 0)
{
cin >> x;
cout << endl << x << " " << 1.0 / x; //division on zero when x == 0
}
return 0;
}
Слайд 1014. Структурное программирование
4.4. Повторение
Пример использования оператора break
// calculates 1./x while
x != 0
int main()
{
float x=0.; // the initialization is not required
while (true) // endless loop. Alternative is for ( ; ;);
{
cin >> x; if (x == 0) break;
cout << endl << x << " " << 1.0 / x;
}
return 0;
}
Слайд 1024. Структурное программирование
4.4. Повторение
Оператор continue
инструкция while или for
{
инструкция1;
инструкция2;
continue;
инструкция3;
инструкция4;
…
}
инструкция do
{
инструкция1;
инструкция2;
continue;
инструкция3;
инструкция4;
…
}
while (Условие_цикла) ;
Слайд 1034. Структурное программирование
4.4. Повторение
Оператор continue: стандартный прием использования
Инструкция while или for
{
инструкция1;
инструкция2;
if (Условие_перехода) continue;
инструкция3;
инструкция4;
…
}
инструкция do
{
инструкция1;
инструкция2;
if (Условие_перехода) continue;
инструкция3;
инструкция4;
…
}
while (Условие_цикла) ;
true
true
Слайд 1044. Структурное программирование
4.4. Повторение
Пример, где нужен инструкция continue
// calculates product
of non-negative x excepting 0. Finish if x<0
int main()
{
float x=0.f, p=1.f;
do
{
cin >> x;
if (x == 0) continue;
if (x < 0) break;
p *= x;
}
while (true);
cout << endl << p;
_getch();
return 0;
}
Слайд 1054. Структурное программирование
4.4. Повторение
Как обойтись без continue
инструкция while
или for
{
инструкция1;
инструкция2;
if (!Условие_перехода)
{
инструкция3;
инструкция4;
…
}
}
инструкция do
{
инструкция1;
инструкция2;
if (!Условие_перехода)
{
инструкция3;
инструкция4;
…
}
}
while (Условие_цикла) ;
true
true
Слайд 1064. Структурное программирование
4.4. Повторение
Как обойтись без break
while (Условие_цикла
&& !Условие_досрочного_выхода)
{
инструкция1;
инструкция2;
if (!Условие_досрочного_выхода)
{
инструкция3;
инструкция4;
…
}
}
инструкция, следующая за циклом
true
Слайд 1074. Структурное программирование
4.4. Повторение
Как обойтись без break
for (…;
Условие_цикла && !Условие_досрочного_выхода ; … )
{
инструкция1;
инструкция2;
if (!Условие_досрочного_выхода)
{
инструкция3;
инструкция4;
…
}
}
инструкция, следующий за циклом
true
Слайд 1084. Структурное программирование
4.4. Повторение
Как обойтись без break
do
{
инструкция1;
инструкция2;
if (!Условие_досрочного_выхода)
{
инструкция3;
инструкция4;
…
}
}
while (Условие_цикла && !Условие_досрочного_выхода);
инструкция, следующая за циклом
true