Алгоритмы и способы их описания Понятие алгоритма - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
4. Перечень экзаменационных тем Дисциплина «Алгоритмы и их сложность» 1 69.64kb.
Алгоритмы и программирование Урок 1 Понятие алгоритма. Линейные алгоритмы 1 168.58kb.
Вопросы к зачету «Теория алгоритмов» 1 7.27kb.
Программа «Системы корпоративного управления» 1 50.59kb.
Команд исполнителя (на примере учебного исполнителя). Свойства алгоритма. 1 119.82kb.
введение. 3 Понятие алгоритма и его свойства. 4 Способы описания... 6 515.83kb.
М. В. Ломоносова Специальность "Физика атомного ядра и частиц" Билет... 1 219.98kb.
Алгоритмы и способы повышения точности работы системы ориентации... 1 311.94kb.
Лабораторная работа №1 "исследование одноключевых блочных криптографических... 1 45.8kb.
1 краткая история возникновения квантовой механики 1 253.19kb.
Лабораторная работа №4 «симметричные криптоалгоритмы» Студенты гр. 1 100.25kb.
Лекция №2 (16. 02. 10) Определение 4 1 51.47kb.
Направления изучения представлений о справедливости 1 202.17kb.

Алгоритмы и способы их описания Понятие алгоритма - страница №8/9

Таблица 1


вар.

Функция


Изменения аргумента

Параметр



y=

X Є[1,15] ∆x=1

a=2.01, 3.5, 5.8




y=

X Є[0.1,2.0] ∆x=0.3

a=0.325, 0.4, 0.425 b=1.3



y=

X Є[0.75,1.1] ∆x=0.05

a=0.3, 0.4, 0.5, 0.6



y=

X Є[0.25, 1.75] ∆x=0.5

a=0.125, 0.325, 0.525


y=

X Є[7.5,12] ∆x=0.5


a=0.3, 0.05, 0.015 b=0.05



y=

X Є[0.1,0.25] ∆x=0.01

a=1, 2, 3, 4



y=

X Є[1,4.6] ∆x=0.4

a=2, 5, 8, 11



y=

X Є[0.1,1.9] ∆x=0.4

a=0,1, 2, 3 b=1.1



y=

X Є[0.3,1.0] ∆x=0.1

a=1, 7.5, 14 b=1.8



y=

X =

a=0.5, 0.6, 1.0, 1.2



y=

X Є[0.05,0.3] ∆x=0.05

a=0.2, 0.35, 0.75



y=

X Є[0.8,1.6] ∆x=0.1

a=1.5, 2.1, -3.8 b=0.15



y=

X Є[1,2] ∆x=0.2

a=2.8, -3.1, -0.5



y=

X Є[0.5, 2] ∆x=0.5

a Є[0.5, 2.0] ∆a=0.5 b=1.3



y=

X Є[0.1, 1] ∆x=0.2

a Є[2, 2.6] ∆a=0.2



y=

X Є[0.1, 1] ∆x=0.2

a Є[0.3, 0.5] ∆a=0.1 b=3.3



y=

X Є[1,5] ∆x=0.5

a Є[1.5, 3.5] ∆a=1



y=

X Є[0.2, 2.8] ∆x=0.4

a=2.3, 3.7, 4,1 b=1.8



y=

X Є[0.1,1] ∆x=0.2

a Є[1.5, 4.5] ∆a=1.5



y=

t Є[0.1,3] ∆t=0.3

a [-0.5, 4.5] ∆a=1.5



y=

X Є[7.5,12] ∆x=0.5

a=0.3, 0.05, 0.015 b=0.05



y=

X Є[0.1,0.25] ∆x=0.01

a=1, 2, 3, 4



y=

X Є[1,4.6] ∆x=0.4

a=2, 5, 8, 11



y=

X Є[0.1,1.9] ∆x=0.4

a=0,1, 2, 3 b=1.1



y=

X Є[0.3,1.0] ∆x=0.1

a=1, 7.5, 14 b=1.8

12.11. Указатели и массивы

12.11.1. Указатели

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

Начнем с того, что поговорим о структуре памяти любого компьютера. Как известно, память компьютера представляет последовательность 8-битовых байтов. Каждый байт пронумерован, причем нумерация начинается с нуля. Номер байта называется адресом. Иногда говорят, что адрес указывает на определенный байт. Таким образом, указатель является просто адресом байта памяти.

Язык Си позволяет определять переменные, которые могут хранить адреса памяти. Такие переменные и называются указателями. Значение указателя сообщает о том, где размещен объект, но ничего не говорит о значении самого объекта.

Указатель

Объект

Данные или группа данных



Присваивая указателю то или иное допустимое значение, можно обеспечить доступ к желаемым данным через этот указатель.

Для описания переменной типа указатель используется символ *.



Формат описания:

Тип *имя;

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

Напимер:


int *x;

char *y;


Пример следует понимать, что x – это указатель на ячейку, в которой хранится целое значение, а y – указатель на однобайтовую ячейку, предназначенную для хранения символа.

Двумя наиболее важными операциями, связанными с указателями, являются операция обращения по адресу * и определение адреса &.

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

Например:

int *x;

. . .


*x=5;

Операция определения адреса & возвращает адрес памяти своего операнда. Операндом должна быть переменная.

Напимер:

int *x;


int a=5;

x=&a;


Кроме того, над указателями можно выполнять арифметические операции сложения и вычитания.

Если у – указатель на целое, то унарная операция y++ увеличивает значение адреса, хранящегося в переменной-указателе на число равное размеру ячейки целого типа, т.е. на 2 байта; теперь оно является адресом следующей ячейки целого типа. Соответственно, оператор y-- означает, что адрес уменьшается на 2 байта.

Указатели и целые числа можно складывать. Конструкция у + n (у - указатель, n - целое число) задает адрес n-гo объекта, на который указывает у. Это справедливо для любых объектов (int, char, float и др.); транслятор будет масштабировать приращение адреса в соответствии с типом, указанным в определении объекта.

Любой адрес можно проверить на равенство (= =) или неравенство (!=), больше (>) или меньше (<) с любым другим адресом.

Рассмотрим следующий фрагмент программы:

#include

main()

{

int *x, *w;



int y;

*x=16;


y=-15;

w=&y;


. . .

}

Этот текст можно понимать так:



Выделить память под три переменные x, w, y, где x и w –переменные типа указатель. Оператор *x=16; означает, что в ячейку, адрес которой записан в х, помещается значение 16. Затем переменной у присваивается значение -15. После чего в указатель w записывается адрес переменной y. Синтаксически текст записан правильно. Проблема заключается в том, что указатель х не инициализирован. Описание int *x; приводит к тому, что компилятор резервирует память, необходимую для хранения адреса целой ячейки, но адрес в этой ячейки может быть любой, в том числе и адрес, где хранится полезная информация, например, операционная система. Запись в такую ячейку может привести к сбою в работе компьютера. Поэтому при работе с указателями их надо правильно инициализировать. Существует 4 способа правильного задания начального значения для указателя:

1) Описать указатель глобально, т.е. вне любой функции. При этом указатель будет инициализирован безопасным нулевым адресом. Кроме того любому указателю можно присвоить безопасный нулевой адрес, например:

int *x;

char *y=0;



x=NULL;

Гарантируется, что этот адрес не совпадет ни с одним адресом, уже использованным в системе.

2) Присвоить указателю адрес переменной. Например: w=&y;

3) Присвоить указателю значение другого указателя, к этому моменту правильно инициализированного. Например: x=w;

4) Использовать функции выделения динамической памяти malloc() и calloc(). При использовании этих функция необходимо подключать библиотеку . Рассмотрим пример использования функции malloc():

x=(int*)malloc(sizeof(int));

Приведенный пример означает, что функция выделит область памяти, размер которой определит функция sizeof(). Если вы знаете размер ячейки заданного типа, то можно написать проще: x=(int*)malloc(2);

По окончанию работы программы, память, выделенную функцией malloc() рекомендуется освободить функцией free(x);

И так, вернемся к приведенному ранее фрагменту программы:

#include

main()

{

int *x, *w;



int y;

x=(int*)malloc(sizeof(int));

*x=16;

y=-15;


w=&y;

. . .


}

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



12.11.2. Понятие массива

Массив представляет собой упорядоченное множества однотипных элементов. В языке Си массив описывается переменной сложной структуры. При описании массива необходимо указать:



  • способ объединения элементов в структуру (одномерный, двухмерный и т.д. массивы);

  • число элементов;

• тип элементов.

Общий вид описания массива

<тип элементов> имя [число элементов];

Доступ к каждому элементу массива осуществляется с помощью индексов. Индексы задают порядковый номер элемента, к которому осуществляется доступ. В языке Си первый элемент массива имеет индекс ноль. Число индексов определяет структуру массива: если используется один индекс, то такой массив называется одномерным, если два индекса - двухмерным, и т.д. В общем случае размерность массива может быть произвольной.



12.11.3. Одномерные массивы

В математике одномерному массиву соответствует n-мерный вектор, например:



; i = 1, n,

где х, - компонента (координата) вектора;



i - номер компоненты;

п - число компонент.

Описание одномерного массива

На языке Си описание одномерного массива задается следующим образом:



<тип элементов> <имя массива>[размер];

Компилятор отводит под массив память размером (sizeof(тип)*размер) байтов.

Непосредственно при описании можно задать начальные значения массива:

int dat[4]={5,8,-2,11};

float kom[]={3.5,6,-1.1};
Указатели могут обеспечить простой способ ссылок на массив. Имя массива фактически является константой-указателем, ссылающимся на начальный адрес данных (адрес первого элемента массива). Начальный адрес массива определяет компилятор в момент описания массива, и такой адрес не может быть переопределен. Первый элемент массива имеет индекс ноль.

Например:

int Ar[5];

printf (“адрес Ar=%x\n”,Ar);

printf (“адрес Ar=%x\n”,&Ar[0]);

В приведенном фрагменте обе функции printf выводят начальный адрес массива Ar, т.к. выражения Ar и &Ar[0] эквивалентны.



Индексные переменные

Выбор отдельного элемента из массива осуществляется с помощью индексной переменной, которая задается следующим образом:

x[i] - индексная переменная (элемент массива).

Здесь x - имя массива;

i - индекс (номер элемента массива).

В качестве индекса используются:



  • целые константы, например х[2] х2;

  • целые переменные, например х[к] хk;

  • индексные выражения, например х[2*n+1] x2n+1.

Замечание. В языке Си индексы начинаются с нуля. Индексными выражениями являются арифметические выражения целого типа.

Индексная переменная, как и простая; может стоять в левой части оператора присваивания, например:

х[3]=2.5;

Ввод-вывод одномерных массивов

Ввод-вывод массивов осуществляется поэлементно с помощью операторов scanf и printf соответственно и оператора цикла for..., в котором в качестве параметра используется индекс.



Пример 1. Организовать ввод с клавиатуры массива:

A = (1.2, 5,-6.8, 14).

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

void main()

{ float A [4] ;

int i;


В программе ввод массива рекомендуется организовать в виде диалога, поместив перед оператором ввода оператор вывода (printf), в котором дается поясняющее сообщение, например:

printf(“Введите массив А\n”);

for( i = 0; i<4; i++)

scanf(“%f”,&A[i]);

В момент работы оператора scanf на клавиатуре через один или несколько пробелов набираются элементы массива (ввод в строке экрана) и нажимается клавиша [Enter]:

1.2 5 -6.8 14 [Enter]



Замечание. Элементы массива можно вводить в «столбик», если после ввода каждого элемента нажимать клавишу [Enter].

Пример 2. Организовать вывод массива А на экран таким образом, чтобы все элементы располагались на одной строке экрана.

В программе надо записать следующие операторы:

for ( i = 0; i<4; i++)

printf(%5.2f “,A[i]);

printf(“\n”);

Вид выводимого массива на экране:

1.2 5.0 -6.8 14.0

Оператор printf(“\n”); без списка служит для перевода курсора к началу следующей строки.



Обработка одномерных массивов

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



Задача 1. Организация счетчика

Дан целочисленный массив: В = {bi};i=. Определить количество элементов массива, которые делятся на 3 без остатка.

#include

#include

void main()

{

clrscr();



int В [20] ; /* описание массива B*/

int i, L;

printf(“Введите массив В\n”);

for( i =0; i<20; i++)

scanf(“%d”, &B[i]); /* ввод данных в массив с клавиатуры*/

L=0;


for( i =0; i<20; i++)

if (B[i] % 3= = 0) /*проверка элемента на кратность 3*/

L ++;

printf(“Кол-во=%d\n”, L);



}
Задача 2. Накопление суммы и произведения

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



; .

#include

#include

void main()

{

clrscr();



float X [100];

int n, i;

float S=0, P=1;

printf(“Введите размер массива n= “);

scanf(“%d”,&n);

prinf(“Введите массив X\n”);

for( i = 0; i

scanf(“%f”,&X[i]);

for( i=0; i

{

S = S + X[i]; /* вычисление суммы элементов массива Х */



P =P*X[i]; /* вычисление произведения элементов Х */

}

S = S/n; /* вычисление среднего значения Х */



P=exp(l/n*log(P)); /* вычисление среднего геометрического Х */

printf(“S=%6.2f\n”, S);

printf(“P=%10.2f\n”,P);

}

Задача 3. Поиск минимального и максимального элементов массива

Дан вещественный массив: T = {ti}; i=. Поменять местами минимальный и максимальный элементы массива и вывести массив после обмена.

Решение

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

Введем обозначения:

min - минимальный элемент;

imin - индекс минимального элемента;

max - максимальный элемент;

imax - индекс максимального элемента.

#include

#include

#include

void main()

{

clrscr();



float Т [10] ; /* описание массива Т */

int i, imin, imax;

float min, max;

printf(“Введите массив Т\n”);

for( i = 0;i<10;i++)

scanf(“%f”,&T[i]);

min =+1E6;

max =-1E6;

for( i = 0; i<10; i++)

{

if (T[i]

{

min = T[i];

imin=i; /* сохранение номера текущего min */

}

If( T[i]>max)



{

max = T[i];

imax = i; /* сохранение номера текущего max */

}


}

T[imin]=max;

T[imax]= min;

for( i= 0; i<10; i++)

printf(“%6.2f “,T[i]);

printf(“\n”);

}


<< предыдущая страница   следующая страница >>



Если девушка уступает тебе место в трамвае, нет смысла за ней ухаживать. Аркадий Давидович
ещё >>