Обработка последовательностей без использования дополнительной памяти

Обработка последовательностей без использования дополнительной памяти

Алгоритмы исследования элементарных функций, в частности – точного и приближенного решения квадратного уравнения с целыми и вещественными коэффициентами, определения экстремумов квадратичной функции на отрезке.

Алгоритмы анализа и преобразования записей чисел в позиционной системе счисления.

Алгоритмы, связанные с делимостью целых чисел. Алгоритм Евклида для определения НОД двух натуральных чисел.

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

Алгоритмы обработки массивов. Примеры: перестановка элементов данного одномерного массива в обратном порядке; циклический сдвиг элементов массива; заполнение двумерного числового массива по заданным правилам; поиск элемента в двумерном массиве; вычисление максимума и суммы элементов двумерного массива. Вставка и удаление элементов в массиве.

Рекурсивные алгоритмы, в частности: нахождение натуральной и целой степени заданного ненулевого вещественного числа; вычисление факториалов; вычисление n-го элемента рекуррентной последовательности (например, последовательности Фибоначчи). Построение и анализ дерева рекурсивных вызовов. Возможность записи рекурсивных алгоритмов без явного использования рекурсии.

Сортировка одномерных массивов. Квадратичные алгоритмы сортировки (пример: сортировка пузырьком). Слияние двух отсортированных массивов в один без использования сортировки.

Алгоритмы анализа отсортированных массивов. Рекурсивная реализация сортировки массива на основе слияния двух его отсортированных фрагментов.

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

Построение графика функции, заданной формулой, программой или таблицей значений.

Алгоритмы приближенного решения уравнений на данном отрезке, например, методом деления отрезка пополам. Алгоритмы приближенного вычисления длин и площадей, в том числе: приближенное вычисление длины плоской кривой путем аппроксимации ее ломаной; приближенный подсчет методом трапеций площади под графиком функции, заданной формулой, программой или таблицей значений. Приближенное вычисление площади фигуры методом Монте-Карло. Построение траекторий, заданных разностными схемами. Решение задач оптимизации. Алгоритмы вычислительной геометрии. Вероятностные алгоритмы.

Читайте также:  Как поменять батарейку в водонепроницаемых часах

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

Представление о структурах данных.Примеры: списки, словари, деревья, очереди. Хэш-таблицы.

Языки программирования

Подпрограммы (процедуры, функции). Параметры подпрограмм. Рекурсивные процедуры и функции.

Логические переменные. Символьные и строковые переменные. Операции над строками.

Двумерные массивы (матрицы). Многомерные массивы.

Средства работы с данными во внешней памяти. Файлы.

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

Представление о синтаксисе и семантике языка программирования.

Понятие о непроцедурных языках программирования и парадигмах программирования. Изучение второго языка программирования.

Разработка программ

Этапы решения задач на компьютере.

Структурное программирование. Проверка условия выполнения цикла до начала выполнения тела цикла и после выполнения тела цикла: постусловие и предусловие цикла. Инвариант цикла.

Методы проектирования программ «сверху вниз» и «снизу вверх». Разработка программ, использующих подпрограммы.

Библиотеки подпрограмм и их использование.

Интегрированная среда разработки программы на выбранном языке программирования. Пользовательский интерфейс интегрированной среды разработки программ.

Понятие об объектно-ориентированном программировании. Объекты и классы. Инкапсуляция, наследование, полиморфизм.

Среды быстрой разработки программ. Графическое проектирование интерфейса пользователя. Использование модулей (компонентов) при разработке программ.

Последовательная обработка

В ряде задач применяется последовательная обработка данных, если:

1. необходимо вводить и обрабатывать последовательность элементов исходных данных в том порядке, в каком она размещена в файле на внешнем носителе;

2. каждый элемент последовательности используется не более одного

Такие задачи называют (однопроходной) последовательной обработкой данных . В этом случае не требуется хранения сразу всех элементов. Достаточно иметь одну переменную, содержащую текущий (очередной) элемент входной последовательности.

В некоторых случаях используются несколько текущих элементов (например, два-три соседних).

Элементами данных последовательности могут быть:

— записи файла и др.

Последовательность исходных данных может задаваться:

1. с указанием количества элементов;

2. с признаком конца последовательности;

3. обрабатываться до конца входного файла.

Обработка числовых последовательностей

22.Числовая последовательность задается с указанием количества вводимых чисел:

Читайте также:  Zte mf920 личный кабинет

n, A 1 , A 2 , . A n .

На языке С процесс обработки можно записать с помощью оператора цикла while или лучше оператора цикла for:

while (i a вещественного типа (float), поэтому указан формат %f. Если же последовательность состоит из целых чисел типа int , то следует выбрать формат %d.

Обработка очередного числа может иметь линейную структуру (состоять из нескольких последовательно выполняемых операторов) или структуру ветвления, которая программируется с помощью оператора if .

23.Последовательность задается в виде

A 1 , A 2 , . , A n , W

(n заранее неизвестно, W — признак конца последовательности), тогда процесс обработки в общем виде можно представить одной из двух схем, представленных на рис. 5.2.

Фрагменты программ на языке С, соответствующие этим схемам: а)

scanf ("%f", &a); while (a!=W)

W — символическая константа, которая должна быть определена с помощью директивы #define . Если а принимает целые значения, формат в операторе ввода нужно поменять на %d.

24.Входная последовательность A 1 , A 2 , . , A n продолжается до конца входного файла, n — неизвестное заранее количество элементов (n >=0), признак конца отсутствует.

While (не конец входного файла)

Конец файла при вводе с клавиатуры задается комбинацией клавиш

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

Например, значением функции scanf() является количество фактически введенных элементов. Если не удалось ввести ни одного элемента, значение функции равно константе EOF, определенной в файле stdio.h как число -1.

Иногда в языке C можно обойтись одной операцией ввода A, поместив ее внутри условия цикла.

while (ввод A и A != W)

while (ввод A и не конец входного файла) Обработка A;

лабораторные работы и задачи по программированию и информатике, егэ по информатике

Пример работы с последовательностью

Последовательности — это абстрактный набор данных, которые можно перебирать.

В отличие от других структур последовательности не хранятся в памяти (поэтому «абстрактный»), т.е. память используется только в конкретный момент времени, когда происходит перебор значений последовательности, и, как правило, нам необходим только 1 элемент (в единицу времени).

Читайте также:  Мегаком как узнать свой номер

Последовательностью может быть, например, последовательность чисел:

арифметическая прогрессия: 1 3 5 7 9

геометрическая прогрессия: 1 2 4 8 16

Тип последовательности: Sequence of Real , Sequence of Integer

Наиболее близким типом данных к последовательности является массив.

Рассмотрим стандартный пример работы с числовым рядом, БЕЗ использования последовательности:

begin var s:=0.0; for var i:=1 to 10 do begin var x:=ReadReal; s+=x; end; print(s) end.

Данный стиль написания программы считается плохим, т.к. основной алгоритм смешивается с вводом ( ReadReal ).

Ввод данных необходимо отсоединить от основного алгоритма. Для этого используем последовательность:

// накапливаем последовательность, переменная q хранит ее var q:=ReadSeqReal(10); var s:=0.0; foreach var x in q do s+=x; print(s) end.

Теперь алгоритм находится отдельно от ввода, программа стала более модифицируема.
Остается оформить основной алгоритм в виде функции:

function Sum(q: sequence of real):real; begin var s:=0.0; foreach var x in q do s+=x; result:=s end; begin print(Sum(ReadSeqReal(10))) end.

Генерация и формирование последовательностей

Итак, мы рассмотрели, как сформировать последовательность через ввод с клавиатуры:

Теперь рассмотрим, как генерируются последовательности.

Генераторы последовательностей:
Range(a,b: integer) : sequence of integer

Range(a,b,step: integer) : sequence of integer

Range(c1,c2: char) : sequence of char

Partition(a,b: real; n: integer) : sequence of real

print(Partition(0.0, 6.0, 4)); // делим поровну на 4 части [0, 1.5, 3, 4.5, 6]

SeqRandomInteger(n: integer[; a,b: integer]) : sequence of integer;

var q:=SeqRandomInteger(5,10,20); print(q); // [12,18,16,14,16]

SeqRandomReal(n: integer[; a,b: real]) : sequence of real;

var q:=SeqRandomReal(3, 1.0, 5.0); print(q); // [4.98996168374548,2.22339218166815,2.81110574389394]

Seq(params a: array of T) : sequence of T;

foreach var x in Seq (1,3,8) do print(x*x); // 1 9 64

SeqFill(count: integer; x: T) : sequence of T;

begin var q:=SeqFill(7,5); print(q); // [5,5,5,5,5,5,5] end.

Следует учесть, что последовательности формируются каждый раз, как только с ними организовывается цикл или работает метод:

Вывод последовательностей

Print(delim: string := ‘ ‘) : sequence of T;

var q:=SeqRandomInteger(5,10,20); q.Print(‘/’); // 16/11/13/10/13

Println(delim: string := ‘ ‘) : sequence of T;

Ссылка на основную публикацию
Обзор монокуляров с алиэкспресс
Монокуляры активно применяются на охоте, во время путешествий, наблюдения за птицами и животными, при просмотре спортивных соревнований и в военных...
Непрерывность степенной функции доказательство
1. Непрерывность многочленов Так как функция у = х непрерывна в любой точке, по теореме о непрерывности произведения непрерывных функций,...
Ник для фотографа в инстаграме
В 2018 году количество пользователей Instagram превысило один миллиард. Уже более миллиарда вариаций ника занято. И с каждым годом решить...
Область определения функции корень кубический из х
РЕШЕНИЕ:Корень 3 степени может извлекаться как из положительных чисел и 0, так и из отрицательных чисел Корень третьей степени можно...
Adblock detector