Контрольная работа по "Информатике"

Министерство  образования и науки Российской Федерации.

Государственное образовательное учреждение

высшего профессионального образования.

Новосибирский государственный технический университет

Кафедра Прикладной математики

 

 

 

 

РГР

«Практикум  на ЭВМ:

Методы программирования»

 

 

 

Факультет

Группа 

Студент 

Преподаватель

 

 

 

Новосибирск

2010

1 Условие задачи

По заданной последовательности целых чисел А построить последовательность В такую, что В(i) – это количество элементов из А, превосходящих А(i), в начальном отрезке А длиной i-1

2 Анализ задачи

Дано:   A = { | Z, i=} ,  n N 

Результат: В = { | Z, i=}

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

=       , где t=

Решение:

При i=2, j=2, =0

Повторять

r= i-1

t=0

При k=1

 Повторять

если , то

t=t+1

k=k+1

Пока k≤r

=t

=j+1

Пока i≤n

Решение данной задачи можно свести к одной крупной подзадаче: сравнивание элемента последовательности А с элементами этой же последовательности длиной i-1 и присваивание значений соответствующим элементам последовательности  В.

3 Структуры данных, используемые для представления исходных данных и результатов задачи

               Внешнее представление исходных  данных –

1 строка:  n-число (количество вводимых пользователем чисел).

2 строка: последовательность из n целых чисел, разделенных пробелами, т.е. .

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

               Внутреннее представление исходных данных – переменная типа int и одномерный массив, элементы которого типа int.

               Внутреннее представление выходных данных – одномерный массив, элементы которого типа int.

4 Укрупненный  алгоритм  решения задачи

Подзадача для построения последовательности В такой, что – это количество элементов из А, превосходящих , в начальном отрезке А длиной i-1.

 

 

 

 

 

 

Основная программа

 

 

 

 

 

5 Структура программы

void zap (int z, int x[], int *y) – процедура, присваивает значения элементам последовательности В путем сравнивания элемента последовательности А с предыдущими ее элементами. На вход процедуре будут подаваться z ( размерность 2-х последовательностей)и последовательность X. На выход: последовательность Y.

 

 

 

 

 

 

 

6 Текст программы

#include <stdio.h>

#include <conio.h>

#include <locale.h>

#include <string.h>

void zap (int z, int x[], int *y)

{int i, r, k, t, j;

j=1;

y[0]=0;

for (i=1; i<z; i++)

{

r=i-1;t=0;

for (k=0; k<=r; k++)

{

if(x[k]>x[i])

t=t+1;

}

y[j]=t;j=j+1;

}

}

 

void main ()

{

setlocale ( LC_CTYPE, "Russian");

const int n1 (1000);

int a[n1], b[n1];

int n, i, j;

printf_s (" \nВведите количество чисел: ");

scanf_s ("%d", &n);

printf_s (" \nВведите последовательность целых чисел А: \n");

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

scanf_s ("%d", &a[i]);

zap (n, a, b);

printf_s (" \nПоследовательность B:\n"); 

for(j=0;j<n;j++)

printf_s("%d ", b[j]);

_getch();

}

 

 

 

 

 

 

 

 

 

7 Набор тестов

№ теста	Входные данные: n, A	Выходные данные: B	Примечание
1	n=6 A: 1 2 5 7 9 16	0 0 0 0 0 0	Последовательность В  будет нулевой,т.к. ни один элемент  последовательности А не превосходит  следующий
2	n=8 A: 5 2 12 0 3 21 9 1	0 1 0 3 2 0 2 6	Последовательность В  не нулевая, т.к. в последовательности А присутствуют элементы, превосходящие  следующие
3	n=10 A:  -6 2 7 -9 -12 8 3 9 -5 7	0 0 0 3 4 0 2 0 5 2	Тот же принцип и с  отрицательными числами

 

Рассмотрим случай, когда n=6 и А представляет собой такую последовательность целых чисел: 5 -7  -10 -7 9 -8

Тогда программа считает эту  последовательность и начнет проверку со второго элемента, присвоив уже  элементу значение 0. Т.к. предыдущее число 5 превосходит 2-ое число по значению, то присваивается значение 1. Если превосходящих i-ый элемент (т.е.-10) чисел 2(а именно 5 и -7), то соответственно будет равно 2 и т.д.

В конце на экран выведется последовательность В: 0 1 2 1 0 4