Пример анализа программы: выбор возрастающих последовательностей

Определить значения переменных после выполнения действий.

//------------------------------------------------- 1

inti1 = 0xFFFF; i1 ++;

//------------------------------------------------- 2

unsigned u1,u2,u;

u1 = 5;

u2 = -1;

u=0;

if (u1 > u2) u++;

//------------------------------------------------- 3

int i1 = 0x01FF; char c; c = i1; i1 = c;

//------------------------------------------------- 4

int i1 = 0x01FF;

unsigned char c;

c = i1;

i1 = c;

//------------------------------------------------- 5

double d1,d2,d3;

  d1 = 2.56;

d2 = (int)d1 + 1.5;

  d3 = (int)(d1 + 1.5);

//------------------------------------------------- 6

double d1 = 2.56; 

int i;

i = (d1 - (int)d1) * 10;

//------------------------------------------------- 7

int i1=2000000000,i2=200000000,s ;

unsigned s1,s2;

  s1 = i1 + i2;

  s2 = (unsigned)i1 + i2;

  if (s1 == s2) s=0; else s=1;

//------------------------------------------------- 8

i=0; if (i++) i++;

//------------------------------------------------- 9

i=0; if (++i) i++;

//------------------------------------------------ 10

m = a > b ? a : b;

//------------------------------------------------ 11

m = (a * b) > 0;

//------------------------------------------------ 12

m = a > 0 ? a : -a;

Неявные преобразования типов

Даны определения переменных:

char      cval;

int       ival;

float     fval;

double    dval;

unsignedint ui;

Какиенеявныепреобразованиятиповбудутвыполнены?

(a) cval = cvаl + 3;

(b) fval = ui - ival * 1.0;

(c) dval = ui* fval;

(d) cval = ival + fval + dval;

1.3 Исправьте ошибки в примерах:

(1) if ( ivall != ival2 )

ivall = ival2 else

ivall = ival2 = 0 ;

(2) if ( ivat< minval ) minvat = ival; occurs = 1;

(3) if ( int ival = get_value () )

cout <<"ival ="<< ival << endl;

if ( ! ival ) cout <<"ival = \n";

(4) if ( ival = 0 ) ival = get_value();

(5) if ( ival == 0 ) else ival = 0;

(6) switch (   ival ) {

case ' а' : aCnt++;

case ' e ' : eCnt++;

default: iouCnt++; }

(7) switch ( ival ) {

case 1: int ix - get_value(); ivec[ ix ] = ival; break;      

default: ix - ivec.size()-1; ivec[ ix ] = ival; }

(8) switch ( ival ) {

  case 1, 3, 5, 7, 9: oddcnt++; break;

  case 2, 4, 6, 8, 10: evencnt++; break; }

(9) int ival=512 jval=1024, kval=4096; int: bufsize; // . . .

  switch( swt ) { case ival:

bufsize = ival * sizeoff int ); break; case jval:

bufsize = jval * sizeof( int ); break; case kval:

bufsize = kval * sizeof( int }; break; }

Определить значения переменных после выполнения операторов

(по умолчанию все переменные - int).

//------------------------------------------------- 1

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

//------------------------------------------------- 2

for (i=0,j=20; i<j; i++, j--);

//------------------------------------------------- 3

for (n=16,i=0; n!=1; i++, n/=2);

//------------------------------------------------- 4

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

//------------------------------------------------- 5

for (i=0, d=0; i<10; i++, d =!d);

//------------------------------------------------- 6

for (i=0; i>=0; i++);

//------------------------------------------------- 7

i=5; if (i) i++;

//------------------------------------------------- 8

for (i=1,s=1; i<=5; i++) s=s*i;

//------------------------------------------------- 9

for (i=1,s=0; i<=5; i++) s=s+i;

//------------------------------------------------ 10

for (i=0; 1; i++) { if (i==20) break; }

//------------------------------------------------ 11

for (i=0, n=0; i<10; i++) { if (i>5) continue; n++;}

//------------------------------------------------ 12

a = 5; b = 3; c = 1;

switch ((a > b) * 2 + (b > c))

  {

case 0: n = c; break;

case 1: n = b; break;

case 2: n = c > a ? c : a; break;

case 3: n = a; break;

  }

Содержательно сформулировать результат выполнения фрагмента программы

Например в таком виде: “Последовательный просмотр элементов массива и поиск нулевого”.

//---------------------------------------------------

int d,s,i,A[20]; char c;

//------------------------------------------------- 1

for (s=0,i=0; i<20; i++) s+=A[i];

//------------------------------------------------- 2

for (d=A[0], i=1; i<20; i++)

if (d > A[i]) d=A[i];

//------------------------------------------------- 3

for (i=0; i<20 && A[i] !=0; i++);

if (i!=20) A[i]=10000;

//------------------------------------------------- 4

for (d=0, i=0; i>=0; i==19 ? d=!d : 1 , d ? i-- : i++)

  { A[i]; }

//------------------------------------------------- 5

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

  { if (A[i]==0) continue; s++; }

//------------------------------------------------- 6

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

  if (A[i]==0) { A[i]=10000; break; }

//------------------------------------------------- 7

for (i=s=0; i<20; A[i] >=0 ? s++ : s--, i++);

//------------------------------------------------- 8

for (i=s=0; i<20; i++) s+= A[i] > 0;

//------------------------------------------------- 9

for (s=A[19], i=19; i!=0; i--) A[i]=A[i-1];

A[0]=s;

//------------------------------------------------ 10

d = -1;

switch (c)

  {

case '9': d++;

case '8': d++;

// ...

case '0': d++;

  };

1.6 Упростите следующий код:

for(sum= i=0, j = 2, k=i+j;i<10 || k < 15 ;++i, ++j, ++k)

     sum += (i < j)? k : i ;

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

Какие ошибки допущены в следующих операторах.

//for

(1) for ( int *ptr = &ia,, ix = 0;

ix < size && ptr != ia+size;

+ + ix, + +ptr )

// . . .

(2) for ( ; ; ) {

if ( some_condition ) break; //.... }

(3) for ( int ix = 0; ix < sz; ++ix ) // . . .

if ( ix != sz ) // . . .

(4) int ix;

for ( ix < sz; ++ix ) // . . .

(5) for ( int ix = 0; ix < sz; ++ix, ++ sz ) // . . .

//while

(6) string bufString, word;

while ( cin >> bufString >> word )

(7) while ( ptr = 0 )

ptr = find_a_value();

(8) while ( bool status = find( word ))

{ word = get_next_word(); if ( word.empty() ) break;}              

if ( ! status ) cout<< "Словненайдено \n";

//do while

(9) do

string rsp;

int vail, va!2;

coub<< “Введите два числа: ";

cin>>val1 >>val2;

cout << "Сумма " << val1 << " и " << val2

<< " = " << val1 + val2 << "\n\n"

<< "Продолжить? [да][нет] ";

cin>>rsp;

while ( rsp[0] != 'n' );

(10) do {

// . . .

} while ( int ival = get_response() );

(11) do {

int ival = get_response();

if ( ival == some_value() )

break; }

while ( ival };

 if ( !ival ) // . . .

2 Программы на С++

2.1 Пример текста программы на С++

//----------------------------------------------------

#include <stdio.h>

// В текст программы включается заголовочный файл

// стандартной библиотека ввода-вывода, в котором

// содержится необходимая транслятору информация о

// функциях.

double min(double A[], int nn)

// Заголовок функции min, возвращающей в качестве

// результата вещественное число - значение минимального

// элемента массива. Формальные параметры-

// указатель на массив А, и размерность массива - nn.

{

double A_min;

int i;

// Локальные переменные функции, текущее минимальное

// значение элемента A_min и индекс в массиве i.

for (i=1, A_min=A[0]; i<nn; i++)

// Цикл выполняется для всех значений переменной i

// от 1 до nn-1 включительно. При этом начальное

// значение А_min устанавливается равным элементу

// массива A синдексом 0.

  if (A[i] < A_min) A_min=A[i];

// В каждом шаге цикла производится сравнение теку-

// щего элемента массива A[i] и A_min. Если текущий

// элемент меньше, то его значение становится новым

// минимумом.

return (A_min);

}

// Значение A_min возвращается в качестве результата 

// функции и выполнение тела функции завершается.

double B[10]={ 3.,6.,-5.,4.,12.,3.3,0.45,5.,4.,8.};

// Массив из 10 вещественных чисел, инициали-

// зированный списком начальных значений, которые

// будут установлены в нем в момент запуска про-

// граммы. Массив является глобальной переменной,

// то есть доступен для любой, следующей за ним

// функции (в данном случае main).

double C[20];

// Глобальный массив из 20 вещественных чисел.

// Начальных значений не имеет.

void main()

{

// Основная функция main, вызывается при запуске

// программы.

int i,n1;

double dd;

// Локальные переменные функции. i - текущий индекс

// элемента массива. n1 - количество заполненных

// элементов в массиве C[]. dd - сохраняет

// результат, возвращаемый функцией min при вызове.

do

// Оператор цикла с проверкой условия продолжения

// после очередного шага цикла.

  {

// Тело цикла - составной оператор,

// последовательность из двух простых операторов

  cout << "Элементов массива:";

// Выражение содержит операцию вывода в объект - поток.

// Ограниченное символом ";", превращается в простой

// оператор. Выводит на экран текст подсказки.

  cin >> n1;

// Вводит с клавиатуры значение целой переменной n1.

  } while (n1 < 1 || n1 > 20);

// Цикл продолжается, пока введенное значение n1 не

// попадет в интервал 1..20. Условие продолжения -

// не попадает в интервал, то есть меньше 1 или

// больше 20.

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

// Цикл повторяется для всех значений i, начиная от 0

// и заканчивая nn-1 включительно

  {

// Тело цикла - составной оператор

  cout << "C["<<i<<"]=";

// Вывод подсказки - строка "C[...]", в угловых

// скобках значение переменной i - индекс текущего

// элемента массива.

  cin >> C[i];

// Ввод значения i-го элемента массива в формате

// вещественного числа

  } 

dd = min(C,n1);

// Вызов функции min для массива C[] и количества

// заполненых элементов в нем - n1. Результат

// функции присваивается переменной dd.

cout <<"Минимум С[]="<< dd<<endl;

// Вывод строки "Минимум C[i]=..." со значением пере-

// менной dd в формате вещественного числа.

// После вывода строки производится перевод курсора

// на экране к началу следующей (символ \n в

// форматной строке).

cout << "Минимум B[]=" << min(B,10)) endl;

// Вывод строки в подобном формате для массива B[].

// Вместо промежуточной переменной непосредственно

// следует вызов функции min для массива B[] раз-

// мерностью 10 элементов (фактические параметры).

}

Теперь становится ясно, сколько нужно комментариев в программе, чтобы смысл ее был вполне понятен.

Способы анализа программы

Назначение любой программы – давать определенный результат для любых входных значений. Результат же – это набор значений, удовлетворяющих некоторым условиям, или обладающий некоторыми свойствами. Если посмотреть на программу с этой точки зрения, то она имеет много общего с математической теоремой. Действительно, теорема утверждает, что некоторое свойство имеет место на множестве элементов (например, теорема Пифагора устанавливает соотношение для гипотенузы и катетов всех прямоугольных треугольников). Программа обладает тем же самым свойством: для различных вариантов входных данных она дает результат, удовлетворяющий определенным условиям. Поэтому анализ программы – это не что иное, как формулировка теоремы о том, какой результат она дает.

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

Убедиться, что теорема верна, можно различными способами. (Обратите внимание - убедиться, но не доказать). Точно так же можно убедиться, что программа дает тот или иной результат:

–выполнить программу в компьютере или проследить ее выполнение на конкретных входных данных “на бумаге” (анализ методом единичных проб);

– разбить программу на фрагменты с известным “смыслом” и попробовать соединить результаты их выполнения в единое целое (анализ на уровне неформальной логики и “здравого смысла”);

– формально доказать с использованием логических и математических методов (например, метода математической индукции), что фрагмент дает заданный результат для любых значений входных переменных (формальныйанализ).

Те же самые методы можно использовать, если результат и “смысл” программы не известен. Тогда при помощи единичных проб и разбиения программы на фрагменты с уже известным “смыслом” можно догадаться, каков будет результат. Такой же процесс, но в обратном направлении имеет место при разработке программы. Можно попытаться разбить конечный результат на ряд промежуточных, для которых уже имеются известные фрагменты.

Смысл фрагментов алгоритмов может быть разным:

–каждая переменная в программе не просто хранит значение. С ней обычно связывается результат выполнения некоторого процесса. Существует ряд стандартных процессов, которые присутствуют в большинстве алгоритмов, существует и ряд стандартных "смыслов" переменных (переменная цикла, счетчик, накопитель, признак, минимум/максимум);

– если циклический процесс завершается в зависимости от выполнения или невыполнения условия на множестве проверяемых элементов, то такой цикл проверяет свойства всеобщности или существования на этом множестве - в этом заключается его смысл;

– каждая предметная область имеет набор выражений и фрагментов, которые несут дополнительный смысл только при их использовании в этой области. Так, например, остаток от деления на 10 в арифметических задачах дополнительно означает еще и младшую цифру числа (делимого);

– каждая структура данных имеет стандартный набор выражений, имеющий смысл только применительно к ней;

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

Пример анализа программы: выбор возрастающих последовательностей

for (m=0, k=0, i=1; i<20; i++)

        if (A[i-1]<A[i]) k++;

        else { if (k>m) m=k; k=0; }

1. Смысл цикла for() - последовательный просмотр элементов массива.

2. Смысл переменной m из выражения if (k>m) m=k; - выбор максимального значения из последовательности получаемых значений k.

3. A[i] - текущий элемент массива, A[i-1] - имеет смысл - предыдущий элемент массива, A[i-1]<A[i] имеет смысл - два соседних элемента массива (предыдущий и текущий) расположены в порядке возрастания.

4. Смысл переменной k из выражения if () k++;- переменная-счетчик.

5. Смысл фрагмента if (A[i-1]<A[i]) k++; - подсчет количества пар соседних элементов, расположенных в порядке возрастания.

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

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

i= 1 2 3 4 5 6 7 8

A[] 3 4 5 2 1 3 4 6 2

k=0 k++ k++ k=0 k=0 k++ k++ k++ k=0

1 2 0 0 1 2 3 0

m=0         m=k            m=k

            2   3

Очевидно, что процесс подсчета k связан каким-то образом с процессом возрастания значений A[i]. Если несколько значений расположены подряд в порядке возрастания, то выполняется одна и та же ветка if , а k последовательно увеличивается. При появлении первого убывающего значения в последовательности счетчик сбрасывается, но перед этим его значение фиксируется на предмет максимума. Таким образом, программа определяет МАКСИМАЛЬНУЮ ДЛИНУ ПОСЛЕДОВАТЕЛЬНОСТИ ВОЗРАСТАЮЩИХ ЗНАЧЕНИЙ в массиве.