Билет №44. Основы алгоритмизации. Алгоритм. Язык структурного программирования. Принципы структурного программирования.
Язык структурного программирования
Три основные (базовые) конструкции:
1. Действие
2. Условие
3. Цикл
Принципы структурного программирования
1. Отказ от оператора безусловного перехода “goto”.
2. Все алгоритмы строятся на основе трёх базовых конструкций.
3. Эти конструкции могут быть вложены друг в друга неограниченное количество раз.
4. Повторяющиеся фрагменты алгоритма желательно оформлять в виде подпрограммы.
5. Каждую логически законченную структуру стоит оформлять как блок.
6. Все конструкции имеют один вход и один выход.
7. Разработка программ должна вестись методом «сверху вниз» (от больших функций к детальным).
Метод «сверху вниз» представляет собой способ записи алгоритма, когда он расписывается в виде вызовов функций-«заглушек», возвращающих какие-либо постоянные значения. Каждая функция-«заглушка» реализуется в виде своего алгоритма, также основанного на вызове «заглушек». Это продолжается, пока алгоритм не будет расписан до элементарных действий.
Билет №45. Основы алгоритмизации. Поиск минимума и максимума.
Поиск минимума
Если n > 0
min = A[0]
i = 0
Пока (i < n)
Если min > a[i] то
min = a[i]
i = i + 1
n – кол-во элементов в массиве
Поиск максимума
Если n > 0
max = A[0]
i = 0
Пока (i < n)
Если max < a[i] то
max = a[i]
i = i + 1
n – кол-во элементов в массиве
Билет №46. Основы алгоритмизации. Алгоритмы сортировки. Сортировка «пузырьком».
|
|
|
n – количество элементов в массиве
i = 0
Пока i < n
j = i + 1
Пока j < n
Если a[i] > a[j] то
tmp = a[j]
a[j] = a[i]
a[i] = tmp
j = j + 1
i = i + 1
Билет №47. Основы алгоритмизации. Алгоритмы сортировки. «Гномья сортировка».
n – количество элементов в массиве
i = 1
j = 2
Пока i < n
Если a[i - 1] > a[i]
i = j
j = j + 1
Иначе
tmp = a[i-1]
a[i-1] = a[i]
a[i] = tmp
i = i - 1
Если i == 0
i = j
j = j + 1
Билет №48. Основы алгоритмизации. Алгоритмы сортировки. Сортировка «расчёской».
n – количество элементов в массиве
i = 0
tmp = 0
// f округляем до целых
f = 1 / 1.247330950103979
Пока f >= 1
i = 0
Пока i+f < n
Если a[i] > a[i+f]
tmp = a[i]
a[i] = a[i+f]
a[i+f] = tmp
i += 1
f -= 1
Билет №49. Основы алгоритмизации. Алгоритмы сортировки. Алгоритм быстрой сортировки Хоара.
БыстраяСортировка{
i = k
j = k-1
n = b[(i + j)/2]
пока (i <= j)
{
пока(b[i] < n)
i = i + 1
пока(b[j] > n)
j = j - 1
если(i <= j)
{
tmp = b[i]
b[i] = b[j]
b[j] = tmp
i = i + 1
j = j - 1
}
}
если (i < k-1)
БыстраяСортировка(i, k-1)
если (k < j)
БыстраяСортировка(k, j)
}
Билет №50. Основы алгоритмизации. Рекурсия. Назначение и проблемы применения.
|
|
|
Рекурсия
Вызов функцией самой себя с некоторым изменением входных параметров.
База рекурсии – пустой массив, или состоящий из одного элемента, возвращающийся в исходном виде.
Главное условие вызова рекурсивной функции – наличие сходимости (достижение базы рекурсии).
При несоблюдении этого объёма будет ошибка либо некорректная работа.
Билет №51. Основы алгоритмизации. Проверка вводимых данных: типовые ошибки и методы борьбы с ними.
Операции с данными
Типовые ошибки:
· Деление на ноль
· Запись нецелого числа в целое, появление там «машинного нуля»
· Корень чётной степени из отрицательного числа
· Аргумент тригонометрической функции, выходящий за рамки ОДЗ
Методы борьбы:
То есть, для любых функций, имеющих ограничение на ОДЗ, необходимо проводить проверку вводимых данных.
· Установка границ для вводимых данных, согласно ОДЗ
Операции с массивами и памятью
Типовые ошибки:
· Обращение к элементу массива с индексом, выходящим
за рамки [0, длина_массива – 1].
· Ввод данных слишком большого размера, не помещающихся в ячейку, выделенную для них.
Методы борьбы:
· Проверка вводимых индексов для элементов массива
|
|
|
· Проверка размеров копируемого блока памяти, проверка размеров области, выделяемой для этого блока.
Знаковые и беззнаковые переменные
Нельзя использовать в одном выражении знаковые и беззнаковые переменные, т.к. они имеют разную интерпретацию: знаковое число воспринимается как большое беззнаковое и наоборот.
Методы борьбы:
Принудительное приведение к одной форме знаковых и беззнаковых переменных.
Билет №52. Основы устройства современных вычислительных систем. Память. Назначение. Классификации.
Память, назначение
Устройство или среда, предназначенные для хранения информации.
Информация может храниться как в виде электронных сигналов, так и путём преобразования сигналов в иные физические структуры с последующим обратным преобразованием.
Для любой памяти обязательной операцией является чтение.
Классификация
По доступным операциям:
· Постоянная (только чтение)
o Память, значение которой формируется однократно при её производстве или первичной инициализации для программируемых З. У.
Примером первичной инициализации может быть разрушение электронных контактов путём подачи повышенного напряжения на пустую микросхему памяти.
|
|
|
· Перепрограммируемая (запись новых данных)
o Развитое ПЗУ, в котором появилась возможность восстанавливать память в исходное неинициализируемое состояние.
Пример: схема с ультрафиолетовым стиранием информации,
электрически стираемая информация (EEPROM).
· Без ограничений (и чтение, и запись)
o Позволяет читать и записывать информацию без применения дополнительных мер и существенных ограничений.
§ По способу хранения разделяется на статическую (достаточно записи данных; обеспечивает непрерывное хранение информации и возможность её постоянного чтения) и динамическую (данные нужно обновлять, иначе они пропадут; склонна к потере информации с течением времени и нуждается в её регулярном обновлении – цикле регенерации; для большинства типов динамической памяти характерно уничтожение информации при её чтении. То есть, считывая информацию, её нужно записывать обратно).
§ По типу носителя разделяется на регистровую (строится на основе триггеров, относится к наиболее быстродействующим типам памяти, но дорога в производстве), конденсаторную (диодно-конденсаторную) – (используется при построении оперативной памяти; быстрее, чем другие типы памяти, но медленнее, чем регистровая; экономичнее регистровой в производстве, но нуждается в регенерации), флеш-память (энергозависимая память, построенная на основе полупроводниковых технологий), на основе магнитных носителей (дискета), на основе отражающих (диск), в будущем – голографическая, кристаллическая, молекулярная.
§ По способу адресации: с произвольным доступом (при этом, как правило, имеется минимальный адресный объём памяти), ассоциативная – кэш-память (не может напрямую адресовать конкретный элемент; адресует на основании конкретных адресов и ссылок), с очередностью чтения и записи (стек, очередь) – кэш-память с очередностью позволяет хранить только адреса входа или входа и выхода.
§ По организации адресного пространства – реальная (адресация осуществляется в соответствии с физической организацией носителя информации) и виртуальная (адресация и принцип действия отличаются от реально используемой физической структуры для создания единообразия в работе с памятью. Все задачи по взаимодействию с физической средой ложатся на операционную систему и драйверы).
Дата добавления: 2019-01-14; просмотров: 1162; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!