Определите “смысл” приведенных ниже фрагментов программ.

Сформулируйте его в виде одной фразы, например: 

“Программа находит максимальное значение из элементов массива A”.

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

cin >> a >> b;

c=a; a=b; b=c;

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

c= A[i]; A[i]=A[i+1]; A[i+1]=c;

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

cin >> a >> b;

if (a < b) c = b; else c = a;

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

cin >> a >> b;

c = a; if (a > b) c = b;

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

if (a < 0) a = -a;

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

if (a > 0 ) a = a + 1; else a = a - 1;

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

for (i=1; i<10; i++) ...

// Переменная - минимум/максимум

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

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

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

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

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

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

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

for (i=0,k=-1; i<10; i++)

   { if (A[i]<0) continue;

   if (k==-1) k=i;

   else

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

   }

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

for (i=0,k=-1; i<10; i++)

   { if (A[i]<0) continue;

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

   }

// Переменная - счетчик

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

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

   if (A[i]>0) s++;

//---------------------------------------------------------13

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

   if (A[i]>0 && A[i-1]<0) s++;

//---------------------------------------------------------14

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

   {

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

   else

           { if (k>s) s=k;

           k=0;

           }

// Переменная -признак

//---------------------------------------------------------15

for (i=0,s=0,k=0; i<10; i++)

   if (A[i]<0) k=1;

   else

           { if (k==1) s++;k=0; }

// Переменная - накопитель

//--------------------------------------------------------16

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

//--------------------------------------------------------17

for (s=1, i=0; i<10; i++) s = s * 2;

//--------------------------------------------------------18

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

//--------------------------------------------------------19

for (s=1, i=0; i < 10; i++) s = s * A[i];

//--------------------------------------------------------20

for (i=0, s=1; s < n; i++) s = s * 2;cout << i;

// Последовательности

//---------------------------------------------------------21

for (i=0; A[i]!=0; i++) {...}

//---------------------------------------------------------22

cin >> b;

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

A[i]=b;

A[i+1]=0;

// Работа с цифрами числа

//---------------------------------------------------------23

for (a=10; a<30000; a++)

   { for (n=a, s=0; n!=0; n=n/10)

           { k=n%10; s=s+k;}

   if (a==s*s*s) cout << a << "\n";

   }

//---------------------------------------------------------24

for (i=0, n=a; n!=0; i++, n=n/10);

for (A[i--]=0, n=a; n!=0; i--, n=n/10)

A[i]=n % 10;

// Признаки делимости

//--------------------------------------------------------25

for (i=2; n % i !=0; i++);

cout << i;

//--------------------------------------------------------26

for (i=n1-1; !(n1 % i ==0 && n2 % i ==0); i--);

cout << i;

//--------------------------------------------------------27

i = n1; if (i < n2) i=n2;

for (; !(i % n1 ==0 && i % n2 ==0); i++);

cout << i;

//--------------------------------------------------------28

for (i=0,a=2; a<10000; a++)

   {

   for (n=2; n<a; n++)

           { if (a%n==0) break; }

   if (n==a) A[i++]=a;

   }

A[i]=0;

//--------------------------------------------------------29

for (i=0,a=2; a<10000; a++)

   {

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

           { if (a%A[j]==0) break; }

   if (j==i) A[i++]=a;

   }

A[i]=0;

// Завершениецикла

//--------------------------------------------------------30

for (s=0, i=0; i < 10 && A[i] >0; i++)

   s = s + A[i];

//--------------------------------------------------------31

for (s=0, i=0, k=0; i < 10 && k ==0; i++)

   { s = s + A[i]; if (A[i]<=0) k=1; }

// Свойства - "для всех" и "существует"

//--------------------------------------------------------32

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

  if (A[i]<0) break;

if (i==10) cout << "Хорошо!!!\n";

//--------------------------------------------------------33

for (i=2; i<a; i++)

  if (a%i==0) break;

if (i==a) cout << "Хорошо!!!\n";

//--------------------------------------------------------34

for (n=a; n!=0; n/=10)

  {

  k=n%10;

  for (i=2; i<k; i++)

        if (k%i==0) break;

  if (k!=i) break;

  }

if (n==0) cout << "Хорошо!!!\n";

//--------------------------------------------------------35

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

  {

  for (j=2; j<A[i]; j++)

        if (A[i]%j==0) break;

  if (j==A[i]) break;

  }

if (i!=10) cout << "Хорошо!!!\n";

// Прочее

//--------------------------------------------------------36

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

   A[i-1] = A[i];

A[9] = s;

//--------------------------------------------------------37

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

   { c=A[i]; A[i]=A[9-i]; A[9-i]=c; }

//--------------------------------------------------------38

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

   { c=A[i]; A[i]=A[j]; A[j]=c; }

Примеры разработки и составления программ.

Особые числа

Число 1997 имеет особые свойства. Будучи простым, оно при разделении его цифр на две любые части также дает простые числа (199 и 7, 19 и 97, 1 и 997). Найти другие подобные числа в диапазоне от 1000 до 2000.

Идея: Поскольку проверка на то, является ли число простым, производится в нескольких случаях, то ее необходимо оформить в виде функции. Сущность алгоритма состоит в последовательной проверке всех значений от 1000 до 2000 на предмет соблюдения указанного свойства (полный перебор). Разделить число на две части можно, используя частное и остаток от его деления на степени 10, то есть 10,100,1000.

Факты:

1. Алгоритм проверки - является ли число простым, приведен в тестовых вопросах предыдущего параграфа. Число aпростое, если оно не делится ни на одно из чисел в диапазоне от 2 до a-1. Это свойство всеобщности проверяется циклом с break.

for (i=2; i<a; i++) if (a%i==0) break;

if (a==i)... // выход по a==i без break - не было ни одного деления

2. Этот фрагмент оформляется в виде функции, возвращающей логическое значение 0/1.

int PR(int a)

{ int i;

for (i=2; i<a; i++) if (a%i==0) break;

if (a==i) return 1; else return 0;

}

3. Усовершенствование: завершить функцию с результатом 0 можно сразу же по обнаружении факта деления нацело. Кроме того, функция не проверяет значение 1, которое также является простым числом.                           

int PR(int a)

{ int i;

if (a==1) return 1;

for (i=2; i<a; i++) if (a%i==0) return 0;

return 1;

}

4. Сам процесс поиска состоит в полном переборе значений в заданном диапазоне.

  void main()

  {

  for (int n=1000; n<2000; n++)

        { ... Удовлетворяет ли n - условиям

        if (удовлетворяет)cout<<n<<endl;

        }

  }

5. Разделить число nна две части и проверить, являются ли они простыми, можно, используя частное и остаток от его деления на степень 10, например

  intv=100;

  n / v - число без двух младших цифр

  n % v - число из двух младших цифр

6. Получить подряд степени числа 10 можно следующим циклом:

  for (int v=10; v<n; v*=10) { ...n/v...n%v...}

7. Проверить, являются ли простыми все части, на которые делится число n,можно с помощью цикла проверки свойства ВСЕОБЩНОСТИ

  for (int v=10; v<=n; v*=10)

{

if (!PR(n/v)) break;

if (!PR(n%v)) break;

}

  if (v>n) ... // Не было выхода по break (свойство: число простое)

8. Оператор continueдосрочно завершает шаг цикла и переходит к следующему, его можно использовать, если в результате проверки оказывается, что число nне удовлетворяет одному из условий. Тогда последовательность конструкций if(условие не соблюдается) continue;позволяет организовать “сито” проверок

  {

  if (!PR(n)) continue;        // пропустить - число не простое

  for (int v=10; v<=n; v*=10)

{

if (!PR(n/v)) break;

if (!PR(n%v)) break;

}

  if (v<=n) continue;   // пропустить - был выход по break

  cout<<n<<endl;        // прошли сквозь сито - найдено число

}

Практически программа уже написана, остается составить ее из частей.

Простые множители

Сформировать массив простых множителей заданного числа. Простые множители числа -простые числа, произведение которых дает заданное число, например: 72 = 2*2*2*3*3.

Шаг 1: Исходные данные и результат -формальные параметры функции.

void calc(int val, int A[], int n){ ... }

val -Заданное число

A - Масссив простых множителей

n - Размерность массива

Шаг 2: Форма представления результата. Последовательность простых множителей в массиве А ограничена значением 0. Основной цикл получения множителей состоит в выделении очередного множителя из val и запоминания его.

void calc(int val, int A[], int n)

{

int i;      // Количество множителей

int m;      // Значение множителя

for (i=0; не кончился массив и есть множители; i++)

  {

// Получить значение множителя m

  A[i] = m;

  }

A[i]=0;

}

Шаг 3. Получение очередного простого множителя. Простой множитель -минимальное простое число, на которое исходное делится без остатка. Если оно найдено, то в следующем шаге нужно использовать частное от деления исходного числа на множитель, чтобы искать следующий, то есть val = val / m; Последний множитель даст переменной val значение 1.

void calc(int val, int A[], int n)

{

int m,i;

for (i=0; i<n-1 && val !=1; i++)

  {

// Получить минимальное простое число m,нацело делящее val

  val /= m; A[i] = m;

  }

A[i] = 0;

}

Шаг 4: Для поиска минимального m, нацело делящего val, в цикле подряд проверяются все m, начиная с 2, до тех пор, пока остаток от деления не станет равным 0.

Окончательный вариант:

//------Простые множители числа

void calc(int val, int A[], int n)

{

int m,i;

for (i=0; i<n-1 && val !=1; i++)

  {

  for (m=2; val % m !=0; m++);

  val /= m; A[i] = m;

  }

A[i] = 0;

}

Простые числа

Сформировать массив простых чисел, не превышающих заданное. Простое число -число, которое делится нацело только на 1 и на само себя.

Шаг 1: Исходные данные и результат -формальные параметры функции -аналогично предыдущему примеру.

void calc(int val, int A[], int n) {...}

Шаг 2: Сущность алгоритма состоит в проверке всех чисел от 2 до val и сохранении их в массиве, если они простые.

void calc(int val, int A[], int n)

{

int i;      // Номер очередного простого часла

int m;      // Очередное проверяемое число

for (i=0, m=2; i < n-1 && m < val; m++)

  {

  if (m - простое число)

        A[i++] = m;

  }

A[i] = 0;

}

Шаг 3: Конкретизируем утверждение, что m -простое число. Во-первых, оно не делится ни на одно число в диапазоне от 2 до m/2 включительно. Во-вторых, что то же самое, оно не делится ни на одно простое число от 2 до m-1. Тогда можно воспользоваться накопленными простыми числами в массиве A от A[0] до А[i-1]. Фрагмент программы, где определяется "простота" числа будет иметь вид:

int n;

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

  if (m % A[n]==0) break; // Разделилосьнацело

if (i==n)

  { ...m - простое число... }

Окончательный вариант:

//-------Простые числа

void calc(int val, int A[], int n)

{

int i,m,k;

for (i=0, m=2; i < n-1 && m < val; m++)

  {

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

        if (m % A[k]==0) break;

  if (i==k)

        A[i++] = m;

  }

A[i] = 0;

}

Счастливыебилеты

“Счастливым” называется билет, в котором в шестизначном номере сумма первых трех цифр равна сумме последних трех.

Шаг 1: Исходные данные и результат. Функция возвращает целое -количество “счастливых” билетов. Формальных параметров нет.

Шаг 2: Если известно, каким образом преобразовать шестизначное число в массив из 6 значений его цифр, то алгоритм будет состоять в последовательном разложении всех шестизначных чисел на цифры и проверки результата на “счастье”.

int calc()

{

int n;      // Количество "счастливых" билетов

long v;      // Проверяемое шестизначное число

int B[6];   // Массив значений цифр

for (n=0,v=0; v < 1000000; v++)

  {

// Разложить val в массив значений цифр числа - B

  if (B[0]+B[1]+B[2]==B[3]+B[4]+B[5]) n++;

  }

return n;

}

Шаг 3: Остаток от деления целого числа на 10 дает значение младшей цифры, например 1996 % 10 = 6. Частное от деления целого числа на 10 дает то же самое число без последней цифры: 1996 / 10 = 199. Тогда остатки от последовательного деления на 10 исходного числа дадут искомые значения цифр (при условии, что частное от деления на следующем шаге становится делимым).

int m;                 // Номер шага (цифры)

long vv;                  // Исходное число

for (vv = v, m=0; m<6; m++)

  {

  B[m] = vv % 10;      // Остаток - очередная цифра

  vv = vv / 10;      // Частное становится делимым

  }

Окончательный вариант:

//------Счастливые билеты

int calc()

{

int n, B[6];

long v;

for (n=0,v=0; v < 1000000; v++)

  {

  int m;

  long vv;

  for (vv = v, m=0; m<6; m++, vv /=10)

        B[m] = vv % 10;

  if (B[0]+B[1]+B[2]==B[3]+B[4]+B[5]) n++;

  }

return n;

}

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

Типы данных