Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Дисциплины "ЯЗЫКИ ПРОГРАММИРОВАНИЯ" "ПРОГРАММИРОВАНИЕ" Управление потоком команд

План лекции © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 1.Инструкции перехода. 2.Ветвление 3.Цикл

Инструкции перехода (x86) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 3

Безусловный переход © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 4 0x1000instr #1 0x1004instr #2 0x1008instr #3 0x100cintsr #4 0x1010jmp 0x1024 0x1014instr #7 0x1018instr #8 0x101cinstr #9 0x1020instr #10 0x1024instr #11 0x1028instr #12 0x102cinstr #13 Существует несколько команд безусловного перехода. 1.CALL – вызов процедуры. 2.RET – возврат из процедуры. 3.INT – вызов программного прерывания. 4.JMP – переход (прыжок) к указанному адресу.

Условный переход © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 5 0x1000instr #1 0x1004instr #2 0x1008cmp %eax %ebx Сравнить значения регистров 0x100сjle 0x1018 Если %eax < %ebx перейти 0x1010instr #3 0x1014instr #4 0x1018instr #5 0x101сinstr #6 Команда процессору на изменение порядка выполнения программы в соответствии с результатом проверки некоторого условия.

Команды условного перехода © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 6 JA(Jump if Above ) переход, если X > Y JB(Jump if below) переход, если X < Y JBE(Jump if Below or Equal ) переход, если X Y JAE(Jump if Above or Equal) переход, если X Y JE(Jump if equal) переход X = Y cmp X Y Обычно имеет две стадии. 1. Сравнение некоторых величин (X и Y), от которых зависит дальнейшее выполнение программы. 2. Непосредственно выполнение перехода (инструкции для сравнения беззнаковых целых).

Ветвление © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 7 x > y y = x x = y ДАНЕТ Ветвление – управляющая структура, организующая выполнение лишь одного из двух указанных действий в зависимости от справедливости некоторого условия. Условие – высказывание, которое может быть истинно (ветвь ДА) или ложно (ветвь НЕТ). Запись ветвления выполняется в двух формах: полной (слева) и неполной (справа). x > y y = x ДАНЕТ

Ветвления © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 8

Реализация ветвления на языке ассемблера © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 9 main:... movl $15, -4(%ebp) // x = 15 movl $10, -8(%ebp) // y = 10 movl -4(%ebp), %eax // eax = x cmpl -8(%ebp), %eax // x - y jle.L2// x < y movl -8(%ebp), %eax movl %eax, -4(%ebp) jmp.L5.L2: movl -4(%ebp), %eax movl %eax, -8(%ebp).L5:... НЕТ ДА x > y y = x x = y ДАНЕТ

Оператор ветвления СИ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 10 УсловныйОператор = "if" "(" Выражение ")" Оператор1 [ else Оператор2 ]. if( x > y ){ y = x; }else{ x = y; } x > y y = x x = y ДАНЕТ

Оператор ветвления СИ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 11 УсловныйОператор = "if" "(" Выражение ")" Оператор1 [ else Оператор2 ].... if( x > y ){ y = x; }... Части синтаксических конструкций, не обязательные для использования, указываются в квадратных случаях. В данном случае неполная версия ветвления не требует ветви "else". Части синтаксических конструкций, не обязательные для использования, указываются в квадратных случаях. В данном случае неполная версия ветвления не требует ветви "else". x > y y = x ДАНЕТ

Составной оператор СИ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» if( x > y ){ int t; t = x; x = y; y = t; }... Табуляция x > y t = x x = y y = t t = x x = y y = t ДАНЕТ Операторы ветвления в языке СИ предусматривают наличие только одного оператора. Для того, чтобы выполнить несколько операторов в рамках некоторой ветви необходимо заключить их в фигурные скобки. В результате оператор ветвления будет работать с одним сложным (составным) оператором, содержащим группу более простых.

Составной оператор СИ (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 13 Отсутствие фигурных скобок приведет к неправильной интерпретации алгоритма компилятором. Например:... if( x > y ) t = x; x = y; y = t;... x > y t = x ДАНЕТ x = y y = t x = y y = t

Условие © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 14 В качестве условия в конструкции ветвления обычно применяются логические выражения. Задача: На вход подается выручка (x и y) двух филиалов предприятия с точностью до тысяч рублей (два целых числа). Требуется, взяв за 100% выручку первого филиала, определить, является ли прибыль сбалансированной: относительная прибыль p второго филиала удовлетворяет условию: 80% < p < 120%. Например: 1. Входные данные: , ответ: нет 2. Входные данные: , ответ: да if( ((100*y)/x > 80) && ((100*y)/x < 120) ) printf("Да\n"); else printf("Нет\n");

Особенности вычисления логических выражений (логическое И) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 15 f (x) И g(y) Стратегии вычисления результата данного выражения: 1.Полное вычисление (Visual Basic): вычислить f(x), g(y), произвести сравнение результатов с нулём, затем выполнить операцию «И» для результатов. 2.Неполное вычисление (Си, С++, Java, JavaScript, Python): вычислить f(x) и сравнить результат с нулём. Если результат сравнения – «истина», то вычислить g(y). В противном случае пропустить вычисление g(y), так как для операции «И» остальные аргументы уже не играют роли. xy xy

Особенности вычисления логических выражений (логическое ИЛИ) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 16 f (x) ИЛИ g(y) Стратегии вычисления результата данного выражения: 1.Полное вычисление (Visual Basic): вычислить f(x), g(y), произвести сравнение результатов с нулём, затем выполнить операцию «ИЛИ» для результатов. 2.Неполное вычисление (Си, С++, Java, JavaScript, Python): вычислить f(x) и сравнить результат с нулём. Если результат сравнения – «ложь», то вычислить g(y). В противном случае пропустить вычисление g(y), так как для операции «ИЛИ» остальные аргументы уже не играют роли. xy xy

Особенности вычисления логических выражений © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 17 При вычислении более сложных выражений операции выполняются согласно приоритетам и ассоциативности: 1. f (a) И g(b) И h(c) И k(d) = f (a) И [ g(b) И { h(c) И k(d) } ] 2. f (a) И g(b) И h(c) ИЛИ k(d) = [f (a) И { g(b) И h(c) } ] ИЛИ k(d) 3. f (a) ИЛИ g(b) И h(c) И k(d) = f (a) ИЛИ [{ g(b) И h(c) } И k(d)] Неполное вычисление является наиболее распространённым вариантом в промышленных языках (Алгола, Фортрана, С++, С, Java, JavaScript, ECMAScript, JScript, C#, Python). В этих языках действует жёсткое правило: «Логическое выражение всегда вычисляется слева направо и его вычисление останавливается сразу же, как только результат всего выражения становится определённым».

Особенности вычисления логических выражений СИ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 18 Задача: На вход подается выручка двух филиалов предприятия с точностью до тысяч рублей (два целых числа). Требуется, взяв за 100% выручку первого филиала, определить, является ли прибыль сбалансированной: относительная прибыль p второго филиала удовлетворяет условию: 80% < p < 120%. Необходимо учитывать некорректные входные данные: if( y > 0 && (100*x)/y > 80) && ((100*x)/y < 120) ) printf("Да\n"); else printf("Нет\n");

Вложенность ветвлений © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 19 Существуют ситуации, в которых существует не два а более вариантов исполнения программы. Например: 1)квадратное уравнение может иметь 0, 1 или 2 корня; 2)прямые могут совпадать (бесконечное количество общих точек), пересекаться (одна общая точка) или быть параллельны (нет общих точек). Для описания таких ситуаций конструкции ветвления вкладываются друг в друга: if( D < 0 ) printf("Нет корней\n"); else{ if( D == 0 ) printf("Один корень\n"); else printf("Два корня\n"); }

Вложенность ветвлений (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 20 if( D < 0 ) printf("Нет корней\n"); else{ if( D == 0 ) printf("Один корень\n"); else printf("Два корня\n"); } D < 0 ДАНЕТ 0 0 D = 0 ДАНЕТ

Вложенность ветвлений (3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 21 if( D < 0 ) printf("Нет корней\n"); else if( D == 0 ) printf("Один корень\n"); else printf("Два корня\n"); УсловныйОператор = "if" "(" Выражение ")" Оператор1 [ else Оператор2 ]. if( D < 0 ) printf("Нет корней\n"); else{ if( D == 0 ) printf("Один корень\n"); else printf("Два корня\n"); }

Вложенность ветвлений (форматирование исходного кода) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 22 if( D < 0 ) printf("Нет корней\n"); else{ if( D == 0 ) printf("Один корень\n"); else printf("Два корня\n"); } if( D < 0 ) printf("Нет корней\n"); else{ if( D == 0 ) printf("Один корень\n"); else printf("Два корня\n"); } Правильное форматирование Отсутствиее форматирование

Циклы © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 23

Условный переход в обратном направлении © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 24 Операция условного перехода не накладывает никаких ограничений на его направление. То есть переход может осуществляться как в прямом направлении (конструкция ветвления), так и в обратном (на инструкцию, имеющую меньший адрес). 0x1000instr #1 0x1004jmp 0x1014 Пропуск тела для проверки 0x1008instr #2 Тело цикла 0x100сinstr #3 0x1010instr #4 0x1014cmp %eax %ebx Вычисление условия 0x1018jle 0x1008 Продолжение/выход 0x101cinstr #5 Инструкция после цикла

Циклическая конструкция СИ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 25 Цикл – разновидность управляющей конструкции в высокоуровневых языках программирования. Предназначена для организации многократного исполнения набора инструкций. Циклом может называться любая многократно исполняемая последовательность инструкций, организованная любым способом (например, с помощью условного перехода). i < 20 ДА НЕТ i = 0 i = i + 1 В языке Си предусмотрено 3 циклических конструкции, которые являются взаимозаменяемыми: 1) с предусловием – while, for; 2) с постусловием – do-while.

Циклический оператор while © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 26 JLE(Jump if Less than or Equal ) переход, если X Y movl $0, -4(%ebp) jmp.L2.L3: addl $1, -4(%ebp).L2: cmpl $19, -4(%ebp) jle.L3 #include int main() { int i = 0; while( i < 20 ){ i++; } return 0; } "while" "(" Условие ")" Оператор. Условие Оператор НЕТ ДА

Цикл: основные понятия © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 27 Условие ДА НЕТ Инициализация Тело цикла Предварительная инициализация переменных, в частности установка переменной-счетчика. Условие продолжение цикла. Тело цикла выполняется до тех пор, пока условие истинно. Условие продолжение цикла. Тело цикла выполняется до тех пор, пока условие истинно. Тело цикла, содержащее "полезные" инструкции, которые необходимо выполнить несколько раз.

Цикл: основные понятия (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 28 Счетчик цикла – термин, используемый для обозначения переменной, контролирующей повторы выполнения циклов. Счетчики циклов изменяют свое значение при каждом прохождении цикла, подставляя уникальное значение для каждой отдельной итерации. Счетчик цикла также используется для определения момента, когда цикл должен завершить свою работу, после чего программа продолжает свое выполнение, обратившись к инструкции, расположенной после цикла. Обычно счетчики называют i, j и k. i < 20 ДА НЕТ i = 0 i = i + 1 Итерация цикла – однократное выполнение тела цикла.

Применение циклов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 29 Циклические конструкции позволяют автоматизировать объемные вычисления, требующие многократного повторения однотипных действий над различными данными. Для того, чтобы записать цикл, позволяющий решить поставленную задачу необходимо: 1) выделить повторяющиеся операции и определить набор S переменных, которые должны изменяться на каждой итерации цикла и правила по которым они изменяются; 2) определить условие продолжения цикла; 3) выписать начальные значения переменных в наборе S; 4) оформить цикл в соответствии с синтаксисом языка Си.

Вычисление суммы элементов числовой последовательности © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 30 Задача: На вход программы поступает количество N чисел в последовательности, а потом элементы a 1, a 2, … a N этой последовательности. Необходимо вычислить их сумму. Решение: S = a 1 + a 2 + … + a N – 1 + a N 1) 2) i) N – 1) N) S = a 1 + (a 2 + … + (a N – 1 + a N )…) S = 0 S = S + a 1 S = S + a 2 … S = S + a i … S = S + a N – 1 S = S + a N

Вычисление суммы элементов числовой последовательности © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Решение задачи можно разбить на однотипные фрагменты: прибавление к имеющемуся фрагменту суммы очередного элемента. При этом на каждой итерации цикла вводится элемент a i, обновляется сумма S (S = S + a i ), вычисляется номер i (i=i+1) следующего элемента. 2. Цикл продолжается до тех пор, пока не будет введено N элементов. i – счетчик цикла, определяет количество выполненных итераций. Поэтому условие продолжения цикла можно записать следующим образом: i N. 3. Изначально переменные, описывающие состояние цикла нужно установить соответственно: i = 1 – ввод первого элемента. S = 0 – до начала ввода сумма полагается нулевой. 1) 2) i) N – 1) N) S = 0 S = S + a 1 S = S + a 2 … S = S + a i … S = S + a N – 1 S = S + a N

Вычисление суммы элементов числовой последовательности (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 32 1) 2) i) N – 1) N) S = 0 S = S + a 1 S = S + a 2 … S = S + a i … S = S + a N – 1 S = S + a N i N ДА НЕТ i = 1, S = 0 S = S + a i = i + 1 S = S + a i = i + 1 N N a a S S Начало Конец

Вычисление суммы элементов числовой последовательности (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 33 i N ДА НЕТ i = 1, S = 0 S = S + a i = i + 1 S = S + a i = i + 1 N N a a S S Начало Конец #include int main() { int i, S, N, a; printf("Input N: "); scanf("%d",&N); i = 1; S = 0; while( i

Вложенные циклы © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» (1,1), (2, 1), (3,1), (4,1), (1,2), (2,2), …, (1,5), …, (4,5) Для решения этой задачи можно предложить два варианта: 1) организовать один цикл со счетчиком и на каждой итерации выражать координаты текущей области из текущего значения счетчика. 2) организовать два цикла так, чтобы один из них (внутренний) составлял в итерацию другого (внешнего). Счетчик внешнего цикла будет отвечать за координату y, а внутреннего – за координату x. При решении многих задач возникает необходимость одновременного перебора (однократного просмотра) значений по нескольким независимым направлениям. Например, перебор координат двумерной области:

Вложенные циклы (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 35 y 4 НЕТ y = 1 (x, y) Конец x = 1 x 5 НЕТ x = x + 1 y = y + 1 Начало

Вложенные циклы (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 36 (1,1) (2,1) (3,1) (4,1) (5,1) (1,2) (2,2) (3,2) (4,2) (5,2) (1,3) (2,3) (3,3) (4,3) (5,3) (1,4) (2,4) (3,4) (4,4) (5,4) #include int main() { int x, y; y = 1; while( y

Вложенные циклы (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 37 (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4) (5,1) (5,2) (5,3) (5,4) #include int main() { int x, y; x = 1; while( x

Вычисление простых чисел в указанном диапазоне © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 38 Простое число – это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Все остальные натуральные числа, кроме единицы, называются составными. Задача: Вывести список простых чисел, расположенных в диапазоне от 1 до N, где N задается с клавиатуры. Решение: 1. Осуществить перебор всех чисел в диапазоне от 1 до N (цикл, в котором счетчик i пробегает значения от 1 до N c шагом 1). 2. Для каждого числа i проверить его простоту. Для этого необходимо проверить, делится ли оно на что-либо кроме 1 и самого себя (цикл, в котором счетчик j перебирает все возможные делители i, т.е. j = 2 … i – 1).

Проверка на простоту © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 39 1) 2) j) i – 1) f = 0 f = f ИЛИ (i % 2 0) f = f ИЛИ (i % 3 0) … f = f ИЛИ (i % j 0) … f = f ИЛИ (i % (i – 1) 0) 1. Повторяющийся шаг: проверка, делится ли i на текущий потенциальный делитель j. На каждой итерации изменяется j (j = j + 1) и флаг f, в котором фиксируется факт деления без остатка. Если по завершению цикла f = 1, то число составное. 2. Цикл продолжается до тех пор, пока не будет просмотрено (i – 1) делителей. Условие продолжения цикла: j < (i – 1) можно записать следующим образом: i N. 3. Инициализация переменных: j = 2 (первый потенциальный делитель), f = 0 – изначально предполагаем число простым.

Проверка на простоту © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 40 j i – 1 ДА НЕТ j = 2, f = 0 f = f ИЛИ (i mod j 0) j = j + 1 f = f ИЛИ (i mod j 0) j = j + 1 f f...

Перебор чисел в заданном диапазоне © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 41 i N НЕТ i = 2 i = i + 1 N N Начало Конец f = i - простое f = i - простое f = 0 ДА i i

Вычисление простых чисел в указанном диапазоне © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 42 #include int main() { int N, i = 2, j, f; printf("Input N: "); scanf("%d", &N); while( i