Методы разработки алгоритмов и программ: модульный, структурный.

⇐ ПредыдущаяСтр 3 из 3

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

Структурное программирование Цель структурного программирования - выбор структуры программы путем расчленения исходной задачи на подзадачи. Программы должны иметь простую структуру. Сложные, запутанные программы, как правило, являются неработоспособными, а их тестирование требует больших затрат. Разработка алгоритма, являясь четким логичным процессом, упрощается на каждом уровне шаг за шагом. Затем в процессе задействуется следующий метод алгоритмизации - метод пошагового уточнения (совершенствования). Сначала задача рассматривается в целом, выделяются наиболее крупные ее части. Алгоритм, указывающий порядок выполнения этих частей, описывается в структурированной форме, не вдаваясь в мелкие детали. Затем от общей структуры переходят к описанию отдельных частей. Таким образом, разработка алгоритма состоит из последовательности шагов в направлении уточнения алгоритма.

Идея модульного програмирования состоит в том, что алгоритм может быть представлен в виде системы, совокупности отдельных модулей. Каждый модуль рассматривается как самостоятельная, относительно независимая программа, которая может содержать набор данных и функций, доступных только из этого модуля. Модульное программирование позволяет значительно ускорить процесс за счет привлечения к работе нескольких специалистов сразу, доверив каждому разработку отдельного модуля. Кроме того, модульное программирование предполагает возможность использования заранее разработанных стандартных программ (т.н. библиотек стандартных подпрограмм).

На этапе проектирования алгоритма решения сложной задачи, состоящей из нескольких подзадач, используют два подхода: нисходящий и восходящий. При нисходящем проектировании вначале проектируются функции управляющей программы - драйвера. Затем более подробно представляют каждую подзадачу и разрабатывают другие модули. При нисходящем проектировании на каждом шаге функционирование модуля описывается с помощью ссылок на последующие, более подробные шаги. При восходящем проектировании вначале проектируют программы низшего уровня.

Базовые управляющие структуры, их назначение и преимущество использования.

Любая программа представляет собой структуру, построенную из трёх типов базовых конструкций:

• последовательное исполнение — однократное выполнение операций в том порядке, в котором они записаны в тексте программы;

• ветвление — однократное выполнение одной из двух или более операций, в зависимости от выполнения некоторого заданного условия; if, case

• цикл — многократное исполнение одной и той же операции до тех пор, пока выполняется некоторое заданное условие. (While, until, for)

Способы описания алгоритмов: словесный, графический.

Словесное описание алгоритма представляет собой описание структуры алгоритма на естественном языке. Например, к приборам бытовой техники, как правило, прилагается инструкция по эксплуатации или рецепты приготовления блюда.

Графическое описание алгоритма в виде блок-схемы – это описание структуры алгоритма с помощью геометрических фигур с линиями связи.

Псевдокод – описание структуры алгоритма на естественном, но частично формализованном языке. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика. Строгих синтаксических правил для записи псевдокода не предусмотрено.

Системы счисления. Способы перевода чисел из системы в систему.

СИСТЕМЫ СЧИСЛЕНИЯ - способы кодирования числовой информации, т.е. способ записи чисел с помощью некоторого алфавита, символы которого называют цифрами.

Величина числа может зависеть от порядка цифр в записи, а может и не зависеть. Это свойство определяется системой счисления и служит основанием для простейшей классификации таких систем, что позволяет все системы счисления разделить на три класса (группы):

- позиционные;

- непозиционные;

- смешанные.

Денежные знаки — это пример смешанной системы счисления.

Примером «чисто» непозиционной системы счисления является римская система.

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

Десятичная система включает в себя числа от 0 до 9, двоичная от 0 до 1, восьмеричная от 0 до 7, в шестнадцатеричную же входят числа от 0 до 9, а числа 10, 11, 12, 13, 14, 15 обозначаются буквами A, B, C, D, E, F соответственно.

Конечно же существует несколько способов(алгоритмов) перевода числа из одной системы в другую

Алгоритм замещения(далее)

2)ручной перевод чисел из десятичной системы в другую;

-для перевода целых чисел используется алгоритм деления:

осуществляется последовательное деление исходного числа на 2 и собираются остатки(коэффициенты нового разложения), начиная с последнего. Деление длится до получения частного, меньшего основания системы.

Например:

25|2

- 24|-----

---| 12|2

1| -12|----- 25(10)=11001(2)

----| 6|2

0| -6|---

---| 3|2

0| -2|----

--| 1

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

Например:

0, |125*2

---|---------

0 | 250*2 0, 125(10)=0, 001(2)

0 |500*2

1 |000

(по аналогии и в остальных системах счисления)

*Перевод неправильных дробей осуществляется отдельно для целой и дробной части

Понятие о смешанных(промежуточных) системах исчисления(НАСТЯ)

Техника быстрого перевода из двоичной в другую(НАСТЯ)

Арифметические операции в различных системах счисления

Двоичное вычитание:

0-0=0

1-0=1

1-1=0

10-1=1

при вычитании в данном разряде при необходимости занимается единица из следующего старшего разряда, эта занимаемая единица равна двум единицам занимаемого старшего разряда.

110111, 01 110111, 01

- 1011, 10 - 1011, 10

------------- -------------

100011, 11 11111, 11

Сложение:

0+0=0

1+0=1

1+1=10

В операции сложения, аналогично, при переполнении число переносится в старший разряд:

01 110111, 01

+11 + 10011, 01

–- --------------

100 1001010, 10

Разумеется, данные операции применимы и для остальных систем счисления

в восьмеричной: в шестнадцатеричной:

67 D7 37, 4

+ 1 + 9 -13, 8

----- ------ ---------

70 E0 23, C

I Алгоритм замещения(алгоритм подбора коэффициентов)

Из десятичной в другие

1)Выберем систему счисления, в которую хотим перевести число(допустим р)

2)Найдем k и коэффициент α, так что умещалось в данное число.

3)Вычитаем из данного числа

4)Проделываем тоже самое для k-1, k-2…до тех пор пока данное число не станет равно 0.

5)Выписанные коэффициенты и есть данное число в выбранной системе счисления p.

II Промежуточные (смешанные) системы счисления.

В качестве смешанной системы счисления целесообразно использовать системы с основанием существенно упрощающий преобразование информации из системы в двоичную и наоборот.

Теорема

Если (где Q, P, k-целые), то запись любого числа в смешанной системе счисления (Q-P) тождественно совпадает с записью этого числа в системе счисления с основанием Q

Пример

⇐ Предыдущая 1 23