Понятие и свойства алгоритма

2 1

3 2 1

2 1

3 2 1

2 1

5 4 3 2 1

Двоичная арифметика.

Правила сложения:

Пример. Сложить двоичные числа 1101₂ и 11011₂.

Запишем слагаемые в столбик и пронумеруем разряды, присвоив младшему разряду номер 1:

номера разрядов:

+ 1 1 0 1

1 1 0 1 1

Процесс образования результата по разрядам описан ниже:

1. разряд 1 формируется следующим образом: 1 + 1 = 10; 0 остается в разряде 1, 1 переносится во второй разряд;
2. разряд 2 формируется следующим образом: 0 + 1 + 1 = 10, где вторая 1 - единица переноса; 0 остается в разряде 2, 1 переносится в третий разряд;
3. третий разряд формируется следующим образом: 1 + 0 + 1 = 10, где вторая 1 - единица переноса; 0 остается в разряде 3, 1 переносится в разряд 4;
4. четвертый разряд формируется следующим образом: 1 + 1 + 1 = 11, где третья 1 - единица переноса; 1 остается в разряде 4, 1 переносится в пятый разряд;
5. пятый разряд формируется следующим образом: 1 + 1 = 10; где вторая 1 - единица переноса; 0 остается в разряде 5, 1 переносится в шестой разряд.

Таким образом:

1 1 0 1

+ 1 1 0 1 1

1 0 1 0 0 0

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

Поскольку 13 + 27 = 40, двоичное сложение выполнено верно.

Пример. Сложить шестнадцатеричные числа 1С₁₆ и 7В₁₆.

Запишем слагаемые в столбик и пронумеруем разряды, присвоив младшему разряду номер 1:

номера разрядов:

+1 С

7 В

Процесс образования результата по разрядам описан ниже (он включает преобразование в процессе сложения каждой шестнадцатеричной цифры в десятичное число и обратные действия):

1. разряд 1 формируется следующим образом: С₁₆ + В₁₆ = 12 + 11 = 23 = 17₁₆; 7 остается в разряде 1; 1 переносится в разряд 2;
2. разряд 2 формируется следующим образом: 1₁₆ + 7₁₆ + 1₁₆ = 9₁₆, где вторая 1₁₆ - единица переноса.

Таким образом:

1 С

+7 В

9 7

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

Поскольку 28 + 123 = 151, сложение выполнено верно.

Правила вычитания:

Пример. Вычесть из двоичного числа 101₂ двоичное число 11₂.

Запишем алгебраические слагаемые в столбик в порядке "уменьшаемое - вычитаемое" и пронумеруем разряды, присвоив младшему разряду номер 1:

номера разрядов:

-1 0 1

1 1

Процесс образования результата по разрядам описан ниже:

1. разряд 1 формируется следующим образом: 1 - 1 = 0;
2. разряд 2 формируется следующим образом: поскольку 0 меньше 1 и непосредственное вычитание невозможно, занимаем для уменьшаемого единицу в старшем разряде 3. Тогда разряд 2 рассчитывается как 10 - 1 = 1;
3. третий разряд формируется следующим образом: поскольку единица была занята в предыдущем шаге, в разряде остался 0.

Таким образом:

1 0 1

- 1 1

1 0

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

По Таблица 7.2 имеем:

101₂ = 5;

11₂ = 3;

10₂ = 2.

Поскольку 5 - 3 = 2, вычитание выполнено верно.

Пример. Вычесть из шестнадцатеричного числа 97₁₆ шестнадцатеричное число 7В₁₆.

Запишем алгебраические слагаемые в столбик в порядке "уменьшаемое - вычитаемое" и пронумеруем разряды, присвоив младшему разряду номер 1:

номера разрядов:

-9 7

7 В

Процесс образования результата по разрядам описан ниже:

1. разряд 1 формируется следующим образом: поскольку 7 меньше В и непосредственное вычитание невозможно, занимаем для уменьшаемого единицу в старшем разряде 2. Тогда 17₁₆ - В₁₆ = 23 - 11 = 12 = С₁₆;
2. разряд 2 формируется следующим образом: поскольку единица была занята в предыдущем шаге, разряд 2 уменьшаемого стал равным 8₁₆. Тогда разряд 2 рассчитывается как 8₁₆₆ - 7₁₆ = 1₁₆.

Таким образом:

9 7

-7 В

1 С

Вычитание выполнено верно (см. пример про сложение).

Правила умножения:

Пример. Умножить двоичное число 101₂ на двоичное число 11₂.

Запишем множители в столбик и пронумеруем разряды, присвоив младшему разряду номер 1:

номера разрядов:

1 0 1

1 1

Процесс образования результата по шагам умножения множимого на каждый разряд множителя с последующим сложением показан ниже:

1. умножение множимого на разряд 1 множителя дает результат: 101₂ * 1₂ = 101₂;
2. умножение множимого на разряд 2 множителя дает результат: 101₂ * 10₂ = 1010₂. Здесь значение разряда 2 множителя сформировано по принципам формирования значения числа в позиционных системах счисления;
3. для получения окончательного результата складываем результаты предыдущих шагов: 101₂ + 1010₂ = 1111₂.

Для проверки результата найдем полное значение сомножителей и произведения (см. Таблица 7.2):

101₂ = 5;

11₂ = 3;

1111₂ = 15.

Поскольку 5 * 3 = 15, умножение выполнено верно.

Пример. Умножить шестнадцатеричное число 1С₁₆ на шестнадцатеричное число 7В₁₆.

Запишем множители в столбик и пронумеруем разряды, присвоив младшему разряду номер 1:

номера разрядов:

1 С

7 В

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

1. умножение множимого на разряд 1 множителя дает результат: 1С₁₆ * В₁₆ = 28 * 11 = 308 = 134₁₆;
2. умножение множимого на разряд 2 множителя дает результат: 1С₁₆ * 7₁₆ = 28 * 112 = 3136 = С40₁₆. Здесь значение разряда 2 множителя сформировано по принципам формирования значения числа в позиционных системах счисления;
3. для получения окончательного результата складываем результаты предыдущих шагов: 134₁₆ + С40₁₆ = D74₁₆.

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

1С₁₆ = 28;

7В₁₆ = 123;

.

Поскольку 28 * 123 = 3444, умножение выполнено верно.

Правила деления:

Рассмотрим правила деления только для двоичных чисел, поскольку деление шестнадцатеричных чисел проще выполнять, переведя их предварительно в десятичную систему счисления.

Пример. Разделить двоичное число 1111₂ на двоичное число 11₂.

Решение задачи представим схемой:

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

1111₂ = 15;

11₂ = 3;

15 / 3 = 5;

5 = 1012.

Деление выполнено верно.

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

Алгоритмизация:

1. Этап решения задачи, заключающийся в конструировании алгоритма решения на основе условия задачи и ее требований к конечному результату;

2. Раздел информатики, изучающий методы и приемы построения алгоритма, а также их свойства.

Алгоритмизация задачи – это процесс разработки (проектирования) алгоритма для решения задачи с помощью ЭВМ.

Рассмотрим предварительно простую жизненную ситуацию: что следует сделать, если нужно привлечь к решению задачи человека, не знакомого с её решением?

Очевидно, в таком случае его надо научить. Каким образом?

1. Выбирают метод (способ, порядок) решения задачи и изучают его во всех подробностях;

2. Сообщают исполнителю выбранный метод в абсолютно понятном для него виде;

3. Исполнитель решает задачу строго в соответствии с методом.

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

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

Второй этап значительно сложнее. Дело в том, что если способ (метод решения) задачи описан произвольно, нет гарантии, что он будет правильно понят исполнителем. Поэтому описание метода следует выполнять в соответствии с определёнными правилами, а именно:

- выделить величины, являющиеся исходными для задачи;

- разбить процесс решения задачи на такие этапы, которые известны исполнителю и которые он может выполнить однозначно без всяких пояснений;

- указать порядок выполнения этапов;

- указать признак окончания процесса решения задачи;

- указать во всех случаях, что является результатом решения задачи.

Описание метода, выполненное в соответствии с этими правилами, называется алгоритмом решения задачи. Составить такое описание обычно нелегко, но, следуя ему, механически выполняя все указанные в нём этапы в требуемом порядке, исполнитель может всегда правильно решить задачу. Итак, мы пришли к центральному понятию информатики – алгоритму.

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

Дата добавления: 2014-01-06