Алгоритм решения задачи в виде блок-схемы
Рис. 23. Алгоритм решения задачи в виде блок-схемы.
Алгоритм решения задачи в виде псевдокода
начало
ввод а, n, pi
s = 0
цикл i = 1 до n
конец цикла
s = s * pi
вывод s
конец
Программа решения задачи
#include <stdio.h>
#include <stdlib.h>
void main()
{
/* работа с динамическими массивами */
/* вычислить y = pi * summa(a[i] / i); */
float *a, y, pi = 3.1416;
int i, n;
printf("\nn="); /* n - число элементов */
scanf("%d", &n);
1.3. a = (float *) malloc(n * sizeof(float));
for (i = 0; i < n; i++) /* цикл ввода чисел */
{
printf("a[%d] = ", i);
scanf("%f", &a[i]);
}
/* цикл вычисления суммы */
y = 0;
for (i = 0; i < n; i++) /* цикл вычисления суммы */
{
y = y + a[i] / (i + 1);
}
y = pi * y;
printf("\ny=%12.5f", y);
free (a); /* освобождение памяти */
}
Вложенные циклы.В теле цикла разрешены любые исполняемые операторы, в том числе и циклы, т.е. можно конструировать вложенные циклы. В математике вложенным циклам соответствуют, например, кратные суммы или произведения.
Пример:
Алгоритм решения задачи в виде блок-схемы.
Рис. 24. Блок схема решения задачи.
Алгоритм решения задачи в виде псевдокода.
1.4. начало
ввод а
цикл j = 0 до 2
цикл i = 0 до 5
p = p * a[j][i]
c = c + a[j][i]
конец цикла i
s = s + c + p
конец цикла j
вывод s
конец
Текст программы.
#include <stdio.h>
void main()
{
double a[2][5], s, c, p;
int j, i;
for (j = 0; j<2; j++)
for (i = 0; i < 5; i++)
{
printf("a[%d][%d]=", j+1, i+1);
scanf("%lf", &a[j][i]);
}
for (s= 0.0, j = 0; j < 2; j++)
{
for (p = 1.0, c = 0.0, i = 0; i < 5; i++)
{
p*=a[j][i];
c+=a[j][i];
}
s+=c+p;
}
printf("s=%lf", s);
}
Результаты расчетов.
a[1][1] = 2
a[1][2] = 3
a[1][3] = 4
a[1][4] = 3
a[1][5] = 2
a[2][1] = 3
a[2][2] = 5
a[2][3] = 4
a[2][4] = 4
a[2][5] = 3
s=897.000000
6.4.1. Инициализация массивов
При определении массивов возможна их инициализация, т.е. присваивание начальных значений их элементам. По существу (точнее по результату), инициализация – это объединение определения объекта с одновременным присваиванием ему конкретного значения. Использование инициализации позволят изменить формат определения массива. Например, можно явно не указывать количество элементов одномерного массива, а только перечислить их начальные значения в списке инициализации:
double d [ ] = {1.0, 2.0, 3.0, 4.0, 5.0};
В данном примере длину массива компилятор вычисляет по количеству начальных значений, перечисленных в фигурных скобках. После такого определения элемент d[ 0 ] равен 1.0, d [ 4 ] равен 5.0.
Если в определении массива явно указан его размер, то количество начальных значений не может быть больше количества элементов в массиве. Если количество начальных значений меньше, чем объявленная длина массива, то начальные значения получать только первые элементы массива (с меньшими значениями индекса):
int M[8] = {8, 4, 2};
В данном примере определены значения только переменных M[0], M[1], и M[2], равны соответственно 8, 4 и 2. Значения M[3], … , M[7] не инициализируются.
Правила инициализации многомерных массивов соответствуют определению многомерного массива как одномерного, элементами которого служат массивы, размерность которых на единицу меньше, чем у исходного массива. Одномерный массив инициализируется заключенным в фигурные скобки списком начальных значений. В свою очередь, начальное значение, если оно относится к массиву, также представляет собой заключенный в фигурные скобки список начальных значений. Например, присвоить начальные значения вещественным элементам двумерного массива А, состоящего из стрех «строк» и двух «столбцов», можно следующим образом:
double A[3] [2] = {{10, 20}, {30, 40}, {50, 60}};
Эта запись эквивалентна последовательности операторов присваивания: A[0][0] = 10; A[0][1] = 20; A[1][0] = 30; A[1][1] = 40; A[2][0] = 50; A[2][1] = 60; Тот же результат можно получить с одним списком инициализации:
double A[3][2] = {10, 20, 30, 40, 50, 60};
с помощью инициализации можно присваивать значения не всем элементам многомерного массива. Например, чтобы инициализировать только элементы первого столбца матрицы, ее можно описать так:
double Z[4][6] = {{1}, {2}, {3}, {4}};
6.4.2. Упорядочение в одномерных массивах.
6.4.3. Прямое упорядочение.
/* упорядочение элементов массива */
#include <stdio.h>
void main()
{
int n, i, j;
double a[10], b;
while(1) /* цикл для проверки вводимого значения n */
{
printf("\n n=");
scanf("%d", &n);
if (n > 1 && n <= 10) break;
printf("Error n!");
}
printf("\n array \n"); /* ввод значений массива */
for (j = 0; j<n; j++)
{
printf("a[%d]=", j+1);
scanf("%lf", &a[j]);
}
/* сортировка массива */
for (i = 0; i < n - 1; i++)
for (j = i + 1; j < n; j++)
if (a[i] > a[j])
{
b = a[i];
a[i] = a[j];
a[j] = b;
}
/* печать результата сортировки */
printf("\n sort array: \n");
for (j = 0; j < n; j++)
printf ("a[%d]=%f\n", j+1, a[j]);
}
В программе реализован алгоритм прямого упорядочения – каждый элемент a[i], начиная с a[0] и кончая a[n – 2], сравнивается со всеми последующими, и на место a[i] выбирается минимальный. Таким образом, a[0] принимает минимальное значение, a[1] – минимальное значение из оставшихся и т.д. Недостаток этого алгоритма состоит в том, что в нем фиксированное число сравнений, не зависимое от исходного расположения значений элементов. Даже для уже упорядоченного массива придется выполнить то же самое количество итераций (n-1) *n/2, так как условия окончания циклов не связаны со свойствами, т.е. с размещением элементов массива.
6.4.4. Попарное сравнение
Алгоритм попарного сравнения соседних элементов позволяет в ряде случаев уменьшить количество итераций при упорядочении. В цикле от 0 до n-2 каждый элемент a[i] массива сравнивается с последующим a[i+1] (0<i<n-1). Если a[i]> a[i+1], то значения этих элементов меняются местами. Упорядочение заканчивается, если оказалось, что a[i] не больше a[i+1] для всех i. пусть k – количество перестановок при очередном просмотре. Тогда упорядочение можно осуществить с помощью такой последовательности операторов:
/* упорядочение элементов массива */
#include <stdio.h>
void main()
{
int n, n1, i, j, k;
double a[10], b;
while(1)
{
printf("\n n=");
scanf("%d", &n);
if (n > 1 && n <= 10) break;
printf("Error n!");
}
printf("\n array \n");
n1 = n;
for (j = 0; j<n; j++)
{
printf("a[%d]=", j+1);
scanf("%lf", &a[j]);
}
do
{
for (i=0, k = 0; i<n-1; i++)
if (a[i] > a[i+1])
{
b = a[i];
a[i] = a[i+1];
a[i+1] = b;
k = k + 1;
}
n--;
}
while (k>0);
printf("\n sort array: \n");
for (j = 0; j < n1; j++)
printf ("a[%d]=%f\n", j+1, a[j]);
}
Здесь количество повторений внешнего цикла зависит от исходного расположения значений элементов массива. После первого завершения внутреннего цикла элемент a[n-1] становится максимальным. После второго окончания внутреннего цикла на место a[n-2] выбирается максимальный из оставшихся элементов и т.д. Таким образом, после j-го выполнения внутреннего цикла элементы a[n-j],…, a[n-1] уже упорядочены, и следующих внутренний цикл достаточно выполнить только для 0 <i< (n-j-1). Именно поэтому после каждого окончания внутреннего цикла значение n уменьшается на 1.
В случае упорядоченности исходного массива внешний цикл повторяется только один раз, при этом выполняется (n-1) сравнений, k остается равным 0. Для случая, когда исходный массив упорядочен по убыванию, количество итераций внешнего цикла равно (n-1), а внутренний цикла последовательно выполняется (n-1)*n/2 раз.
6.4.5. Метод пузырька (обменная сортировкой с выбором)
Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно. Реализуется так - будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в том случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий" элемент всего массива. Теперь повторим всю операцию для оставшихся неотсортированными N-1 элементов (т.е. для тех, которые лежат "ниже" первого).
#include <stdio.h>
#define swap(a,b) { int tmp; tmp=a; a=b; b=tmp; }
main()
{
int a[10], dim=10;
int i, j;
for (i=0;i<dim;i++)
{
printf("Элемент\n");
scanf("%d",&a[i]);
}
printf("Было\n");
for (i=0;i<dim; i++)
printf("%d\n",a[i]);
/* Проход массива "вниз", начиная с нулевого элемента */
for (i = 0; i < dim; i++)
/* Проход массива "вверх", начиная с последнего до i-го элемента */
for (j = dim-1; j > i; j--)
/* Сравнение двух соседних элементов и их обмен */
if(a[j-1] > a[j]) swap(a[j-1], a[j]);
printf("Стало\n");
for (i=0;i<dim; i++)
printf("%d\n",a[i]);
}
6.4.6. Сортировка выбором
На этот раз при просмотре массива мы будем искать наименьший элемент, сравнивая его с первым. Если такой элемент найден, поменяем его местами с первым. Затем повторим эту операцию, но начнем не с первого элемента, а со второго. И будем продолжать подобным образом, пока не рассортируем весь массив.
#include <stdio.h>
#define swap(a,b) { int tmp; tmp=a; a=b; b=tmp; }
main()
{
int a[10], dim=10;
int i, j, k;
for (i=0;i<dim;i++)
{
printf("Элемент\n");
scanf("%d",&a[i]);
}
printf("Было\n");
for (i=0;i<dim; i++)
printf("%d\n",a[i]);
/* Проход массива, начиная с 0-го до предпоследнего элемента */
for (i = 0; i < dim-1; i++)
{
/* Проход массива, начиная с (i+1)-го до последнего элемента */
for (k = i, j = i+1; j < dim; j++)
if(a[j] < a[k]) k = j; /* Поиск наименьшего k-го эл-та */
swap(a[k], a[i]); /* Перемещение наименьшего "вверх" */
}
printf("Стало\n");
for (i=0;i<dim; i++)
printf("%d\n",a[i]);
}
6.4.7. Метод Шелла
Этот метод предложил Donald Lewis Shell в 1959 г. Основная идея алгоритма заключается в том, чтобы вначале устранить массовый беспорядок в массиве, сравнивая далеко стоящие, друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).
#include<stdio.h>
#define swap(a,b) { int tmp; tmp=a; a=b; b=tmp; }
main()
{
int a[10], dim=10;
int i, j, gap;
for (i=0;i<dim;i++)
{
printf("Элемент\n");
scanf("%d",&a[i]);
}
printf("Было\n");
for (i=0;i<dim; i++)
printf("%d\n",a[i]);
for (gap = dim/2; gap > 0; gap/=2) /* Выбор интервала */
for (i = gap;i < dim; i++) /* Проход массива */
/* Сравнение пар, отстоящих на gap друг от друга */
for (j = i-gap; j >= 0 && a[j] > a[j+gap]; j -= gap) swap(a[j], a[j+gap]);
printf("Стало\n");
for (i=0;i<dim; i++)
printf("%d\n",a[i]);
}
6.5. Функции
Определение функций.Каждая программа на языке Си – это совокупность функций. В определении функции указывается последовательность действий, выполняемых при обращении к функции, имя функции, тип результата (возвращаемого значения) и совокупность форматных параметров, заменяемых при обращении к функции фактическими параметрами (аргументами).
В настоящее время более широко используется и рекомендуется стандартом языка Си определение функции, в котором список формальных параметров объединен с их спецификацией.
Структура стандартного определения функции:
тип результата
имя_функции (спецификация_формальных_параметров)
{
определения_объектов;
исполняемые_операторы;
}
Пример той же функции:
double f (int a, float b, double d)
{ /* тело функции */ }
Принципиально важным оператором тела функции является оператор возврата из функции в точку ее вызова:
return выражение;
или
return;
Выражение в операторе возврата задает возвращаемое функцией значение. Для функции, не возвращающей никакого значения (указан тип void), выражение в операторе return отсутствует. В теле такой функции оператор return может вообще отсутствовать. В этом случае компилятор предполагает, что оператор return находится в самом конце тела функции.
Применение оператора return допустимо и к функции main(). Если программист явно не поместил в функцию main() оператор return, то компилятор поместит его в конце текста функции main(). В отличие от «неглавных» функций, откуда возврат выполняется в вызывающую функцию, выполнение оператора return; или return выражение; в функции main() приводит к завершению программы. Управление при таком выходе передается вызывающей программе, например, операционной системе, которая может анализировать значение выражения, использованного в операторе возврата.
Пример. Функция для вычисления объема цилиндра.
float w(float g, float h)
{ /* большее считается радиусом, меньшее – высота */
if (g >= h )
return 3.14156*g*g*h;
else
return 3.14156*g*h*h;
}
Пример. Вычислить скалярное произведение двух векторов n-мерного линейного пространства по формуле:
Функция для вычисления указанного произведения может быть определена следующим
float Scalar_Product (int n, float a[ ], float b[ ])
{
int i; /* параметр цикла */
float z; /* формируемая сумма */
for (i = 0, z = 0.0; i < n; i++)
z+=a[i]*b[i];
return z; /* возвращаемый результат */
}
Обращение к функции и ее прототип.Для обращения к функции используется элементарное (первичное) выражение, называемое «вызов функции»:
имя_функции (список_фактических_параметров)
Значение этого выражения – возвращаемое функцией значение (определяется в теле функции выполненным оператором return). Список фактических параметров (аргументов) – это список выражений, заменяющих формальные параметры функции. Соответствие между формальными и фактическими параметрами устанавливается по порядку их расположения в списках. Если формальных параметров у функции нет, то не должны быть и фактических параметров при обращении к этой функции. Фактические параметры (аргументы) передаются из вызывающей программы в функции по значению, т.е. вычисляется значение каждого аргумента, и именно оно используется в теле функции вместо заменяемого формального параметра.
Примеры вызовов определенных выше функций:
w(z-1.0, 1e-2)
При работе с функциями тип возвращаемого функцией значения определяется только типом результата, указанным в определении функции перед ее именем.
Стандарт языка Си предусматривает обязательное описание функции со стандартным заголовком с помощью прототипа. Прототип включает спецификацию параметров:
тип_результата имя_функции
(спецификация_формальных_параметров);
Здесь спецификация формальных параметров представляет собой список типов и, возможно, имен параметров функции.
Прототип функции схож с ее заголовком. Но имеются два существенных отличия. Во-первых, в прототипе могут не указываться имена специфицируемых параметров. Прототип может не использоваться только в том случае, когда определение функции находится в том же файле, где размещена вызывающая ее программа, и это определение помещено выше вызывающей программы. Прототипы введенных выше функций могут быть такими:
floatw(float, float);
Scalar_Product(int n, floata[], floatb[]);
Имена формальных параметров в прототипе функции w() не указаны, специфицированы только их типы.
Применение прототипа предполагает только стандартную форму записи заголовка функции. Использование прототипа несовместимо со «старомодным» видом заголовка.
Пример. Вычисление биномиального коэффициента.
, где n>= m>=0; n, m – целые.
Программа.
#include <stdio.h>
int fact(int k) /* вычисление факториала k! */
{
int j, i; /* вспомогательные переменные */
for (i=1, j=1; i<=k; i++) /* цикл вычислений */
j*=i;
return j;
} /* конец определения функции */
/* вычисление биномиального коэффициента */
void main()
{
int n, m, nmc, nm; /* nm - значение (n-m) */
/* nmc - значение биномиального коэффициента */
while(1)
{
printf("\ninput n=");
scanf("%d", &n);
printf("m=");
scanf("%d", &m);
if (m>=0 && n>=m && n<10) break;
printf("error!");
}
nm = n - m;
nmc = fact(n) / fact(m) / fact(nm);
printf("\n c=%d", nmc);
} /* конец главной программы */
Результаты расчета.
input n=4
m=2
c=6