- •Ответы по дисциплине «Основы алгоритмизации и программирования»
- •Запись алгоритма Евклида на языке с
- •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() {
«Правильный» алгоритм поиска маршрута
Очевидно, что исчерпывающее решение задачи дает алгоритм, основанный на переборе и оценке всех возможных маршрутов движения, а их количество, как несложно показать, равно количеству перестановок.
Например, если n=20, то количество возможных маршрутов будет порядка
20! = 2 432 902 008 176 640 000
Лекция 2. Язык программирования С. Общие сведения.
Вопрос №6. Краткая характеристика языка С.
Популярный компактный язык общего назначения; изначально создавался как язык системного программирования (для ОС UNIX)
«Низкоуровневый» язык, типы данных и управляющие структуры которого близки архитектуре большинства компьютеров
Примечательные особенности языка С:
адресная арифметика с использованием указателей
чрезвычайно широкий набор операций
все функции используют передачу аргументов по значению
простая двухуровневая структура областей видимости
отсутствуют средства ввода/вывода и управления памятью (они обеспечиваются подпрограммами из библиотеки)
гибкая структуры типов
Вопрос №7. Стандартизация языка С. Эволюция языка С.
Первый стандарт языка C был опубликован американским институтом ANSI. Через некоторое время он был принят международной организацией по стандартизации ISO, продолжившей выпускать следующие версии стандарта, которые стали приниматься как стандарт и институтом ANSI. Несмотря на это стандарт до сих пор чаще называют ANSI C, а не ISO C.
C89
В 1983 году Американский национальный институт стандартов сформировал комитет X3J11 для создания спецификации стандарта C. В 1989 году, после длительного и напряжённого процесса, стандарт был завершён и утверждён как ANSI X3.159-1989 «Язык программирования C». Именно эту версию часто называют «ANSI C», или «C89» (чтобы отличить её от C99).
C90
В 1990 году, стандарт ANSI C (с небольшими изменениями) был принят Международной организацией по стандартизации (ISO) как ISO/IEC 9899:1990. Эту версию иногда называют C90. Однако, термины C89 и C90 относятся в сущности к одному языку.
C99
В марте 2000 года ANSI принял стандарт ISO/IEC 9899:1999. Этот стандарт обычно называют C99. Это и есть современный стандарт языка программирования C, однако его не поддерживает полностью ни один компилятор.
C1x
C1x - новый стандарт языка, который ещё находится в стадии подготовки. Существует черновой вариант. Основным новшеством стандарта являются потоки.
Эволюция языка с bcpl → b → c → k&r c → ansi c → c99 → c1x
≈1960 ≈1970 ≈1972 ≈1978 ≈1988 ≈1999 ??
Переменные, константы и типы данных
Вопрос №8. Определение понятия «переменная». Имена переменных.
Фундаментальные объекты данных, с которыми работает программа – это переменные и константы.
Переменная имеет имя, тип и текущее значение.
Имя для переменной выбирается программистом произвольно с учетом следующих ограничений:
имя должно начинаться с буквы и может состоять из букв и цифр; знак «подчеркивание» считается буквой;
буквы в верхнем и нижнем регистре различаются;
в качестве имен не разрешается использовать зарезервированные слова языка (for, while, int и т.п.);
длина имени не может быть более 31 символа для внутренних переменных и более 6 символов для внешних переменных.
Вопрос №9. Символические константы и директива препроцессора #define.
Кроме имен переменных в программах могут использоваться символические имена (символические константы), которые определяются с помощью директивы препроцессора #define и задают правило подстановки: