Практические задания и вопросы к зачету по дисциплине «Программирование»

Практические задания и вопросы к зачету по дисциплине «Программирование»

Вопросы:

1. Хранение информации. Двоичная, восьмеричная и шестнадцатеричная системы счисления и связь между ними. Внутреннее представление беззнаковых целых чисел. Внутреннее представление текстовых данных.

2. Упрощенный процессор, основные элементы и их взаимодействие. Пример выполнения программы. Программа на языке ассемблера и на языке высокого уровня, основные отличия. Этапы формирования исполняемого кода из исходного.

3. Состав языка СИ. Алфавит. Лексемы. Расширенная форма Бэкуса-Наура. РБНФ идентификатора. Пример проверки идентификатора на соответствие РБНФ. РБНФ выражения языка СИ. Пример проверки выражения на соответствие РБНФ. Приоритеты и ассоциативность операций, примеры.

4. Оператор описания, его РБНФ, пример проверки соответствия РБНФ. Целочисленные типы данных языка Си. Примеры определения, ввода/вывода, арифметические действия. Вещественные типы данных языка Си. Примеры определения, ввода/вывода, арифметические действия.

5. Исполняемый оператор следования, его. РБНФ. Пример проверки соответствия РБНФ. Алгоритмы обмена значениями двух ячеек памяти. Блок операторов.

6. Исполняемый оператор ветвления. Настройка флага четности. Вложенность операторов ветвления.

7. Циклические конструкции. Цикл while, for, do-while, и их РБНФ. Пример использования. Вложенность циклов. Пример использования.

8. Использование программного отладчика GDB. Основные команды. Пример отладочного сеанса. 9. Задача сортировки. Алгоритм сортировки методом пузырька.

10. Одномерные массивы. Объявление массивов, инициализация. Операция индексации. Обработка массива. Выход за границы массива. Использование GDB для обнаружения данного класса ошибок.

11. Многомерные массивы. Логическое и физическое размещение элементов. Адресация двумерных массивов. Задача определения смещения элемента в физическом представлении. Адресация трехмерных массивов. Задача определения смещения элемента в физическом представлении. Обработка двумерного массива. Различный порядок обхода ячеек. Алгоритм вычисление произведения матриц.

12. Инициализация двумерных массивов. Сечение двумерных массивов. Оператор sizeof. Сечение трехмерных массивов. Оператор sizeof.

13. Хранение текстовой информации. Подходы к представлению строк. Преимущества и недостатки Pascal-strings. Преимущества и недостатки С-strings. Инициализация строк в языке СИ. Ввод-вывод строк в языке СИ.

14. Операции со строками. Получение символа по индексу. Определение длины строки. Копирование строки. Проверка строк на совпадение с учетом регистра. Проверка строк на совпадение без учета регистра. Сравнение строк в алфавитном порядке. Поиск символа в строке. Получение подстроки по индексам. Определение подстроки, состоящей только из допустимых символов. Поиск подстроки в строке.

15. Способы хранения многострочного текста. Хранение набора строк. Инициализация. Обращение к строке набора по индексу. Вставка новой строки. Удаление строки из набора. Поиск заданной строки в наборе. Конкатенация строк набора. Перестановка строк в наборе.

16. Императивная парадигма программирования. Процедурное программирование. Модульное программирование. Пример проектирования программ методом «сверху-вниз».

17. Подпрограммы в языке СИ. Понятие объявления, определения и вызова функции. Понятие формальных и фактических параметров функции. Передача параметров по значению. Передача параметров по указателю.

Задачи:

4. Ввод-вывод информации

4.1 На вход программы поступает два целых числа, значения которых находятся в диапазоне
[-30000, 30000]. Вычислить значения арифметических операций: a + b, a – b, a * b, a / b. Для a = 10 и b = 5 вывод программы должен выглядеть следующим образом:

10 + 5        = 15

10 – 5        =  5

10 * 5        = 50

10 / 5                = 2

4.2 На вход программы поступает два вещественных числа, значения которых находятся в диапазоне [-30000, 30000]. Вычислить значения арифметических операций: a + b, a – b, a * b, a / b. Для a = 10 и b = 3 вывод программы должен выглядеть следующим образом:

10 + 3        = 13

10 – 3        =  7

10 * 3        = 30

10 / 3                = 0.33

4.3 Распечатать на экране значение введенного целого числа в десятичной, восьмеричной и шестнадцатеричной системах счисления.

4.4 Выполнить ввод значения переменных a, b, c, d, типы которых соответственно char, short, unsigned int.

4.5 Какие типы данных достаточны, если входные данные не превышают число 1)? 2)? 3)? Сколько двоичных разрядов требуется для хранения этих чисел (выполнить перевод в двоичную систему счисления).

f5 ABFF FEFAAA

5. Арифметические операции

5.1 Необходимо разработать программу, на вход которой поступает целое число. Результатом работы программы является 1, если число нечетное и 0, если четное.

5.2 Необходимо разработать программу, на вход которой поступает целое число. Результатом работы программы является 1, если число четное и 0, если нечетное.

5.3 Преподаватель подготовил N вариантов заданий, их нужно распределить между M студентами. Если M ≤ N, то каждый студент получает уникальный вариант. Если M > N, то распределение производится следующим образом:

1) первые N студентов получают задания, которые совпадают с их номерами;

2) студент с номером (N+1) выполняет 1-е задание,  с номером 2N – N-е задание и так далее.

На вход программы поступает количество N вариантов и порядковый номер i  студента в списке преподавателя. Определить вариант, который необходимо выполнить студенту.

5.4 На вход программы поступает вещественное число. Необходимо вывести его целую и дробную части, например:

Вход: 12.568

Выход: 12; 0,568

5.5 На вход программы поступает вещественное число. Необходимо выполнить его арифметическое округление, например:

вход:  12.568; выход: 13

вход:  12.368; выход: 12

Реализовать решение как с использованием оператора ветвления, так и без него.

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

5.8 Привести два варианта решения задачи вычисления модуля вещественного числа на языке Си: с использованием операции ветвления и без.

5.9 Способы представления знаковых чисел на базе беззнаковых - дополнительный код. Разработать программу перевода знакового числа в дополнительный код.

5.10 Способы представления знаковых чисел на базе беззнаковых - дополнительный код. Разработать программу перевода числа, представленного в дополнительном коде, в знаковое представление.

6. Оператор ветвления

6.1 Вычислить модуль разности двух целых чисел. Входные данные: вещественные числа x и y.

Выходные данные: |x –  y|. Ограничения: Не допускается вычисление разности с последующим взятием модуля: нет возможности хранить отрицательное число.

6.2 Реализовать операцию сложения чисел в дополнительном коде (4 десятичных разряда). Входные данные: целые знаковые числа x и y. Выходные данные:

дополнительные коды для входных чисел x', y'. сумма чисел (x' + y') в дополнительном коде. знаковое представление числа (x' + y').

Указания:

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

6.3 Реализовать операцию вычитания чисел в дополнительном коде (4 десятичных разряда). Входные данные: целые знаковые числа x и y. Выходные данные:

дополнительные коды для входных чисел x', y'. разность чисел x' и y' согласно правилам арифметики чисел, представленных дополнительным кодом. знаковое представление полученного результата вычитания.

Указания:

выполнить преобразование входных знаковых чисел в дополнительный код; реализовать алгоритм вычитания чисел в дополнительном коде (если уменьшаемое меньше вычитаемого, то к нему прибавить 10000); выполнить преобразование полученного результата из дополнительного кода в знаковое число.

7. Циклические операторы

7.1 На вход программы поступает последовательность a, состоящая из N вещественных чисел. Необходимо определить значение максимального из них.

7.2 На вход программы поступает последовательность a, состоящая из N вещественных чисел. Необходимо определить значение минимального из них.

7.3 На вход программы поступает последовательность a, состоящая из N вещественных чисел. Необходимо вычислить среднее арифметическое элементов а.

7.4 На вход программы поступает последовательность a, состоящая из N вещественных чисел. Необходимо вычислить количество нулей в последовательности.

7.5 На вход программы поступает последовательность a, состоящая из N целых чисел. Необходимо вычислить сумму всех положительных чисел в последовательности.

7.6 На вход программы поступает последовательность a, состоящая из N целых чисел. Необходимо вычислить суммы чисел подпоследовательностей, расположенных по возрастанию, например:

вход: 1 2 3 1 5 7 2 4 5

выход: 6 13 11

7.7 На вход программы поступает целое число N. Необходимо распечатать на экран все четные числа от 0 до заданного числа.

7.8 На вход программы поступает десятичное число x = xn  … x3x2x1, где xi – i-й разряд числа x. Необходимо вывести разряды числа x в обратном порядке через пробел.

7.9 Разработать программу. На ее вход поступает десятичное целое положительное число. Необходимо определить количество значащих разрядов в этом числе.

7.10 Разработать программу. На ее вход поступает десятичное целое положительное число и номер разряда. Распечатать на экране значение соответствующего разряда. Например:

вход: x = 123456, i = 4, выход: 2

вход: x = 123456, i = 1, выход: 5

7.11 Для квадратов чисел верны следующие равенства:

1 = 12

1 + 3 = 4 = 22

1 + 3 + 5 = 9 = 32

1 + 3 + 5 + 7 = 16 = 42

. . . .

Используя данное свойство можно арифметически вычислить целую часть корня. Пусть x – число, для которого необходимо найти корень.

1. Если (x – 1) = 0, то √x = 1, если (x – 1) < 0, то [√x] = 0, иначе x = x – 1

2. Если (x – 3) = 0, то √x = 2, если (x – 3) < 0, то [√x] = 1, иначе x = x – 3

3. Если (x – 5) = 0, то √x = 3, если (x – 5) < 0, то [√x] = 2, иначе x = x – 5

4. Если (x – 7) = 0, то √x = 4, если (x – 7) < 0, то [√x] = 3, иначе x = x – 7

7.12 Итерационная формула Герона задает убывающую (начиная со 2-го элемента) последовательность, которая при любом выборе  быстро сходится к величине √a (квадратный корень из числа). Рекуррентное соотношение, описывающее данную последовательность выглядит следующим образом:

Реализовать программу вычисления корня по формуле Герона.

7.13 Реализовать алгоритм вывода целой части числа в двоичной системе счисления.

7.14 Реализовать алгоритм вывода дробной части числа в двоичной системе счисления.

7.15 На вход программы поступает два целых числа, на экран выводится их наибольший общий делитель (НОД). Использовать линейный алгоритм.

7.16 На вход программы поступает два целых числа, на экран выводится их наибольший общий делитель (НОД). Использовать алгоритм Евклида.

8. Вложенные циклические конструкции и массивы

8.1 Вычислить частичную сумму ряда, для заданного x и n:

8.2 Вычислить частичную сумму ряда, для заданного x и n:

8.3 Вычислить частичную сумму ряда, для заданного x и n:

8.4 На вход программы поступает последовательность целых чисел. Определить НОД для соседних элементов. Например:

Вход: 21 7 10 5 15

Выход:

(21, 7) = 7

(7, 10) = 1

(10, 5) = 5

(5, 15) = 5

8.5 На вход программы поступает последовательность целых чисел. Определить НОД для всех пар чисел в последовательности. Например:

Вход: 21 7 10 5 15

Выход:

(21, 7) = 7; (21, 10) = 1; (21, 5) = 1; (21, 15) = 1

(7, 10) = 1; (7, 5) = 1; (7, 15) = 1

(10, 5) = 5; (10;15) = 5;

(5, 15) = 5;

8.6 На вход программы поступает последовательность целых чисел. Определить НОД всех чисел в последовательности. Например:

Вход: 21 7 10 5 15

Выход:

(21, 7, 10, 5, 15) = 1.

8.7 Дана последовательность действительных чисел а1, а2, ..., аn и число x. Выяснить, является ли a возрастающей или убывающей. Если является, то вставить в нее элемент x так, чтобы порядок не был нарушен. Например:

Вход: а = 3 10 15 32 12; х = 12.

Выход: 3 10 12 15 32 12

Вход: а = 40 37 32 15 14 7; х = 20.

Выход: 40 37 32 20 15 14 7

Вход: а = 40 37 50 15 14 7; х = 20.

Выход: 40 37 50 15 14 7 (не изменена).

8.8 Реализовать алгоритм сортировки методом выбора для целых чисел. Программа предназначена для сортировки массивов, размер которых не превышает 100 элементов.

На вход поступает число N элементов в сортируемом массиве. Далее через пробел (или новую строку) подаются значения элементов.

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

8.10 Реализовать алгоритм сортировки методом вставки для целых чисел. Программа предназначена для сортировки массивов, размер которых не превышает 100 элементов.

На вход поступает число N элементов в сортируемом массиве. Далее через пробел (или новую строку) подаются значения элементов.

8.11 Реализовать алгоритм сортировки методом пузырька для целых чисел. Программа предназначена для сортировки массивов, размер которых не превышает 100 элементов.

На вход поступает число N элементов в сортируемом массиве. Далее через пробел (или новую строку) подаются значения элементов.