- •Ответы по дисциплине «Основы алгоритмизации и программирования»
- •Запись алгоритма Евклида на языке с
- •Int main() {
- •Эвристический алгоритм «ближайшего соседа»
- •Эвристический алгоритм «ближайших пар»
- •«Правильный» алгоритм поиска маршрута
- •Эволюция языка с bcpl → b → c → k&r c → ansi c → c99 → c1x
- •#Define имя текст_для_подстановки
- •123, 67543, 037, 07777, 0Xabf7, 0xffff, …
- •123456789L, 0xful (это просто число 15).
- •Определение символических констант в limits.H
- •Int lower, upper, step;
- •Int main() {
- •Int main() {
- •Int main() {
- •Всего операций: 47
- •If (условие) оператор
- •If (условие) оператор1 else оператор2
- •Int main() {
- •Int main() {
- •Int main() {
- •Int main() {
- •If (found)
- •Адресация памяти
- •Адреса объектов программы
- •Int fact(int n) {
- •О размерах участков памяти, выделяемых объектам
- •Правила адресной арифметики
- •Никакие другие операции к адресам неприменимы, т.Е. Адреса нельзя умножать, делить, складывать между собой и пр.
- •Имя массива – это константный указатель на его начало.
- •T X[] эквивалентно t *X
- •Int main() {
- •Void *calloc(size_t n, size_t r)
- •Void free(void *p)
- •Int main() {
- •Void *p;
- •Void swaps(char** a, char** b) {
- •Int main(void) {
- •Int main() {
- •Правило «право-лево»
- •Int pt_in_rect(struct point p, struct rect r) {
- •Int main() {
- •Int main() {
- •Int ival;
- •Void init(Vector*);
- •Void resize(Vector*, int);
- •Void push_back(Vector*, double);
- •Void push_s(Stack *st, double d) {
- •Void init_q(Queue *q) {
- •Void enqueue(Queue *q, double d) {
- •Int dequeue(Queue *q, double *d) {
- •Typedef struct Heap {Vector V;} Heap;
- •Void init_h(Heap *hp) {
- •Int Heap_Maximum(Heap *hp, double *z) {
- •Void Max_Heap_Insert(Heap *hp, double X){
- •Void Max_Heapify(Heap *hp, int I) {
- •Int l, r, largest;
- •Int Heap_Extract_Max(Heap *hp, double *z) {
- •Void Build_Max_Heap(Heap *hp) {
- •Void Insert_head_l1(List1 *l, double z) {
- •Void Insert_back_l1(List1 *l, double z) {
- •Int Extract_head_l1(List1 *l, double *z) {
- •Int Extract_back_l1(List1 *l, double *z) {
- •Void reverse_l1(List1 *l) {
- •Исходный код функции sort_l1
- •Void sort_l1(List1 *l) {
- •Void visit(List1* l) {
- •Void traverse(List1* l) {
- •Void Print_l1(List1 *l) {
- •Void Insert_l2(List2 *l, double z, int direction) {
- •Прямой обход (сверху вниз), при котором мы посещаем узел, а затем левое и правое поддеревья
- •Поперечный обход (слева направо), при котором мы посещаем левое поддерево, затем узел, а затем правое поддерево
- •Обратный обход (снизу вверх), при котором мы посещаем левое и правое поддеревья, а затем узел.
- •Простой метод сортировки массива
- •Задача о взвешивании монет
- •1) Очевидно, что на последнем шаге процедуры взвешивания мы должны иметь дело максимум с 3 монетами, чтобы в при любом исходе взвешивания получить результат.
- •2) Задача предпоследнего шага – отобрать группу из 3-х монет. Это можно сделать, если в нашем распоряжении будет не более 9 монет (3 группы по 3 монеты).
- •3) Наконец, если у нас будет от 10 до 27 монет, мы сможем отобрать из них не более 9
- •Void mov(int n, char a, char c, char b) {
- •Int main() {
Int main() {
int n;
char s[] = "qwerty \t\t \n\n";
printf("before:\n");
printf("number of characters(%s) = %d\n", s, strlen(s));
for (n = strlen(s)-1; n >= 0; n--)
if (s[n] != ' ' && s[n] != '\t' && s[n] != '\n') break;
s[n+1] = '\0';
printf("after:\n");
printf("number of characters(%s) = %d\n", s, strlen(s));
system("PAUSE");
return 0;
}
Вопрос №36. Оператор continue.
Этот оператор похож на break, но, в отличие от break, досрочно прекращает выполнение текущей итерации цикла, а не всего оператора цикла. Для циклов while и do это означает переход к проверке условия, а для цикла for – вычисление выражения3, а уже затем переход к проверке условия.
Пример: подсчитать количество положительных элементов массива и найти их среднее арифметическое.
#include <stdio.h>
#include <stdlib.h>
Int main() {
int x[] = {-1, 4, 0, -3, -7, 5, 11, -2}, i, n;
double s;
for(i = 0, n = 0, s = 0.0; i < sizeof(x) / sizeof(x[0]); i++) {
if(x[i] <= 0) continue;
s += x[i]; n++;
}
if(n) s /= n;
printf("number of positive elements = %d\n", n);
printf("mean value = %f\n", s);
system("PAUSE");
return 0;
}
Вопрос №37. Оператор перехода goto и метки.
Оператор goto метка вызывает безусловный переход к оператору (в той же самой функции) перед которым записана метка (обычное имя, заканчивающееся символом : - двоеточие).
Пример: проверить, имеют ли два массива хотя бы один общий элемент.
#include <stdio.h>
#include <stdlib.h>
Int main() {
int a[] = {-1, 4, 0, -3, -7, 5, 11, -2}, i;
int b[] = {7, -12, 8, 9, 11, -2}, j;
int n = sizeof(a) / sizeof(a[0]);
int m = sizeof(b) / sizeof(b[0]);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if (a[i] == b[j]) goto found;
printf("no common elements\n");
goto final;
found:
printf("common elements: a[%d] == b[%d]\n", i, j);
final: system("PAUSE");
return 0;
}
Оператор goto является «нежелательным» оператором, т.к. «запутывает» логическую структуру программы, однако бывают ситуации, когда программа без goto получается более громоздкой, чем с goto.
Пример: предыдущая программа без goto.
#include <stdio.h>
#include <stdlib.h>
Int main() {
int a[] = {-1, 4, 0, -3, -7, 5, 11, -2}, i;
int b[] = {7, -12, 8, 9, 11, -2}, j, found = 0;
int n = sizeof(a) / sizeof(a[0]);
int m = sizeof(b) / sizeof(b[0]);
for (i = 0; i < n && !found; i++)
for (j = 0; j < m && !found; j++)
if (a[i] == b[j]) found = 1;
If (found)
printf("common elements: a[%d] == b[%d]\n", i, j);
else
printf("no common elements\n");
system("PAUSE");
return 0;
}
Функции и структура программы
Вопрос №38. Определение понятия «модульность». Виды модулей. Средства реализации модульности в языке С.
Модульность в языках программирования — принцип, согласно которому программное средство - ПС (программа, библиотека, web-приложение и др.) разделяется на отдельные сущности, называемые модулями. Модульность позволяет упростить задачи проектирования ПС и распределения процесса разработки ПС между группами разработчиков, а также позволяет реализовать методологию повторного использования кода.
При разбиении ПС на модули для каждого модуля указывается реализуемая им функциональность, а также связи с другими модулями. Роль модулей могут играть структуры данных, библиотеки функций, классы, сервисы и др. программные единицы, реализующие некоторую функциональность и предоставляющие интерфейс к ней.
В языке С модульность поддерживается функциями, препроцессоными командами, многофайловой структурой программы и заголовочными файлами.
Вопрос №39. Функции языка С и модульность программы. Интерфейс и реализация функции.
Функции разбивают большие вычислительные задачи на более мелкие и позволяют инкапсулировать («упрятать» в оболочку) детали реализации некоторой функциональности, предоставив пользователям («клиентам») формат обращения к этой функциональности (интерфейс). Это делает программу в целом более ясной и облегчает внесение в нее изменений.
Пример: функция, преобразующая символьное изображение числа, записанное в строке, в само число.
Вопрос №40. Правила (синтаксис) определения функции. «Минимальная» функция.
Для того, чтобы использовать функцию, ее необходимо определить: описать её интерфейс (т.е. объяснить, как функцией можно воспользоваться) и привести программный код, раскрывающий, как функция работает (т.е. записать реализацию функции на языке программирования).
Определение любой функции имеет следующую форму:
тип_возвращ_знач имя_функции(список_объявлений_арг) {
объявления и операторы
}
Различные части этого определения могут отсутствовать, но обязательными являются: имя_функции, пара круглых скобок и пара фигурных скобок, т.е. «минимальная» функция определяется так: fun(){} Это – «пустышка», которая не принимает никаких аргументов и ничего не делает (имеет пустое «тело»). Подобные функции могут использоваться в качестве «заглушек» при разработке программ.
Если при объявлении функции не указан тип возвращаемого значения, то по умолчанию подразумевается тип int.
Вопрос №41. Свойства функций. Оператор return.
Любая программа является набором определений
типов,
переменных и
функций.
Функции обмениваются данными посредством передачи аргументов и возвращения значений, а также через внешние переменные.
Функции могут следовать друг за другом в файле исходного кода в любом порядке, и текст программы можно разбивать на любое количество файлов, но при этом запрещается разбивать текст функции между файлами.
Функция не может быть определена внутри другой функции
В результате своей работы функция может возвратить в вызывающую ее функцию результат – некоторое значение, тип которого объявлен перед именем функции. Для этого в теле функции должен присутствовать хотя бы один оператор возврата вида: return выражение; Вызывающая функция может игнорировать (т.е. не использовать) возвращаемое значение.
Существует еще одна форма оператора возврата: return; В этом случае в вызывающую функцию ничего не передается, а при определении функции в качестве типа возвращаемого значения указывается void.
Тело функции может не содержать оператора возврата return ; при этом возврат из функции происходит при достижении конца блока (закрывающей скобки } ).
Вопрос №42. Аргументы функции и результат выполнения функции. Вызов функции. Передача аргументов по значению. Указатели в качестве аргументов функции.
Все аргументы в функцию передаются по значению, т.е. функция получает значения своих аргументов в виде временных переменных, а не оригиналов. Следовательно, все действия функции со своими аргументами никак не отражаются на переменных, переданных функции при вызове. Исправить это положение можно с помощью указателей.
Пример: функция, производящая «обмен значениями» двух переменных.
Вопрос №43. Функция main. Две формы функции main.
Программа может использовать любое количество функций при одном условии: в любой программе обязательно должна присутствовать в точности одна функция с именем main («главная» функция), т.к. запуск программы на выполнение операционной системой производится всегда через эту функцию (т.е. main начинает выполняться первой).
Функция main всегда имеет тип возвращаемого значения int, через это значение ОС уведомляется об успешности или не успешности завершения программы (т.н. «код завершения»). А т.к. int подразумевается «по умолчанию», то тип возвращаемого значения для main часто не указывают.
Существует две формы main:
без аргументов – main() и
с аргументами – main(int argc, char *argv[])
Вторая форма main позволяет при вызове программы из командной строки передать в нее произвольное количество строковых аргументов.
Вопрос №44. Определение понятия «рекурсия»
Рекурсия — процесс повторения чего-либо самоподобным способом. Например, вложенные отражения, производимые двумя точно параллельными друг другу зеркалами, являются одной из форм бесконечной рекурсии.
Наиболее общее применение рекурсия находит в математике и информатике. Здесь она является методом определения функций, при котором определяемая функция применена в теле своего же собственного определения. При этом бесконечный набор случаев (значений функции) описывается с помощью конечного выражения, которое для некоторых случаев может ссылаться на другие случаи, если при этом не возникает циклов или бесконечной цепи ссылок. Фактически это способ определения множества объектов через самого себя с использованием ранее заданных частных определений.
В программировании рекурсия — вызов функции из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Язык С допускает рекурсивный вызов функций, т.е. функция может вызывать саму себя прямо или косвенно.
Классический пример рекурсии – вычисление факториала целого числа. n! = n * (n-1)! , 0! = 1.
Лекции 8-9. Указатели и массивы.
Вопрос №45. Определение понятия «адрес объекта». Операция получения адреса объекта.