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

Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

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

2017-07-09 509
Алгоритм решения задачи в виде блок-схемы 0.00 из 5.00 0 оценок
Заказать работу

Рис. 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)

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

Стандарт языка Си предусматривает обязательное описание функции со стандартным заголовком с помощью прототипа. Прототип включает спецификацию параметров:

тип_результата имя_функции

(спецификация_формальных_параметров);

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

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

float w(float, float);

Scalar_Product(int n, float a[], float b[]);

Имена формальных параметров в прототипе функции 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


Поделиться с друзьями:

Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...

Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...

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



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.007 с.