Массовость (универсальность).
Возможность использования данного алгоритма для решения не только данной конкретной задачи, но и для всех иных однотипных задач.
Результативность (сходимость).
Конечный результат должен быть получен после выполнения определённого не бесконечного количества шагов.
Наибольшей наглядностью обладает алгоритм представленный в виде блок-схемы. Элементарные действия подразделяются на классы. Каждый класс имеет свое графическое изображение на схеме - блок. Внутри изображения указывается конкретное действие.
Основные обозначения приведены в приложении 1. Существуют и другие, отражающие специфику элементарных действий.
Отдельные блоки связываются линиями, определяя порядок вызова элементарных операций. От блока к блоку можно переходить только по линии связи. По одной и той же линии связи можно двигаться только в одном направлении, которое в случае неоднозначности задается стрелкой. Допускается объединение нескольких последовательно стоящих блоков одного класса в один.
Существуют стандартные структуры соединения блоков. Это последовательностные структуры (рис.2.1), когда блоки просто вызываются друг за другом. Ветвящиеся структуры - это структуры с возможностью нескольких вариантов продолжения (рис. 2.2). Циклические структуры, когда одни и те же действия повторяются несколько раз с небольшими изменениями.
Алгоритм должен иметь один оператор "начало" и один оператор "конец". Пойдя по любому переходу, в конце концов, надо прийти к блоку "конец". Каждый переход должен быть определён однозначно. Следует обращать внимание, чтобы при всех допустимых изменениях переменных можно было выйти, в конце концов, из цикла (не допускать зацикливания программы). Любой переменной до использования необходимо присвоить значение (она должна быть определена).
|
|
|
Иногда блок-схему алгоритма дополняет словесное описание, необходимое для более чёткого представления действий, выполняемых отдельным блоком и группой блоков. Словесное описание сделать легче, если блоки пронумеровать.
На основании составленного алгоритма пишется программа на конкретном языке программирования.
Для сложных задач не сразу можно определить набор и последовательность необходимых элементарных действий. В таком случае основную задачу разбивают на ряд более мелких подзадач. В свою очередь, любую подзадачу (программный модуль) можно разбить на ещё более мелкие. Это дробление может продолжаться до тех пор, пока не станет ясен алгоритм реализации, упрощенной в очередной раз задачи. Такой метод получил название - декомпозиция.
При этом надо чётко определить, какие из параметров и переменных будут передаваться от программного модуля более высокого уровня - модулю более низкого уровня и обратно.
|
|
|
При очередном разбиении на очередном уровне может быть обнаружено, что некоторые из подзадач этого или разных уровней выполняют одни и те же функции, только может быть с очень небольшими изменениями или над разными переменными. Видимо и алгоритм их будет сходен. Такие подзадачи целесообразно объединить, и в дальнейшем рассматривать как одну. Подобные объединения могут быть реализованы в виде подпрограммы.
Это позволяет сократить количество рассматриваемых модулей, уменьшить размер программы и тем самым увеличить её эффективность. Делает итоговый алгоритм более наглядным и читаемым.
Такой подход получил название модульной структуризации.
После того, как нам становится ясен алгоритм реализации всех программных модулей и структура передаваемых из модуля в модуль данных, можно приступать к написанию программы на выбранном языке программирования. При этом написание программы лучше начинать с модулей более высокого уровня, постепенно опускаясь в модульной структуре и решая более частные задачи. При движении же снизу вверх менее очевидны связи между модулями, и больше вероятность допустить ошибку. Исправление этой ошибки может потребовать переделки всех уже ранее созданных модулей более низкого уровня.
|
|
|
Для написания программы на конкретном языке программирования необходимо знать синтаксис языка (зарезервированные слова), стандартные конструкции языка, структуру программ для данного языка программирования, структуру самого языка (его отдельные модули, внешние библиотеки), состав его стандартных функций и процедур. Необходимо освоить средства разработки данного языка (интегрированная среда, редактор, компилятор).
Рекомендуется каждый программный модуль писать и отлаживать отдельно с последующим присоединением его к остальной программе.
После ввода в компьютер текста программного модуля необходимо произвести компиляцию. При компиляции может быть выявлено большинство ошибок не связанных с алгоритмом(синтаксические, явные противоречия в структуре и назначении переменных, не предусмотренные средствами языка использования переменных и т.д.). После внесения исправлений в текст модуля компиляцию необходимо повторить.
Следующий этап создания программного модуля - тестирование. Этот этап включает в себя прогонку программы с конкретными входными значениями, в том числе и в пошаговом режиме, сравнение полученных результатов с результатами контрольного просчета. Выявление и исправление ошибок алгоритма.
|
|
|
После успешного тестирования модуль может быть включен в модуль более высокого уровня или основную программу. Необходимо производить тестирование и после соединения модулей.
Для контрольных просчетов необходимо использовать исходные данные, позволяющие проверить все ветвления алгоритма. При необходимости следует сделать несколько контрольных просчетов с различными исходными данными. В качестве исходных не следует выбирать данные, приводящие к очевидным результатам. Необходимо обращать внимание на область определения используемых в программе функций (получаемые в ходе работы аргументы не должны выходить за пределы области). Рекомендуется на этапе тестирования проверять правильность восприятия введенных или переданных данных.
После тестирования программа считается отлаженной, текст ее распечатывается и вместе с контрольными решениями подшивается к отчету.
3 Краткие сведения о языке программирования
Общая структура программ
Простейшая программа на языке С выглядит так:
void main() { }
Операторы программы вставляются между фигурными скобками {} и выполняют действия основной(главной) функции программы. Некоторая информация может быть указана до main.
Более общая структура программы как правило содержит следующие элементы:
#include <имя заголовочного файла>
И таких объявлений (директив препроцессора) может быть несколько. Заголовочный файл содержит описание функций, констант, типов и т.д., которые используются в программе, в том числе и из стандартных библиотек языка.
#define имя замещение
Директива препроцессора, задающая константы.
Объявления глобальных переменных и типизированных констант.
Опережающее объявление функций.
Основная функция main().
Определения функций
Условный оператор – оператор IF
if(условие) оператор1;
else оператор2;
Условие представляет собой логическое выражение, результат которого ЛОЖЬ (0) или ИСТИНА (не нулевое целое).
Например :
if((а <5)&& (b<7)) a=b+2;
else b+ =2;
В случае если условие истинно, то выполняется оператор1 (a=b+2) иначе оператор2 (b=b+2). Перед ключевым словом else ставится точка с запятой. Существуют конструкции, когда ключевое слово ELSE отсутствует:
Например: if(a==5) a=0;
Если в случае выполнения или невыполнения условия надо выполнить несколько операторов, оператор 1 или 2 делается составным. Он начинается с { и заканчивается }.
if( а<0){
a=5;
b=7
}
else {
b=0;
a=7;
}
На практике часто используется конструкция if else if, в которой в случае не выполнения первого условия, после else идет проверка другого условия и т.д.
Например:
if(а >5 ) k =1 ;
else if( а <5) k=-1;
else if( а==5) k=0;
Оператор множественного выбора switch
Если вариантов для сравнения много, вместо многочисленных конструкций if else if рациональнее использовать оператор switch.
switch( переменная или выражение)
{ case значение1: оператор1;
break;
case значение2: оператор2;
break;
--------------------------
default: оператор для случая, когда не сработал ни один из наборов значений
}
Если значения переменной или выражения равны значению1 выполняется оператор1, значению2 – оператор2 и т.д. Если не входит не в один из наборов выполняется оператор после default. Операторов при значении может быть и несколько. При этом их не надо оформлять как составной. Концом этих выполняемых операторов является оператор break. В качестве значения переменной или выражения может выступать значение любого перечислимого типа. При задании наборов значений с одинаковой реакцией программы их можно указывать с помощью нескольких case без операторов:
case ‘A’: case ‘B’: case ‘C’: оператор обработки в случае ‘A’, или ‘B’, или ‘C’.
Начиная с ключевого слова default, часть оператора не обязательна и может отсутствовать.
Оператор цикла с предусловием while
while (условие повторения цикла) оператор;
Условие проверяется всякий раз перед выполнением оператора. Оператор выполняется если условие истинно после чего вновь возвращается на проверку условия. Если условие не выполняется переходим к оператору стоящему за оператором цикла. Оператор в цикле может быть составным и даже содержать другие вложенные циклы.
Оператор цикла с постусловием do while
do
оператор;
while( условие повторения цикла);
В отличие от оператора while сначала выполняется оператор потом делается проверка на повторения цикла. Если условие истинно то цикл повторяется. Иначе- выход из цикла.
Счетный цикл for
for( имя переменной цикла:=нач.знач., другие операции до вхождения в цикл;
условие повторения цикла;
действия в конце каждого повторения цикла)
оператор;
Например:
for(I=1; I<=10; I++) A= A+ I;
Оператор представляющий тело цикла, может быть и составным.
Инструкции безусловного перехода goto
goto метка;
Метка – это идентификатор, помечающая оператор который должен быть выполнен после оператора, предшествующего goto.
В тексте программы метка ставится перед инструкцией, которая должна быть выполнена после инструкции goto. Сразу после метки ставится двоеточие.
метка: оператор;
Запрещены переходы по метке между подпрограммами.
Подпрограммы(функции)
Структурное программирование предполагает такой стиль создания программ, при котором её легче написать, тестировать, понять и изменить. Алгоритм программы рассматривается, как последовательность отдельных блоков или модулей, каждый из которых решает свою конкретную задачу. Для каждого модуля определяется набор действий и переменных, необходимых для решения задачи модуля. Модуль может представлять собой набор других подмодулей решающих более частные задачи. Следует избегать использования в модуле переменных и подмодулей не принимающих участие в решении задачи данного блока. Такой подход хорошо сочетается с методом декомпозиции, который широко используется для решения разнообразных задач проектирования.
Суть метода. Решение задачи представляется как выполнение ряда шагов. В начале не ясно какие шаги и в какой последовательности предпринимать. Тогда задачу разбивают на ряд более мелких подзадач, выполнение которых приводит к решению основной, более общей задачи. В свою очередь подзадачи ,если решения их не очевидно, могут быть разбиты на подзадачи более низкого уровня. Это разбиение продолжается до тех пор, пока последовательность шагов, приводящих к решению очередной подзадачи не становится очевидными.
Часто подзадачи называются модулями. При конкретном техническом воплощении, предпочтительнее считается разработка текста программы от модулей более общего характера (верхнего уровня) к частным, - сверху вниз. Этот метод получил название нисходящего проектирования. При его использовании лучше видна структура решения задачи. Это позволяет избежать ряд ошибок и неточностей.
При анализе модулей можно будет заметить, что ряд их производит одни и те же действия но над разными данными или имеют небольшие отличия. Такие модули оформляются в виде подпрограмм, которым сообщают с какими данными и когда именно работать. Использование подпрограмм существенно сокращает размер программы и улучшает ее читаемость.
В языке С все подпрограммы - функции. По традиции определение функций(задание их алгоритмов с помощью операторов языка) помещается после функции main. Перед функцией main для проверки правильности использования помещают заголовки функций(опережающие описания). Структура заголовка:
Тип возвращаемого значения имя функции(тип параметра1 имя1, тип параметра2 имя2, и т. д.);
Функция возвращает как минимум одно значение задаваемого типа с помощью оператора return. Если функция ничего не возвращает – тип этого значения указывается void.
После объявления функции следует тело функции. Структура тела ничем не отличается от структуры функции main.
Константы, переменные объявленные внутри подпрограммы называются локальными и могут быть использованы только внутри этой подпрограммы. Описанные параметры в объявлении подпрограммы рассматриваются как локальные переменные которые при вызове подпрограммы должны быть проинициализированы подставляемыми значениями. Но для того, чтобы задать обработку, параметрам дают формальные имена при описании подпрограмм. Поэтому их иногда называют формальными параметрами. При вызове же, на их место подставляются конкретные значения или переменные (реальные параметры). Заданные в заголовке формальные параметры передаются по значению. Для изменения переменных основной программы, они передаются в подпрограмму по ссылке или через указатель. Наиболее рациональным способом является работа через указатели. Этот способ также используется для передаче в подпрограмму больших параметров – массивов и структур. Для вызова, использования, подпрограммы указывается ее имя и подставляются фактические, реальные параметры на место формальных с соблюдением последовательности и типов, как это указано при объявлении функции.
Пример:
char N;/*глобальная переменная*/
float count( int I, float * a);/*опережающее описание функции count: i – параметр для передачи в функцию значения, a – указатель на float(для возврата вычисленного значения), еще одно значение типа float возвращается как возвращаемое функцией.*/
………………………………………
void main()/* Основная программа*/
{ float S, f, hh;/* локальные переменные главного блока программы*/
S=0; f=10; N=5;/*присвоение начальных значений*/}
f= count( N,& S);/*первый вызов функции n –вместо i,адрес S(указатель на S) – вместо a , f –запоминает значение, возвращаемое функцией*/
/*Результат: N=5, S=28, f=5040. Видим, что N –не изменилось, S и f –изменились*/
………………………………………
f= count(7, & S);/*Повторные вызовы функции в ходе работы программы. На место параметра, передаваемого по значению можно подставить и константу*/
………………………………………
hh=count(N, &S);
}
float count(int I, float *a);/* определение функции */
{
char K; /*локальная переменная*/
float b;
i+=2;{изменяем i}
b=1;
for( K=1; K<= i;K++)
{
* a+= K;/*изменяем значение, хранящееся по указателю a*/
b*= K;/* изменяем b*/
}
return b;/* возвращаем значение функции*/
}/*конец функции*/
Оператор return позволяют завершить подпрограмму в любом месте не доходя до конца.
4. Лабораторная работа №1
“Системы счисления”
Цель работы: получение практических навыков перевода чисел между различными системами счисления, а также выполнения арифметических операций в различных системах счисления.
Теоретическая часть
Системы счисления
Системы счисления разделяются на позиционные и непозиционные. Примером непозиционной системы счисления является римская система. Непозиционные системы счисления практически непригодны для выполнения арифметических операций.
Примером позиционной системы счисления является привычная для нас десятичная система.
Пусть число, записанное в произвольной позиционной системе счисления, имеет n+1 цифру в целой части и m цифр в своей дробной части:
an, an-1, an-2,..., a2, a1, a0, b1, b2,...,bk,
где a i - i-ая цифра целой части, b j - j-ая цифра дробной части числа.
Тогда значение этого числа можно представить в виде
an*рn + an-1*pn-1 +...+ a1*p1 + a0*p0 + b1*p-1 + b2*p-2 +...+ bk*p-k,
где p - основание системы счисления.
Например, для десятичного числа имеем
83887,45 = 8*104 + 3*103 + 8*102 + 8*101 + 7*100 + 4*10-1 + 5*10-2.
В ЭВМ наиболее часто применяются двоичная, восьмеричная и шестнадцатеричная системы счисления (2, 8 и 16 c/c). При этом восьмеричная и шестнадцатеричная системы счисления используются, как правило, для компактной записи двоичных чисел.
Основанием двоичной системы счисления является число 2. Количество цифр, используемых для изображения чисел в любой системе счисления, равно основанию этой системы. В 2 с/с для этой цели используются цифры 0 и 1.
Рассмотрим произвольное двоичное число
11010,101 = 1*24 + 1*23 + 0*22 + 1*21 + 0*20 + 1*2-1 + 0*2-2 + 1*2-3 =
= 16 + 8 + 2 + 1/2 + 1/8 = 26 5/8 = 26,625 (10 с/с)
Представленная выше схема разложения двоичного числа является одновременно схемой перевода из 2 с/с в 10 c/c ( 2 --> 10 ).
Рассмотрим теперь перевод 10 --> 2. Такой перевод производится отдельно для целой и отдельно для дробной частей числа.
Пример. 43,37510 = 101011,0112
43 ¦ 2
42 21 ¦ 2
1 20 10 ¦ 2
1 10 5 ¦ 2
0 4 2 ¦ 2
1 2 1 ¦
0 ¦
<--------------
Деление производится до тех пор, пока не будет получено частное, меньшее делителя. После этого цифры частного и остатков записываются в обратном порядке. В данном случае получим 101011.
Тогда можно записать:
1*25 + 0*24 + 1*23 + 0*22 + 1*21 + 1*20,
т.е. мы получили разложение числа по степеням основания 2.
Для перевода дробной части будем последовательно умножать на 2 исходное число и дробные части получаемых в процессе преобразования чисел до тех пор, пока дробная часть очередного числа не станет равной нулю.
0, ¦ 375 * 2
0, ¦ 75 * 2
1, ¦ 5 * 2
1, ¦ 0
Следовательно, 0,37510 = 0,0112.
Конечная десятичная дробь не всегда образует конечную двоичную дробь.
Основанием восьмиричной системы является число 8. Для изображения числа используются 8 цифр: 0 - 7.
Перевод 10 --> 8 . Схема перевода может использоваться такая же, как и для 2 с/c, но с делением на 8 соответственно.
Перевод 8 --> 2. Для перевода восьмеричного числа в 2 c/c нужно каждую восьмеричную цифру записать в виде двоичной триады, т.е. трех двоичных цифр.
| Восьмеричное число | Двоичное число | Двоичная триада |
| 0 | 0 | 000 |
| 1 | 1 | 001 |
| 2 | 10 | 010 |
| 3 | 11 | 011 |
| 4 | 100 | 100 |
| 5 | 101 | 101 |
| 6 | 110 | 110 |
| 7 | 111 | 111 |
Например, 3763,248 = 011 111 110 011 , 010 1002 = 11111110011,01012
Такое правило перевода 8 --> 2 связано с тем, что 8 = 23.
Для перевода 2 --> 8 следует разделить двоичное число влево и вправо от запятой на триады, а затем заменить каждую триаду одной восьмеричной цифрой. Если первая триада в целой части или последняя триада в дробной части числа получаются неполными, то нужно дополнить их незначащими нулями.
Основанием шестнадцатиричной системы является число 16. Для изображения числа нужно использовать 16 цифр. Так как цифр 0 - 9 недостаточно, то для остальных цифр используются первые буквы латинского алфавита: A (цифра 10), B (цифра 11), C (цифра 12), D (цифра 13), E (цифра 14), F (цифра 15).
Перевод 16 --> 10:
A8B7,E16 = 10*163 + 8*162 + 11*161 + 7*160 + 14*16-1 = 10*4096 + 8*256 + 11*16+ + 7 + 14/16 = 43191,87510.
Перевод 16 --> 2 . Так как 16 = 24 , то в этом случае каждая шестнадцатеричная цифра должна быть представлена двоичной тетрадой.
| 16-ричное число | Двоичное число | Двоичная тетрада | 16-ричное число | Двоичное число | Двоичная тетрада |
| 0 | 0 | 0000 | 8 | 1000 | 1000 |
| 1 | 1 | 0001 | 9 | 1001 | 1001 |
| 2 | 10 | 0010 | A | 1010 | 1010 |
| 3 | 11 | 0011 | B | 1011 | 1011 |
| 4 | 100 | 0100 | C | 1100 | 1100 |
| 5 | 101 | 0101 | D | 1101 | 1101 |
| 6 | 110 | 0110 | E | 1110 | 1110 |
| 7 | 111 | 0111 | F | 1111 | 1111 |
Пример.
D85CA,9B 16 = 1101 1000 0101 1100 1010, 1001 1011 2
Перевод 2 --> 16. В этом случае исходное число нужно разделить влево и вправо от запятой на тетрады, а затем каждую тетраду записать одной шестнадцатеричной цифрой.
Пример.
11¦1011¦1110¦0001¦,0110¦1102 = 3BE1,6C16
Для сокращения вычислений
вместо 10 --> 2 выполняют 10 --> 16 --> 2 ,
вместо 2 --> 10 выполняют 2 --> 16 --> 10 .
Дата добавления: 2019-09-13; просмотров: 1487; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!