5. Основные управляющие структуры. Семантика и реализация в языке с++: следование, выбор. Примеры.

5. Основные управляющие структуры. Семантика и реализация в языке с++: следование, выбор. Примеры.

// Пример 1.1: пересечение отрезков

#include <iostream>

using namespace std;

int main ()

{ int a, b, c, d, w; // входные данные

cout << "Введите координаты первого отрезка (левый и правый концы):\n";

cin >> a >> b;

cout << "Введите координаты второго отрезка (левый и правый концы):\n";

cin >> c >> d;

cout << "Введены отрезки: [" << a << "," << b << "] [" << c << "," << d <<"]\n";

if ((b >= c) && (d >= a)) cout << "Отрезки пересекаются\n“;

else cout << "Отрезки не пересекаются\n“;

cout << "End of the program LINE\n";

return 0;

}

// Пример 1.3: пересечение отрезков (с вычислением булевской переменной)

#include <iostream>

using namespace std;

int main ()

{ int a, b, c, d, w; // входные данные

bool p;

cout << "Введите координаты первого отрезка (левый и правый концы):\n";

cin >> a >> b;

if (a > b) { w = a; a = b; b = w;};

cout << "Введите координаты второго отрезка (левый и правый концы):\n";

cin >> c >> d;

if (c > d) {w = c; c = d; d = w;};

cout << "Введены отрезки: [" << a << "," << b << "] [" << c << "," << d << "]\n";

p = (b >= c) && (d >= a);

cout << "Отрезки “;

if (!p) cout << "НЕ“;

cout << “ пересекаются\n“;

cout << "End of the program LINE INTERSECTION\n";

return 0; }

// пример 2 с инструкцией выбора (ветвления)

#include <iostream>

using namespace std;

int main ()

{ float x, y;

cout << "Enter argument x: “;

cin >> x;

cout << "Argument x = " << x << endl;

y = 0;

if ((-2 < x) && (x <= -1)) y = x + 2;

else if ((-1 < x) && (x <= 1)) y = - x;

else if ((1 < x) && (x <= 2)) y = x - 2;

cout << "Value function f (" << x << ") = " << y << endl;

return 0;

}

//Ленивые вычисления

#include <iostream>

using namespace std;

int main () {

bool f;

int a=0;

int b=3;

f = (a > 0);

cout << f << endl;

if ((a > 0)) && (b % a ==1) cout << "s1" << endl;

else cout << "s2" << endl;

return 0;

}

№8

i = 0; a = 1; s = 1; while (i < n) { i = i+1; a = a* (m – i + 1); s = s + a; }

i = 0; a = 1; s = 1;

while (i < n) {

a = a* (m – i);

s = s + a;

i = i +1;

}

№9

int i, j, k;

i = 1, j = 1;

while (j > 0)

{ i = i + 1;

j = j*2;

cout << "step i = " << i << " result j = " << j << "\n";

}

№10

unsigned short a;

const unsigned short Max_unSh = 65535;

a = Max_unSh;

cout << "a= " << a << endl;

a = a+1;

cout << "(a + 1) = " << a << endl;

a = a-1;

cout << "(a + 1)-1 = " << a << endl;

a = a*2;

cout << "a*2 = " << a << endl;

short a, b;

const short MinInt = -32768;

const short MaxInt = 32767;

cout << "Beginning of the program \n";

a = MaxInt; b = MinInt;

cout << "a= “ << a << " b=" << b << endl;

a = a+1; b = b-1;

cout << "a= “ << a << " b=" << b << endl;

№11

// k ³ 1 – предусловие цикла

x = k; y =0;

/* y – число отброшенных (“прочитанных”)

разрядов */

while (x!= 0) {

y = y + 1;

x = x / 2; // или x = x >> 1; или x >>= 1;

}

//(y = N (k)) & (x=0)} – постусловие цикла

№13

// Вычисления по заданным x и Epsil

i = 0; //...

dd = -2; d = 0; t = x; s = x; w = -x*x;

//s=s(i) & t=t(i) & i=0

while (fabs(t) > epsil) {

// s=s(i) & t=t(i) & d=d(i) & dd=dd(i) & i<n

i++; //...

dd = dd + 8;

d = d + dd;

t = t * w / d;

s = s + t;

// s=s(i) & t=t(i) & d=d(i) & dd=dd(i) & i<=n

}

// s = s(n) & t=t(n) & tabs(t)<=epsil

№15

typedef float real; // (long) double

real eps, epsil;

int i;

i = 0; eps = 1.0;

while (eps+1.0 > 1.0) { // eps=2^(-i) && (1+eps>1)

eps = eps * 0.5;

i = i + 1;

} //end: eps=2^(-i) &&!(1+eps>1) && (1+2*eps>1)

epsil = 2.0 * eps;

№19

…

double f1 (int x, …); // объявляем функцию-аргумент

int function (…, double (&funArg)(int), …);

…

Int main(){

…

Function (…, f1, …);\

…}

…

double f1 (int x){

…

}

№22

#include <fstream>

…

Int main{

…

ofstream outfile ("result.txt");

ifstream infile (“data.txt”);

infile >> x;

…

outfile << …;

…

outfile.close();

… }

Outfile и infile – аналоги cout и cin. Если infile пуст, то и outfile пуст.

…

№23

ifstream infile ("in_seq.txt");

if (!infile) cout << "Входной файл не открыт!" << endl;

i = 0;

y = -2147483648; // для int, а для short =-32768

while (infile >> x)

{ i++;

if (x > y) y = x;

}

Нас не интересовал номер максимального элемента. Его легко получить, добавив переменную k и изменив тело цикла (тогда понадобится и переменная i).

i = 0; k = 0;

y = -2147483648;

while (infile >> x)

{ i++;

if (x > y) {y = x; k = i;}

}

№25

№1

i = 0;

y = true; last = 0;

while ((infile >> x) && y)

{ i++;

y =(x > last);

last = x;

cout << … << endl;

}

№2

ifstream infile ("in_seq9.txt");

if (!infile) cout << "Входной файл не открыт!" << endl;

i = 0;

y = 0; z = 0; last = 0;

while (infile >> x)

{ i++;

// обновление конкурента:

if (x == last) z++;

else z = 1;

// обновление рекорда:

y = max(y,z);

last = x;

cout << … i << … y << … z << endl;

№26

i = 0;

y = INT_MIN;

z = 0;

while (infile >> x)

{ i++;

// обновление конкурента:

if (z > 0) z = z + x;

else z = x;

// обновление рекорда:

y = max(y,z);

cout << …x << …i << …y <<...z << endl;

}

№27

№1

i = 0;

y = 0;

while (infile >> x)

{ i++;

y = y*t + x;

cout << x << "(" << setw(2)<< i << ") ->:" << y << endl;

}

// y = p (w; t)

№2

i = 0;

y = 0; z = 1;

while (infile >> x)

{ i++;

y = y + x*z;

z = z*t;

}

// (y = p (w; t)) & (z = q (w) = t ⁿ)

№28

unsigned short int i, j;

unsigned char s;

s = char(0);

for (i = 0; i <= 15; i++) {

cout << setw(3) << i << "::";

for (j = 0; j <= 15; j++) {

cout << " " << s;

s++;

}

cout << endl;

}

№29

short q; // q - основание системы счисления, x: 0..(q-1)

char x;

unsigned int y;

unsigned int с0 = ‘0’; //код символа ноль

i = 0;

y = 0;

while (infile >> x)

{ i++;

y = y*q + (unsigned int(x) – c0);

cout << x << "(" << setw(2)<< i << ") ->:" << y << endl;

}

№30.

short j = 0; // на выходе: общее число символов

short i = 0; // на выходе: общее число строк

infile >> noskipws; // включить манипулятор!

while (infile >> x)

{ // x - очередной символ

j++; // подсчет символов

cout << x;

outfile << x;

if (x=='\n') i++; // подсчет строк

}

****
short nText; // общая длина текста

short nLn; // количество строк

float mLn; // средняя длина строки

short maxLn; // максимальная длина строки

short minLn; // минимальная длина строки

float mBlank; //среднее количество пробелов в строке

short nBlank, nnBlank; // общее кол-во пробелов в строке / в тексте

short len; // длина строки

const short SHORT_MIN = -32768;

const short SHORT_MAX = +32767;

void readLn (short &len, short &nBlank)

{ char x;

len = 0;

nBlank = 0;

while ((infile >> x) &&!(x=='\n'))

{

len++;

cout << x;

if (x ==' ') nBlank++;

}

cout << endl;

}

nText = 0; nLn = 0; nnBlank = 0;

maxLn = SHORT_MIN; minLn = SHORT_MAX;

// цикл по строкам

do {

readLn (len, nBlank);

nLn++;

nText += len;

nnBlank += nBlank;

maxLn = max (maxLn,len);

minLn = min (minLn,len);

}

while (infile);

mLn = float (nText) / nLn;

mBlank = float (nnBlank) / nLn;

№31.

const int nMax = 10;

float а[100];

int b[50];

char ch[nMax];

typedef int arr [20]; // описание типа

arr d; // объявление массива (выделение памяти)

int tab[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

Простые примеры действий с массивами (поэлементно)

s = 0;

for (int i=0; i<n; i++) s += a[i];

int k = 0;

for (int i=1; i<n; i++) if (arr[i] > arr[k]) k=i; // k –номер максимального

bool p = true;

int i = 1;

while ((i < n) && p) {

p = (x[i-1] < x[i]);

i ++;

} // p = ‘последовательность возрастает’

№32

uns numMax (const arr1 &arr, const uns n)

{

uns n1 = sizeof(arr)/sizeof(arr[0]);

uns k = 0;

if (n>n1) {cout << "Range error" << endl; }

else {

for (uns i=1; i<n; i++) {

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

}

}

return k;

}

№33

n1 = nElements(a1);

m1 = nElements(b1);

вариант функции numMax:
uns numMax (const arr1 &arr, const uns n)

{ // предусловие: n < = фактического размера массива

uns n1 = nElements(arr);

cout << "Внутри numMax: " << n << ':' << n1 << endl;

uns k = 0;

if ((n==0)||(n>n1)) cout << "Range error" << endl;

else

for (uns i=1; i<n; i++) if (arr[i]>arr[k]) k=i;

return k;

// Постусловие: arr[k] – максимальный элемент массива arr[*]

}

№35

Передача массива по адресу:
// Программа: максимум массива 1 (массив передается по адресу)

#include <iostream>

#include <iomanip>

#include <windows.h>

#define nElements(a) (sizeof(a)/sizeof(a[0]))

using namespace std;

const unsigned short Max_n = 10;

//typedef int[Max_n] arr1;

typedef unsigned short uns;

void WriteArr (const int arr [Max_n], const uns n);

uns numMax (const int arr [Max_n], const uns n);

uns numMin (const int arr [Max_n], const uns n);

int main ()

{

// это вставка для правильной кодировки русских букв

SetConsoleCP(1251);

SetConsoleOutputCP(1251);

//

uns n;

int a [Max_n]= {10, 20, 30, 40, 50, 100, 90, 80, 70, 60};

int b [Max_n+1]= {110, 120, 130, 140, 150, 100, 190, 180, 170, 160, 99};

n = Max_n;

//n = Max_n+1;

//n = 5;

//n = 0;

// Вывод массива:

uns n1 = nElements(a);

cout << "Перед вызовом WriteArr: " << n << ':' << n1 << endl;

if ((n==0)||(n>n1)) cout << "Range error" << endl;

else

WriteArr (a, n);

// Поиск максимального:

cout << "Перед вызовом numMax: " << n << ':' << n1 << endl;

if ((n==0)||(n>n1)) cout << "Range error" << endl;

else

{

uns numberMax = numMax (a, n);

cout << " Номер максимального = " << numberMax << " Значение = " << a[numberMax] << endl;

}

// Поиск минимального:

uns numberMin = numMin (a, n);

cout << " Номер минимального = " << numberMin << " Значение = " << a[numberMin] << endl;

// Поиск минимального:

uns nb = nElements(b);

numberMin = numMin (b, nb);

cout << " Номер минимального = " << numberMin << " Значение = " << b[numberMin] << endl;

return 0;

}

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

uns numMax (const int arr [], const uns n)

{ uns n1 = nElements(arr);

cout << "Внутри numMax: " << n << ':' << n1 << endl;

uns k = 0;

//if ((n==0)||(n>n1)) cout << "Range error" << endl;

//else

for (uns i=1; i<n; i++) if (arr[i]>arr[k]) k=i;

return k;

}

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

uns numMin (const int arr [], const uns n)

{ uns n1 = nElements(arr);

cout << "Внутри numMin: " << n << ':' << n1 << endl;

uns k = 0;

//if ((n==0)||(n>n1)) cout << "Range error" << endl;

//else

for (uns i=1; i<n; i++) if (arr[i]<arr[k]) k=i;

return k;

}

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

void WriteArr (const int arr [], const uns n)

{

uns n1 = nElements(arr);

cout << "Внутри WriteArr: " << n << ':' << n1 << endl;

//if ((n==0)||(n>n1)) cout << "Range error" << endl;

//else

for (uns i=0; i<n; i++) cout << arr[i] << ", ";

cout << endl;

}

Передача массива по ссылке:
// Программа: максимум массива 2 (массив передается по ссылке)

#include <iostream>

#include <iomanip>

#include <windows.h>

#define nElements(a) (sizeof(a)/sizeof(a[0]))

using namespace std;

const unsigned short Max_n = 10;

typedef int arr1 [Max_n];

typedef unsigned short uns;

void WriteArr (const arr1 &arr, const uns n);

uns numMax (const arr1 &arr, const uns n);

uns numMin (const arr1 &arr, const uns n);

int main ()

{

// это вставка для правильной кодировки русских букв

SetConsoleCP(1251);

SetConsoleOutputCP(1251);

//

uns n;

int a [Max_n]= {40, 20, 10, 30, 50, 100, 60, 80, 70, 90};

n = Max_n;

//n = Max_n+5;

//n = 5;

//n = 0;

// Вывод массива:

uns n1 = nElements(a);

cout << "Перед вызовом WriteArr: " << n << ':' << n1 << endl;

//if ((n==0)||(n>n1)) cout << "Range error" << endl;

//else

WriteArr (a, n);

// Поиск максимального:

cout << "Перед вызовом numMax: " << n << ':' << n1 << endl;

//if ((n==0)||(n>n1)) cout << "Range error" << endl;

//else

{

uns numberMax = numMax (a, n);

cout << " Номер максимального = " << numberMax << " Значение = " << a[numberMax] << endl;

}

// Поиск минимального:

uns numberMin = numMin (a, n);

cout << " Номер минимального = " << numberMin << " Значение = " << a[numberMin] << endl;

return 0;

}

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

uns numMax (const arr1 &arr, const uns n)

{ uns n1 = nElements(arr);

cout << "Внутри numMax: " << n << ':' << n1 << endl;

uns k = 0;

if ((n==0)||(n>n1)) cout << "Range error" << endl;

else

for (uns i=1; i<n; i++) if (arr[i]>arr[k]) k=i;

return k;

}

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

uns numMin (const arr1 &arr, const uns n)

{ uns n1 = nElements(arr);

cout << "Внутри numMin: " << n << ':' << n1 << endl;

uns k = 0;

if ((n==0)||(n>n1)) cout << "Range error" << endl;

else

for (uns i=1; i<n; i++) if (arr[i]<arr[k]) k=i;

return k;

}

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

void WriteArr (const arr1 &arr, const uns n)

{

uns n1 = nElements(arr);

cout << "Внутри WriteArr: " << n << ':' << n1 << endl;

if ((n==0)||(n>n1)) cout << "Range error" << endl;

else

for (uns i=0; i<n; i++) cout << arr[i] << ", ";

cout << endl;

}

№36

// Программа: 2D-массив: работа с полным массивом

#include <iostream>

#include <fstream>

#include <iomanip>

#include <windows.h>

#define elementsInRow(a) (sizeof(a[0])/sizeof(a[0][0])) // число столбцов (элементов в строке)

#define elementsInCol(a) (sizeof(a)/sizeof(a[0])) // число строк (элементов в столбце)

#define n_elements(a) (sizeof(a)/sizeof(a[0])) // число элементов в 1-мерном массиве

using namespace std;

const unsigned short n_col = 5;

const unsigned short n_row = 4;

typedef int arr2 [n_row][n_col];

typedef int arr1 [n_col];

typedef arr1 arr21 [n_row];

typedef unsigned short uns;

void WriteArr1 (const arr1 &arr);

void WriteArr2 (const arr2 &arr);

void WriteArr2_1 (const arr2 &arr);

void Copy1 (const arr1 &arr, arr1 &carr);

void Copy2 (const arr2 &arr, arr2 &carr);

int main ()

{

// это вставка для правильной кодировки русских букв

SetConsoleCP(1251);

SetConsoleOutputCP(1251);

//

arr2 a = {{0,1,2,3,4}, {10,11,12,13,14}, {20,21,22,23,24}, {30,31,32,33,34}};

arr1 b = {990,991,992,993,994};

arr2 ca;

arr21 cca;

cout << "Входной массив: " << endl;

WriteArr2 (a);

cout << "Входной массив (по строкам): " << endl;

WriteArr2_1 (a);

Copy2 (a, ca);

cout << "Копия входного массива (по строкам): " << endl;

WriteArr2_1 (ca);

Copy2 (ca, cca);

cout << "Копия копии входного массива (по строкам): " << endl;

WriteArr2_1 (cca);

return 0;

}

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

void Copy1 (const arr1 &arr, arr1 &carr)

{

uns m = n_elements(arr);

for (uns j=0; j<m; j++) carr[j] = arr[j];

}

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

void Copy2 (const arr2 &arr, arr2 &carr)

{

uns m = elementsInRow(arr);

uns n = elementsInCol(arr);

cout << "Внутри Copy2: " << n << '*' << m << endl;

for (uns i=0; i<n; i++) Copy1(arr[i], carr[i]);

}

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

void WriteArr2 (const arr2 &arr)

{

uns m = elementsInRow(arr);

uns n = elementsInCol(arr);

cout << "Внутри WriteArr2: " << n << '*' << m << endl;

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

{ for (uns j=0; j<m; j++)

cout << arr[i][j] << ", ";

cout << endl;

};

}

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

void WriteArr1 (const arr1 &arr)

// вывод строки

{

uns m = n_elements(arr);

cout << "Внутри WriteArr1: " << m << endl;

for (uns j=0; j<m; j++) cout << arr[j] << ", ";

cout << endl;

}

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

void WriteArr2_1 (const arr2 &arr)

// вывод строк как вывод одномерных массивов с помощью WriteArr1

{ uns m = elementsInRow(arr);

uns n = elementsInCol(arr);

cout << "Внутри WriteArr2_1: " << n << '*' << m << endl;

for (uns i=0; i<n; i++) WriteArr1 (arr[i]);

//cout << endl;

}

Работа с не полным массивом:
// Программа: 2D-массив: работа с неполным массивом

#include <iostream>

#include <fstream>

#include <iomanip>

#include <windows.h>

#define elementsInRow(a) (sizeof(a[0])/sizeof(a[0][0])) // число столбцов (элементов в строке)

#define elementsInCol(a) (sizeof(a)/sizeof(a[0])) // число строк (элементов в столбце)

#define n_elements(a) (sizeof(a)/sizeof(a[0])) // число элементов в 1-мерном массиве

using namespace std;

const unsigned short n_col = 5;

const unsigned short n_row = 4;

typedef int arr2 [n_row][n_col];

typedef int arr1 [n_col];

typedef arr1 arr21 [n_row];

typedef unsigned short uns;

void WriteArr1 (const arr1 &arr, const uns m);

void WriteArr2 (const arr2 &arr, const uns n, const uns m);

void WriteArr2_1 (const arr2 &arr, const uns n, const uns m);

void Copy1 (const arr1 &arr, arr1 &carr, const uns m);

void Copy2 (const arr2 &arr, arr2 &carr, const uns n, const uns m);

int main ()

{

// это вставка для правильной кодировки русских букв

SetConsoleCP(1251);

SetConsoleOutputCP(1251);

//

uns n = 3;

uns m = 4;

arr2 a = {{0,1,2,3,4}, {10,11,12,13,14}, {20,21,22,23,24}, {30,31,32,33,34}};

arr1 b = {990,991,992,993,994};

arr2 ca;

arr21 cca;

cout << "Входной массив: " << endl;

WriteArr2 (a, n, m);

cout << "Входной массив (по строкам): " << endl;

WriteArr2_1 (a, n, m);

Copy2 (a, ca, n, m);

cout << "Копия входного массива (по строкам): " << endl;

WriteArr2_1 (ca, n, m);

Copy2 (ca, cca, n, m);

cout << "Копия копии входного массива (по строкам): " << endl;

WriteArr2_1 (cca, n, m);

return 0;

}

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

void Copy1 (const arr1 &arr, arr1 &carr, const uns m)

{

uns m1 = n_elements(arr);

if ((m == 0)|| (m>m1)) cout << "range error in row" << endl;

else

for (uns j=0; j<m; j++) carr[j] = arr[j];

}

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

void Copy2 (const arr2 &arr, arr2 &carr, const uns n, const uns m)

{

uns m1 = elementsInRow(arr);

uns n1 = elementsInCol(arr);

cout << "Внутри Copy2: " << n << '*' << m << "::" << n1 << '*' << m1 << endl;

if ((n == 0)||(n>n1)||(m == 0)|| (m>m1)) cout << "range error in row" << endl;

else

for (uns i=0; i<n; i++) Copy1(arr[i], carr[i], m);

}

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

void WriteArr2 (const arr2 &arr, const uns n, const uns m)

{

uns m1 = elementsInRow(arr);

uns n1 = elementsInCol(arr);

cout << "Внутри WriteArr2: " << n << '*' << m << "::" << n1 << '*' << m1 << endl;

if ((n == 0)||(n>n1)||(m == 0)|| (m>m1)) cout << "range error in row" << endl;

else

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

{ for (uns j=0; j<m; j++)

cout << arr[i][j] << ", ";

cout << endl;

};

}

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

void WriteArr1 (const arr1 &arr, const uns m)

// вывод строки

{

uns m1 = n_elements(arr);

cout << "Внутри WriteArr1: " << m << "::" << m1 << endl;

if ((m == 0)|| (m>m1)) cout << "range error in row" << endl;

else

for (uns j=0; j<m; j++) cout << arr[j] << ", ";

cout << endl;

}

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

void WriteArr2_1 (const arr2 &arr, const uns n, const uns m)

// вывод строк как вывод одномерных массивов с помощью WriteArr1

{ uns m1 = elementsInRow(arr);

uns n1 = elementsInCol(arr);

cout << "Внутри WriteArr2_1: " << n << '*' << m << "::" << n1 << '*' << m1 << endl;

if ((n == 0)||(n>n1)||(m == 0)|| (m>m1)) cout << "range error in row" << endl;

else

for (uns i=0; i<n; i++) WriteArr1 (arr[i], m);

//cout << endl;

}

№37

Вариант 1
for (uns i=0; i<n; i++)

for (uns j=0; j<m; j++)

{ float s = 0;

for (uns k=0; k<t; k++)

s = s + p[i][k]*q[k][j];

r[i][j]=s;

}

Вариант 2
for (uns i=0; i<n; i++)

for (uns j=0; j<m; j++)

{ r[i][j]=0;

for (uns k=0; k<t; k++)

r[i][j] = r[i][j] + p[i][k]*q[k][j];

}

№38

uns numMax (const arr1 &arr)

{ uns m = n_elements(arr);

uns k = 0;

for (uns j=1; j<m; j++)

if (arr[j]>arr[k]) k=j;

return k;

}

void ArgMinMax(const arr2 &arr, uns &p, uns &q)

{ uns p1, q1;

uns m = elementsInRow(arr);

uns n = elementsInCol(arr);

p = 0; q = numMax (arr[0]); // arr[p][q]= текущий минимакс

for (uns i=1; i<n; i++) // обработка строк

{ q1 = numMax (arr[i]);

if (arr[i][q1]< arr[p][q]) {p = i; q = q1;} // обновление минимума

}

// arr[p][q]= Min(i=0..n: Max(j=0..m: arr[i][j]))

}

// Программа: 2D-массив: работа с полным массивом

// нахождение MinMax

#include <iostream>

#include <fstream>

#include <iomanip>

#include <windows.h>

#define elementsInRow(a) (sizeof(a[0])/sizeof(a[0][0])) // число столбцов (элементов в строке)

#define elementsInCol(a) (sizeof(a)/sizeof(a[0])) // число строк (элементов в столбце)

#define n_elements(a) (sizeof(a)/sizeof(a[0])) // число элементов в 1-мерном массиве

using namespace std;

const unsigned short n_col = 5;

const unsigned short n_row = 4;

typedef int arr2 [n_row][n_col];

typedef int arr1 [n_col];

typedef arr1 arr21 [n_row];

typedef unsigned short uns;

uns numMax (const arr1 &arr);

void ArgMinMax(const arr2 &arr, uns &p, uns &q);

void WriteArr1 (const arr1 &arr);

void WriteArr2_1 (const arr2 &arr);

int main ()

{

// это вставка для правильной кодировки русских букв

SetConsoleCP(1251);

SetConsoleOutputCP(1251);

//

arr2 a = {{90,91,92,93,94}, {10,11,12,13,14}, {20,21,22,23,24}, {30,31,32,33,34}};

cout << "Входной массив: " << endl;

WriteArr2_1 (a);

uns p,q;

ArgMinMax(a, p, q);

cout << "Arg MinMax = (" << p << ',' << q << "); MinMax = " << a[p][q] << endl;

return 0;

}

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

void WriteArr1 (const arr1 &arr)

// вывод строки

{ uns m = n_elements(arr);

for (uns j=0; j<m; j++) cout << arr[j] << ", ";

cout << endl;

}

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

void WriteArr2_1 (const arr2 &arr)

// вывод строк как вывод одномерных массивов с помощью WriteArr1

{ uns m = elementsInRow(arr);

uns n = elementsInCol(arr);

for (uns i=0; i<n; i++) WriteArr1 (arr[i]);

}

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

uns numMax (const arr1 &arr)

{ uns m = n_elements(arr);

uns k = 0;

for (uns j=1; j<m; j++)

if (arr[j]>arr[k]) k=j;

return k;

}

void ArgMinMax(const arr2 &arr, uns &p, uns &q)

{ uns p1, q1;

uns m = elementsInRow(arr);

uns n = elementsInCol(arr);

p = 0; q = numMax (arr[0]); // arr[p][q]= текущий минимакс

for (uns i=1; i<n; i++)

{ q1 = numMax (arr[i]);

if (arr[i][q1]< arr[p][q]) {p = i; q = q1;}

}

// arr[p][q]= Min(i=0..n: Max(j=0..m: arr[i][j]))

}

№39

bool isSort (arr1 &a)

{ uns n = nElements(a);

bool p = true;

int i = 1;

while ((i < n) && p)

{

p = (a[i-1] <= a[i]);

i ++;

} // p = ‘последовательность возрастает (не убывает)’

return p;

}

№40

(a[0..i) £ a[i..n)) & Sort*(a, 0, i) & (0 £ i £ n)

Отрезок (сегмент) массива a[p..q) упорядочен:
Sort (a, p, q) º (" i: p < i < q: a[i-1] £ a[i])

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

{

uns k = i;

or (uns j=i+1; j<n; j++)

if (a[j]<a[k]) k=j;

w = a[k]; a[k] = a[i]; a[i] = w; // обмен a[i] и a[k]}

№ 41

№1

void partition1 (arr1 &a, const uns le, const uns ri, const int x, uns &j)

// Pred:…

// Post:…

{

short i = ri; // почему не uns i=ri? См.послед.строку пред.слайда

j = le;

// inv: (le£ j £ i + 1£ri+1) & (a[le..j) < x) & (a(i..ri] ³ x)

while (j <= i)

if (a[j]< x) j++;

else if (a[i] >= x) i--;

else { int w = a[j]; a[j]= a[i]; a[i] = w; j++; i--;}

}

№2

void partition2 (arr1 &a, const uns le, const uns ri, const int x, uns &j)

{

j=le;

for (uns i=le; i<=ri; i++)

if (a[i]< x) {int w = a[j]; a[j]= a[i]; a[i] = w; j++; }

}

№43

i = 0; j = 0; q = 0;

while ((i < n) && (j < m))

{

if (a[i] < b[j]) { c[q] = a[i]; i ++;}

else { c[q] = b[j]; j ++; }

q ++;

}

// переписать a[i..n-1] или b[j..m-1] в c[q..k-1]:

while (i < n) {c[q] = a[i]; i ++; q ++; }

while (j < m) {c[q]:= b[j]; j ++; q ++;}

№44

nc = GCD (n, k); //массив a[0..n)

for (int i = 0; i<nc; i++) //цикл по замкнутым траекториям

{ // i – начальный элемент i-й траектории

int x = a[i]; // отложенный первый элемент

cur = i;

next = cur + k;

if (next >= n) next = next - n;

//cur - куда перемещать, next - откуда перемещать

while (next! = i)

{

a[Cur] = a[Next];

cur:= next;

next:= next + k; if (next > n) next = next - n;

}

// next = i

a[Cur] = x} //каждый элемент перемещается сразу на своё окончательное место

№45

№1 for (uns i = m; i < m + s; i++)

{

a[i] «a[j]; j ++;

}

}

void swapEq (arr1 &a, const uns m, const uns k, const uns s)

{ uns j = k; //в цикле будет j = k – m + i

№2

p = k - m; q = n - k;

while (p!= q)

{ if (p > q)

{ swapEq (a, k - p, k, q);

p = p - q;

}

else

{

swapEq (a, k - p, k + q - p, p);

q = q - p;}

}

}

SwapEq (a, k - p, k, p)

№46

void reverse (arr1 &a, const uns m, const uns n)

{ uns k = (m + n) / 2;

uns j = n;

for (uns i = m; i<k; i++)

{j --; a[i] «a[j];}

}

№48

bool q = false;

i = -1;

while ((i < n)&&!q)

{

i++;

p = (x==a[i]);

}

bool q = false;

i = -1;

while ((i < n)&&!q)

{

p = (x==a[++i]);

}

№49

int m;

int le = 0;

int ri = n;

// inv: 0<=le<=ri<=n & a[le-1]<x<=a[ri]

while (le<ri)

{

m = (le+ri)/2; // д.б. le <= m < ri

if (arr[m]<x) le = m +1;

else ri = m;

}

i = ri;

// 0<=ri<=n & a[ri-1]<x<=a[ri]

№51

№1

template <typename T, typename E>

void binSearch(T &arr, const E x, int &i)

{ uns n = nElements(arr);

// pred: (All 1<=i<n: a[i-1] < a[i])

// post: 0<=i<=n & a[i-1]<x<=a[i], при a[-1]=-@, a[n]=+@

int m;

int le = -1;

int ri = n;

// inv: -1<=le<=ri-1<n & a[le]<x<=a[ri]

while (le+1<ri)

{

m = (le+ri)/2; // д.б. le < m < ri

if (arr[m]<x) le = m;

else ri = m;

}

i = le;

// -1<=le<n & a[le]<x<=a[le+1] & le+1==ri

}

№2

int k = 512; // k=k0=2^j

int le = -1;

if (a[k]<x) le=n-k;

//сегмент локализ.a[le..le+k] (или a[-1..-1+k], или a[n-k..n])

/* т.е. сегмент локализации задается левой границей le и длиной k: (a [le] < x <= a [le + k]) & (k = 512 = 2^j) & (j = 9)

Т.о. в цикле вместо пары переменных le и ri будем использовать пару переменных le и k */

int m;

int k = 512; // k=k0

int le = -1;

if (a[k]<x) le=n-k; // сегмент a[le..le+k] (или a[-1..-1+k], или a[n-k..n])

// inv: -1<=le<n && a[le]<x<=a[le+k] && 0<k<=k0

while (k > 1)

{ k = k/2;

// k - новая длина сегмента, 2*k - старая (текущая) длина

m = le+k; // д.б. le < m < le+2*k

if (a[m] < x) le = m;

}

i = le;

// -1<=le<n & a[le]<x<=a[le+1]

№3

template <typename T, typename E>

void binSearch5(T &a, const E x, int &i)

{ uns n = nElements(a);

// пусть 2^j < n < 2^(j+1) и k0=2^j

// post: -1<=i<n & a[i]<x<=a[i+1]

// например, при n=1000 будет k0=512=2^9

int k = 512; // k=k0

int le = -1;

if (a[k]<x) le=n-k;

// сегмент лок-ии a[le..le+k] (или a[-1..-1+k], или a[n-k..n])

// inv: -1<=le<n && a[le]<x<=a[le+k] && 0<k<=k0

if (a[le+256]<x) le += 256; // a[le]<x<=a[le+256]

if (a[le+128]<x) le += 128; // a[le]<x<=a[le+128]

if (a[le+64]<x) le += 64; // a[le]<x<=a[le+64]

if (a[le+32]<x) le += 32; // a[le]<x<=a[le+32]

if (a[le+16]<x) le += 16; // a[le]<x<=a[le+16]

if (a[le+8]<x) le += 8; // a[le]<x<=a[le+8]

if (a[le+4]<x) le += 4; // a[le]<x<=a[le+4]

if (a[le+2]<x) le += 2; // a[le]<x<=a[le+2]

if (a[le+1]<x) le += 1; // a[le]<x<=a[le+1]

i = le; // -1<=le<n & a[le]<x<=a[le+1]

}

Дата добавления: 2015-09-29