Задачи и упражнения

1. Вместо одной функции SINCOS (§ 2) cоставить и использовать две функции так, как было показано в § 3. Первая с именем MyCos вычисляет значение y, а вторая MySin — z, то есть каждая функция имеет один результат и должна использовать оператор return.Сравните вызов функций SINCOS, MyCos и MySin.

2. (Повторение). Изменить функцию SINCOS (§ 2) таким образом, чтобы оба результата, и y и z, вычислялись в одном цикле одновременно.

3. (Повторение). Изменить функцию SINCOS (§ 2), заменив оператор do … while на while.

4. (Повторение). Изменить функцию SINCOS (§ 2), заменив оператор do … while на for.

5. (Повторение). В функции main (см. 2.1) вместо оператора for записать while.

6. Для каждой пары введенных целых чисел найти их сумму и произведение двумя способами: с помощью одной функции типа void, которая возвращает и сумму, и произведение двух чисел; с помощью двух функций с одним результатом типа int, одна из которых возвращает сумму, а вторая — произведение двух целых чисел.

void SumMult (int, int, int &, int &);

int MySum (int, int );

int MyMult (int, int );

int main()

{ int a, b, r1, r2; cout<<endl<<" 0 0 -- exit"<<endl; cin>>a>>b;

while(a!=0 || b!=0 )

{ SumMult(a,b,r1,r2) ;

cout<<a<<" + "<<b<<" = "<<r1<<endl;

cout << a << " * " << b << " = " << r2 << endl;

cout << a << " + " << b << " = " << MySum (a,b) << endl;

cout << a << " * " << b << " = " << MyMult(a,b) << endl;

cin >> a >> b;

}

return 0; }

void SumMult ( int x, int y, int &s, int &p)

{ s=x+y; p=x*y;

}

int MySum (int x, int y)

{ return x+y;

}

int MyMult (int x, int y)

{ return x*y; }

7.Составить и использовать следующие функции: функцию типа int для нахождения наибольшего из двух чисел с помощью оператора if; функцию типа int для нахождения наибольшего из двух чисел с помощью тернарной операции; функцию типа void для нахождения наибольшего из двух чисел с помощью тернарной операции.

int maxfun1 (int, int);

int maxfun2 (int, int);

void maxfun3 (int , int , int &r);

int main()

{ long int a, b;

cout<<endl<<"Введите два числа; 0, 0 – выход : "<<endl;

cin>>a>>b;

while(a!=0 || b!=0 )

{ if (a==b)

cout<<endl<<a<<" is equal "<<b<<endl;

else { cout<<"max of "<<a<<" and "<<b<<"= "

<<maxfun1(a,b)<<" " <<maxfun2(a,b);

int mymax;

maxfun3(a,b,mymax); cout<<" "<<mymax<<endl;

}

cin>>a>>b;

}

return 0;

}

int maxfun1(int x,int y) // первый вариант

{ if (x>y) return x;

else return y;

}

int maxfun2(int x,int y) // второй вариант

{ return x>y?x:y; }

void maxfun3(int x,int y,int &r) //третий вариант

{ r=x>y?x:y;

}

8. Составить логическую функцию, которая определяет, принадлежит ли точка плоскости с координатами (x, y) части круга радиуса R, находящейся в первой или третьей четверти. Оси координат и окружность, ограничивающая указанные секторы, принадлежат области. В головной программе последовательно ввести координаты точек плоскости и для каждой из них вывести “Да” или “Нет” в зависимости от принадлежности точки указанной выше области.

bool Test(float, float, float); // или bool Test (float x, float y, float R);

main()

{ float X,Y, R;

do // ввод радиуса с контролем ввода

{ cout<<"R= "; cin>>R;

if (R<=0) cout<<"Radius must be positive, repeat\n ";

}

while (R<=0);

int gy; gy=wherey()+1;

cout<<"X=1000 && Y=1000 -- exit";

while (1)

{ gotoxy(2,gy); cin>>X; gotoxy(10,gy); cin>>Y;

if (X==1000 && Y==1000) break;

if (Test(X, Y, R)) { gotoxy(20, gy++); cout<<"Yes\n"; }

else { gotoxy(30, gy++); cout<<"No\n"; }

}

return 0;

}

bool Test (float x, float y, float r)

{ return x*x+y*y<=r*r && x*y>=0;

// или return x*x+y*y<=r*r && (x>=0 && y>=0 || x<=0 && y<=0);

// или if (x*x+y*y<=r*r && x*y>=0) return true; else return false;

}

9. Составить функцию, которая вычисляет значение бесконечной суммы ряда y = 1–c точностью e. В головной программе вычислить значения этой функции для x = –1.6, –1.4, –1.2, …, 1.4, 1.6 и вывести их на экран.

float MyCos(float x);

main()

{ printf("\n x MyCos(x) cos(x)");

for(float X=-1.6; X<=1.600001; X+=0.2)

printf("\n%6.1f%11.7f%11.7f", X, MyCos(X), cos(X));

/* Для контроля вывели также значение этой же суммы, вычисленное с помощью стандартной функции */

getch(); return 0;

}

float MyCos(float x)

{ float y=0, u=1, k=-1, eps=1e-6; // или eps=0.000001;

while (fabs(u)>eps)

{ y+=u; k+=2; u*=(-1)*x*x/(k*(k+1));

}

return y;

}

10. В одномерном целочисленном массиве найти числа с наибольшим количеством единиц в его двоичном представлении.

unsigned NUM (int);

main()

{ const n=5; long A[n]={10, 7, 14, 2, 19};

unsigned maxnum=0, num2;

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

{ num2=NUM(A[i]);

if (num2>maxnum) maxnum = num2;

}

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

if (NUM(A[i])==maxnum) cout<<A[i]<<" ";

getch(); return 0;

}

unsigned NUM (int a) // функция находит количество единиц

{ unsigned num=0; // в двоичном представлении одного целого числа

while (a)

{ num+=a%2; a/=2;

}

return num;

}

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

12. Составить и проверить функцию нахождения наибольшего общего делителя двух натуральных чисел.

13. Составить и проверить функцию, которая переставляет цифры заданного целого числа N1 в обратном порядке и получает новое число N2. Например, если N1=425, то N2=524.

14. В массиве целых чисел найти количество чисел с наименьшим количеством цифр. Например, в массиве {123, 34, 56, 1000, 20, 55000, 777, 11} таких чисел 4, это 34, 56, 20, 11. Составить и использовать функцию, которая определяет количество цифр одного целого числа.

15. В целочисленном одномерном массиве все симметричные числа, т. е. числа, которые одинаково читаются слева направо и справа налево (палиндромы, перевертыши), заменить нулем. Составить и использовать логическую функцию для определения, является ли одно целое число симметричным.

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

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

18, 19. Среди заданных координатами вершин треугольников на плоскости найти треугольник с наименьшим периметром (площадью). Составить и использовать следующие функции: вычисление длины отрезка по координатам двух вершин; вычисление периметра (площади) одного треугольника; головную функцию, в которой находим координаты требуемого треугольника.

20, 21. Найти периметр (площадь) выпуклого многоугольника, если заданы координаты его вершин в порядке обхода. Составить и использовать следующие функции: вычисление длины отрезка по координатам двух вершин; вычисление периметра (площади) одного треугольника; головную функцию, в которой находим периметр (площадь) многоугольника.

§ 4. Одномерные массивы в функциях.
Сортировка массива

П р и м е р 1. Рассортировать одномерный целочисленный массив по возрастанию последней цифры числа. Если последняя цифра одинакова, то сортировать по возрастанию самого числа.

void MyInp(int x[],int size); // Ввод массива размерности size

void MyOut(int x[],int size); // Вывод массива размерности size

// Сортировка массива по возрастанию последней цифры числа void MySort(int x[],int size);

int DIGIT(int num) // Для одного числа получаем последнюю цифру

{ return abs(num % 10);

};

void RR(int &u, int &v) // Перестановка двух целых чисел

{ int t;

t=u; u=v; v=t;

};

// DIGIT и RR – это встраиваемые функции (см. 6.1).

int main()

{ const n=5; int A[n]; MyInp(A,n);

cout<<" Integer random array\n"; MyOut(A,n);

MySort(A,n);

cout<<" \n\Array after sorting\n"; MyOut(A,n);

getch(); return 0;

} ;

void MyInp(int x[],int size)

{ // или randomize();

for(int i=0; i<size; i++)

cin>>x[i]; // или x[i]=random(100)-50;

} ;

void MyOut(int x[],int size)

{ cout<<endl;

for(int i=0; i<size; i++)

cout<<x[i]<<" ";

} ;

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

В первом, плохом, варианте и внутренний, и внешний циклы можно повторить (size-1) раз, где size — размерность массива.

for ( int k=1; k<size; k++)

for(int j=0; j<size-1; j++)

if ( x[j]>x[j+1] )

RR(x[j], x[j+1]);

Улучшим внутренний цикл. Легко заметить, что после первого этапа наибольшее число массива будет в конце, то есть займёт своё место независимо от того, где оно было до сортировки. После второго шага второе наибольшее число займёт предпоследнее место, и так далее. Поэтому если вначале надо анализировать все пары чисел, то на втором шаге последнее число можем не “трогать”, так как оно уже на своём месте. Аналогично, на каждом последующем этапе количество сравниваемых пар можно на одну уменьшать. Тогда внутренний цикл будет таким:

for(int j=0; j<size-k; j++) …

Оптимизация внешнего цикла. Всегда ли надо (size-1) просмотров массива? Для “хорошего” массива, который частично рассортирован, результат можем получить и раньше. Как c учётом этого организовать внешний цикл? Предлагается следующее. Просмотр и анализ массива будем продолжать, если на предыдущем этапе была хотя бы одна перестановка. Если окажется, что ни одну пару не переставляли, то это означает, что массив рассортировали и можно выйти из внешнего цикла. Это реализуется с помощью переменной flag. Если на каком-то шаге была хотя бы одна перестановка, переменная flag изменит своё значение на единицу, и внешний цикл продолжаем. В противном случае, если не было ни одной перестановки, останется flag=0, и сортировка прекращается.

int flag=1, k; k=size;

while (flag)

{ k--; flag=0;

for(int j=0; j<k; j++)

if (x[j]>x[j+1]) { RR(x[j], x[j+1]);

flag=1;

}

}

Используемый при написании программы сортировки приём можно назвать методом последовательного (поэтапного) улучшения алгоритма (программы). Вначале составляем наиболее простой, не обязательно эффективный алгоритм. Его можем запрограммировать и отладить. При этом возможны, но не обязательны, некоторые упрощения постановки задачи. Отладив такой упрощённый вариант, улучшаем алгоритм и (или) программу и снимаем ограничения на условие задачи.

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

1) вначале строим массив параметров (массив D последних цифр);

2) сравниваем не сами числа, а эти параметры. И если параметры равны, только тогда сравниваем сами числа, если по условию требуется, как в нашем примере, “двойная” сортировка;

3) переставляем не только сами числа, но и их параметры, чтобы они соответствовали тем же числам, что и до сортировки.

void MySort(int x[],int size)

{ // Строим массив последних цифр

int D[20]; // 20 — наибольшая размерность

for(int i=0; i<size; i++)

D[i]=DIGIT(x[i]); /* В качестве фактического параметра функции можно использовать индексированную переменную, то есть элемент массива. В качестве формального параметра индексированную переменную записывать нельзя */

int flag=1, k; k=size;

while (flag)

{ k--; flag=0;

for(int j=0; j<k; j++)

// сравниваем параметры чисел, а если они равны, то и сами числа

if ( D[j]>D[j+1] || x[j]>x[j+1] && D[j]==D[j+1] )

{ RR(D[j], D[j+1]); // переставляем параметры

RR(x[j], x[j+1]); // переставляем исходные числа

flag=1;

}

} // the end of while

} ; // the end of function MySort

Независимо от того, является массив входным или выходным, он передаётся одинаково в качестве параметра функции по следующим правилам:

· в заголовке функции указываем тип элементов массива, его имя и пустые квадратные скобки. Чаще всего в качестве параметра указывается и его размерность (size в примере). Этим самым мы подчёркиваем, что работаем с массивом произвольной размерности;

· в тексте функции, как обычно, доступ к элементам массива осуществляется с помощью индексов;

· в вызывающей функции объявляем массив обычным образом;

· при вызове функции в качестве фактического параметра записываем только имя массива A (не A[I], не A[N], не A[], не A[5]) или &A[0] — адрес начала массива, т. е. номер первого байта элемента A[0].

П р и м е р 2.

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

2) Составить функцию для вывода массива.

3) Составить логическую функцию, которая возвращает true или false в зависимости от того, рассортирован ли массив по возрастанию.

4) В main проверить эти функции.

void MyInp(int x[],int size);

void MyOut(int x[],int size);

bool Sorted(int x[],int size);

int main(int argc, char* argv[])

{ const n=5; int A[n]; MyInp(A,n);

cout<<" Integer array"; MyOut(A,n);

if (Sorted(A,n))

cout<<" \n рассортирован по возрастанию \n";

else cout<<" \n не рассортирован по возрастанию \n";

getch(); return 0;

} ;

void MyInp(int x[],int size)

{ for(int i=0; i<size; i++)

{ textcolor (15);

do // цикл для ввода одного числа с проверкой

{ cin>>x[i];

if (x[i]>0) break;

textcolor (12);

cprintf("Error. Repeat. ");

} while (1);

}

} ;

void MyOut(int x[], int size)

{ cout<<endl;

for(int i=0; i<size; i++) cout<<x[i]<<" ";

} ;

bool Sorted(int x[], int size)

{ for (int i=0; i<size-1; i++)

if (x[i]>x[i+1])

return false;

return true;

}