Алгоритм решения задачи в виде блок-схемы

Алгоритм решения задачи в виде блок-схемы - student2.ru

Рис. 23. Алгоритм решения задачи в виде блок-схемы.

Алгоритм решения задачи в виде псевдокода

начало

ввод а, n, pi

s = 0

цикл i = 1 до n

Алгоритм решения задачи в виде блок-схемы - student2.ru

конец цикла

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); /* освобождение памяти */

}

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

Пример:

Алгоритм решения задачи в виде блок-схемы - student2.ru

Алгоритм решения задачи в виде блок-схемы.

Алгоритм решения задачи в виде блок-схемы - student2.ru

Рис. 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-мерного линейного пространства по формуле:

Алгоритм решения задачи в виде блок-схемы - student2.ru

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

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() не указаны, специфицированы только их типы.

Применение прототипа предполагает только стандартную форму записи заголовка функции. Использование прототипа несовместимо со «старомодным» видом заголовка.

Пример. Вычисление биномиального коэффициента.

Алгоритм решения задачи в виде блок-схемы - student2.ru , где 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

Наши рекомендации

Число: 2099