- •Ответы по дисциплине «Основы алгоритмизации и программирования»
- •Запись алгоритма Евклида на языке с
- •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 a = 12, b, c;
printf("result = %d \n", c=(b=a)-5);
system("PAUSE");
return 0;
}
Вопрос №23. Операции, совмещенные с присваиванием.
В языке С операция присваивания немного отличается от аналогичной операции в других языках:
Кроме обычного присваивания существует ещё 10 модификаций, в которых присваивание совмещается с какой-либо бинарной операцией, например, k += 2 эквивалентно k = k + 2, или ещё: x >>= 1 эквивалентно x = x >> 1 и т.д. Полный перечень бинарных операций, совмещаемых с присваиванием:
+ - * / % << >> & ^ |
#include <stdio.h>
#include <stdlib.h>
// Подсчет количества единичных битов в двух байтах
Int main() {
unsigned short x = 0x1234;
int b;
for (b=0; x!=0; x >>= 1)
if (x & 01) b++;
printf("the number of bits = %d \n", b);
system("PAUSE");
return 0;
}
Вопрос №24. Тернарная условная операция.
Во многих алгоритмах часто встречается конструкция вида:
if ( условие) x=<выраж1>;
else x=<выраж2>;
Иными словами, переменная x получает значение одного из двух выражений, в зависимости от истинности условия.
В языке С для компактной записи подобного фрагмента существует специальная тернарная условная операция:
x = условие ? <выраж1> : <выраж2>
#include <stdio.h>
#include <stdlib.h>
#define N 57
Int main() {
int i, x[N];
for (i=0; i<N; x[i]=++i);
for (i=0; i<N; ++i)
printf("%6d%c", x[i], (i%8==7 || i==N-1) ? '\n' : ' ');
system("PAUSE");
return 0;
}
Вопрос №25. Приоритет и ассоциирование операций.
№ |
Операции |
Ассоциирование |
Кол. |
1 |
() [] -> . |
→ |
4 |
2 |
! ~ ++ -- + - * & (тип) sizeof |
← |
12 |
3 |
* / % |
→ |
3 |
4 |
+ - |
→ |
2 |
5 |
<< >> |
→ |
2 |
6 |
< <= > >= |
→ |
4 |
7 |
== != |
→ |
2 |
8 |
& |
→ |
1 |
9 |
^ |
→ |
1 |
10 |
| |
→ |
1 |
11 |
&& |
→ |
1 |
12 |
|| |
→ |
1 |
13 |
?: |
← |
1 |
14 |
= += -= *= /= %= &= ^= |= <<= >>= |
← |
11 |
15 |
, |
→ |
1 |
Всего операций: 47
Операции, находящиеся в одной строке таблицы , принадлежат одной группе: имеют одинаковый приоритет и одинаковый порядок выполнения (слева направо или наоборот).
Все 47 операций распределены по 15 группам, группа 1 имеет наивысший приоритет, а группа 15 наинизший приоритет.
1-я группа: () - вызов функции, [] – доступ к элементу массива, -> - обращение к элементу структуры через указатель, . - обращение к элементу структуры через имя структуры.
2-я группа (унарные операции): + - - унарные «плюс» и «минус», * - «разыменование» указателя, т.е. обращение к объекту, на который он указывает, & - получение адреса объекта, (тип) – приведение типа операнда, sizeof – определение размера объекта.
…
15-я группа: , - операция «запятая» - это бинарная операция имеющая вид: выражение1 , выражение2. Действие операции заключается в последовательном вычислении выражений, а её результатом является значение второго выражения.
Вопрос №26. Понятие термина «приведение типа». Явное и неявное приведения типов. Корректные приведения типов.
Приведение типа (type conversion) — преобразование значения одного типа в значение другого типа.
Выделяют явное и неявное приведения типов.
при явном приведении с помощью унарной операции (тип) указывается тип, к которому необходимо преобразовать значение выражения, расположенного справа от этой операции;
при неявном приведении преобразование происходит автоматически, по правилам, заложенным в языке программирования.
Корректными преобразования типов, не вызывающими искажения значений или потери точности, являются приведения более «узких» типов к более «широким».
Если же значение более «широкого» типа приводится к более «узкому» типу, возможно искажение значения или потеря точности, о чем выдает предупреждение (warning) компилятор.
Явные преобразования типов всегда происходят по «инициативе» программиста, а инициатором неявных преобразований выступает компилятор в тех случаях, когда при выполнении операции ожидается один тип, а фактически присутствует другой тип.
Замечание. В некоторых случаях неявное преобразование бывает просто неосуществимым «по определению». Например, в выражении 3.0%2.0 значения 3.0 и 2.0 не преобразуется автоматически к целому типу, т.к. операция % применима только к целочисленным значениям и поэтому компилятор выдаст сообщение об ошибке (error).
Управляющие конструкции языка С.
Вопрос №27. Простой оператор. Составной оператор (блок). Локальные переменные. Вложенные блоки.
Если в конце любого выражения поставить символ ; (точка с запятой), получим элементарную «строительную конструкцию» программы – простой оператор:
z = foo(x+y); x+=y; 2=4*5; …
Простые операторы в программе могут располагаться последовательно, друг за другом:
temp = x+y; z = foo(temp);
Последовательность простых операторов можно заключить в фигурные скобки { и }. В этом случае получится составной оператор, или, иначе – блок, который синтаксически эквивалентен простому оператору и компилируется как самостоятельная конструкция. После закрывающей скобки точка с запятой не ставится.
Блок может быть пустым: {}
Внутри блока можно размещать объявления переменных:
{
int temp = x+y;
z = foo(temp);
}
Такие переменные будут локальными; они будут создаваться при входе в блок и исчезать при выходе из блока. За пределами блока локальные переменные невидимы.
Блоки могут быть вложенными (глубина вложенности не ограничивается)
{
int temp = x+y;
z = foo(temp);
{
float temp2 = x∗y;
z += bar(temp2);
}
}
Вопрос №28. Операторы простого выбора if и if … else.
В простейшем случае требуется выбрать для выполнения определенный оператор, если некоторое условие истинно (т.е. его значение отлично от 0). Это записывается так: