Элементы ЯПВУ С / C++Pascal Потоковый (неформатный) ввод / вывод Одной из важнейших компонент языка программирования С++ является потоковый ввод-вывод. Поток – в языке С++ понятие относящееся к любому переносу данных от источника к приемнику. Потоковые операции рассматривают все передаваемые данные как поток байтов, без какой-либо структуры. Входной поток – байты из потока поступают (извлекаются >>) в переменные. sin – объект, извлекающий байты из входного потока и помещающий их в указанные переменные (входной поток по умолчанию связан с буфером клавиатуры). Выходной поток – байты в поток поступают (помещаются, включаются <<) из переменных. сout – объект, помещающий байты из указанных переменных в выходной поток (выходной поток по умолчанию связан с экраном дисплея). 1 Система ввода-вывода С++, как объектно-ориентированного языка программирования (ООП), основана не на библиотеке функций, а на библиотеке классов. Одним из базовых принципов ООП является предположение о том, что объекты "знают", что нужно делать при появлении обращения (сообщения) определенного типа, т.е. для каждого типа адресованного ему обращения объект имеет соответствующий механизм обработки. Объект cout, представляющий выходной поток, выбирает соответствующую процедуру обработки и выводит значение в соответствующем виде. Объект cout не может перепутать и вывести, например, целое число в формате с плавающей точкой. Для использования cin и cout надо подключать библиотеку и файлам исходного текста давать расширение.cpp ВМП

Элементы ЯПВУ С / C++Pascal Потоковый (неформатный) ввод / вывод cout << элемент_1 << элемент_2 <<…<< элемент_n; где - cout - вывод данных (на экран), - элемент_n может быть - переменная; - числовая константа; - выражение (в круглых скобках); - строковая константа ( в двойных кавычках, в том числе \n – перевод строки ); - ключевое слово endl - перевод строки. Пример: cout << RL << " – это флаг истинности правила. \n"; cout << " S = " << pow (a+b, 1.0/3); // Кубический корень из a+b sin >> элемент_1>> элемент_2 >>…>> элемент_n; где - cin - ввод данных (с клавиатуры), - элемент_n - переменная (но не выражение и не константа). Пример: int S; char kl; cin >> S >> kl; // тип вводимых данных определяется автоматически 2 в С++ сохраняется возможность использовать printf и scanf ВМП

Рекурсия и рекуррентность Рекурсия от латинского слова "recursio" – возвращение. Если программа обращается сама к себе как к подпрограмме непосредственно или через цепочку подпрограмм, то это называется рекурсией. Если подпрограмма р содержит явное обращение к самой себе, то она называется явно рекурсивной. Если подпрограмма р содержит обращение к некоторой подпрограмме q, которая в свою очередь содержит прямое или косвенное обращение к р, то р - называется косвенно рекурсивной. Рекуррентность это способ вычисления функции. Рекуррентный алгоритм задает способ вычисления членов последовательности описывающей функцию при помощи рекуррентных формул. Следующий член последовательности вычисляют как функцию от предыдущего: x k = f(x k-1 ), где x 0 = a. Возможен более сложный случай, когда очередной член последовательности зависит от 2-х предыдущих: x k = f(x k-1, x k-2 ), где x 0 =a, x 1 = b. терминальное условие Рекурсивная программа должна обязательно иметь так называемое терминальное условие, то есть условие при котором программа прекращает рекурсивный процесс, иначе она никогда не остановится. 3 ВМП

Рекурсия 4 Пример рекурсивного алгоритма – вычисление суммы K членов ряда арифметической прогрессии: /* Вычисление суммы K членов ряда арифметической прогрессии K - количество суммируемых членов ряда, N-шаг прогрессии, FS - значение первого члена ряда */ int SUMpr(int K, int FS, int N) /* рекурсивная функция вычисления суммы членов ряда */ { if(K==1) return FS; return FS+(K-1)*N+SUMpr(K-1,FS,N); // рекурсивное выражение } void main() { int n,arg,ras; printf ("Введите количество суммируемых членов ряда n = "); scanf ("%d",n); printf ("\n Введите значение первого члена ряда arg = "); scanf ("%d", arg); printf ("\n Введите шаг прогрессии ras = "); scanf ("%d", ras); printf ("\n Сумма членов ряда = \n", SUMpr(n,arg,ras)); getch(); } ВМП

Рекуррентность При программировании рекуррентного алгоритма организуют цикл, вычисляющий значение очередного члена последовательности x k = f(x k-1 ) : y = a Инициализация – вычисление значения первого члена последовательности перед запуском цикла и присваивание его переменной y if_end false true условие прекращения цикла x = y y = f(x) смещение очередного члена последовательности вычисление очередного члена последовательности Примеры рекуррентных соотношений – это факториал, числа Фибоначчи, алгоритм Евклида и др. Программы вычисления этих соотношений могут быть реализованы как рекурсивным, так и итерационным способом (в цикле). 5 Пример рекуррентного алгоритма: вычисление значения очередного члена последовательности ряда натуральных чисел : X n = X n ВМП

CPascal Практическое занятие Вычислить число с заданной пользователем точностью: Program CyclePi; Var p,t,elem:real;{ значение ПИ, точность, значен.члена ряда } n : integer; { номер члена ряда } Begin p := 0; n := 1; elem := 1; Write ( 'Задайте точность вычисления ПИ -> '); Read (t); Writeln ( 'Вычисление ПИ с точностью ', t:9:6,':'); while elem >= t do begin elem := 1/(2*n-1); if (n mod 2) = 0 then p := p - elem else p := p + elem; n := n+1; end; p := p*4; WriteLn( 'Значение ПИ с точностью ',t:9:6, ' равно ', p:9:6,'.'); WriteLn (' Просуммировано ', n, ' члена(ов) ряда. '); End. #include void main() { float p, t, el; // значение ПИ, точность, значение члена ряда int n; // номер члена ряда p = 0; n = 1; el = 1; // начальное значение члена ряда printf ("\ n Задайте точность вычисления Пи -> "); scanf ("%f", &t); printf(" Вычисление Пи с точностью %f\n", t); while (el >= t) { el = (float) 1 / (2*n-1); if ((n % 2) == 0) p -= el; else p += el; n++; } p = p*4; printf("\n Значение ПИ с точностью %f равно %f. \n", t, p); printf ("\n Просуммировано %i члена(ов) ряда. \n", n); getch(); } Для вычисления используем факт, что значение частичной суммы ряда 1 – 1 / / / / / 11 …. при суммировании достаточно большого количества членов приближается к / 4. На экране должно быть:Задайте точность вычисления ПИ -> Вычисление ПИ с точностью : Значение числа ПИ с точностью равно Просуммировано 502 член(а)(ов) ряда. 6Рекуррентность ВМП

Основные понятия и утверждения целочисленной арифметики Определение 1. Целое число a делится на целое число b (b 0), если существует такое целое число k, что a=k b. В таком случае b называют делителем числа a; a называют кратным числа b. Утверждение 1. Если числа a и b делятся на c, то и их сумма (a+b), и их разность (а-b) делятся на c. Утверждение 2. Если a делится на c, а b делится на d, то их произведение a * b делится на c * d. Определение 2. Пусть a и b – положительные целые числа, c - общий делитель чисел a и b, если a делится на c и b делится на c. Среди общих делителей чисел a и b (не равных одновременно нулю) есть наибольший общий делитель, обозначаемый НОД(a, b). Утверждение 3. Если a делится на b, то НОД(a, b) = b. Утверждение 4. НОД(a, a) = a. Утверждение 5. Если a > b, то НОД(a, b) = НОД(a b, b). Определение 3. Если НОД(a, b) = 1, то числа a и b называются взаимно простыми. Утверждение 6. Существует целое q, что a = b * q + r, где остаток от деления r – целое число, удовлетворяющее неравенству 0 r < b, при этом, НОД(a, b) = НОД(r, b). Целочисленные алгоритмы 7 ВМП

Алгоритм Евклида (1) Основываясь на утверждение 5 целочисленной арифметики: если a > b, то НОД(a, b) = НОД(a b, b),- составим простейший алгоритм нахождения НОД: 1. задать два числа; 2. если числа равны, то взять любое из них в качестве ответа и остановиться; 3. в противном случае продолжить выполнение алгоритма; 4. определить большее из чисел; 5. заменить большее из чисел разностью большего и меньшего из чисел; 6. повторить алгоритм с шага 2. Алгоритм Евклида – это метод нахождения наибольшего общего делителя (НОД) двух чисел. Первая модификация алгоритма Евклида 8 A=A-BA=A-B ТО ИНАЧЕ Вход Получить A и B Выход НОД=A=B Л И B=B-AB=B-A ЕСЛИ A > B ЕСЛИ ВСЁ ПОКА ВСЁ ПОКА A <> B ВМП

Алгоритм Евклида 9 C/C++ Написать на С/C++ программу определения НОД Первая модификация алгоритма Евклида // #include #include void main() { clrscr(); int a, ai, b, bi; // а и b – числа, для поиска НОД int nod; // nod – наибольший общий делитель cout<<"Введите 2-а целых положительных числа для определения НОД"); cout > a; a = ai; cout > b; b = bi; while (ai != bi) { if ((ai > ib) аi -= bi; else bi -= ai; } nod = ai; cout << "\ n Значение НОД(<<a<<","<<b<<") равно \n" << nod; getch(); } A=A-BA=A-B ТО ИНАЧЕ Вход Получить A и B Выход НОД=A=B Л И B=B-AB=B-A ЕСЛИ A > B ЕСЛИ ВСЁ ПОКА ВСЁ ПОКА A <> B ВМП

Алгоритм Евклида (2) Вторая модификация алгоритма Евклида Она основана на утверждении 6 целочисленной арифметики: существует такое целое q, что a = b * q + r, где остаток от деления r – целое число, удовлетворяющее неравенству 0 r < b, при этом, НОД(a, b) = НОД(r, b). Следовательно, НОД двух чисел – это последний не равный нулю остаток от деления большего числа на меньшее. Алгоритм имеет вид: 1. задать два числа; 2. проверить в цикле условия А=0 и A=B; 3. если равно, то НОД=B; 4. иначе, определить большее из чисел; 5. если A>B, то заменить А остатком от деления A на B; 6. если A<B, то взаимно заменить значения A и B; 7. выполнить шаг 5; 8. повторить алгоритм с шага ВМП

Алгоритм Евклида (2) Вторая модификация алгоритма Евклида Program NOD_2; uses Crt; Var x, xi, y, yi: Integer; nod : integer; { НОД } Begin Clrscr; Writeln('Введите два целых положительных числа'); Readln(x,y); { вводим два целых числа } xi := x; yi := y; while (xi<>0) and (yi<>0) do { до тех пор, пока одно из чисел не станет равно нулю } if xi>yi then xi := xi mod yi else yi := yi mod xi; if xi=0 then NOD:= yi else NOD:= xi; Writeln('НОД(',x,','y') = ', NOD); Readln; End. 11 Написать на Pascal программу определения НОД Нарисовать блок-схему определения НОД Pascal Выход A=A%BA=A%B ТО ИНАЧЕ Вход Получить A и B НОД= B Л И B=B%AB=B%A ЕСЛИ A > B ЕСЛИ ВСЁ ПОКА ВСЁ НОД = A ЕСЛИ A = 0 ТО ИНАЧЕ ЕСЛИ ВСЁ ПОКА A<>0 И B<>0 ВМП

Рекуррентные алгоритмы Это последовательность, в которой каждый следующий член равен сумме двух предыдущих, при этом первые два члена равны 1. Получаем ряд 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,..., который описывается рекуррентным соотношением F n = F n-1 + F n-2, при F 1 =F 2 =1. Числа Фибоначчи Суммирование последовательностей Формула для вычисления суммы n членов последовательности a 1,a 2,...,a n имеет вид: S n = S n-1 + a n, где S 1 = a 1. Произведение членов последовательностей Формула для вычисления произведения n членов последовательности a 1,a 2,...,a n имеет вид: P n = P n-1 * a n, где P 0 = Вычисление корня квадратного Рекуррентная формула вычисления выглядит так: X k+1 = ½ (X k + a / X k ), где X 0 =a. Цикл вычисления завершаем, когда разность между двумя соседними членами последовательности становится меньше заданной константы (определяющей точность вычисления) ВМП