Программирование на языке высокого уровня C++. Лекция 4.5. Задачи, которые решаются с помощью массивов

1. Программирование на языке высокого уровня

Богатов Р.Н.
Программирование
на языке высокого уровня
C++ ► Лекция 4.5 ► Примеры задач, которые
решаются с помощью массивов
Кафедра АСОИУ ОмГТУ, 2016

2. Инициализация массива

//#include <stdio.h> ...<conio.h> ...<locale.h> ...<stdlib.h> ...<time.h>
...
if (mode==0) // случайное заполнение массива
int main()
{
{
srand( (unsigned)time(NULL) );
setlocale(LC_ALL, "Russian");
for(int i=0; i<N; i++)
const int N=10;
a[i] = rand();
int a[N];
}
else // ручной ввод массива
int mode;
{
do {
printf("Введите все %d элементов массива\n", N);
printf("Заполнить массив случ. числами (0) или вручную (1)? ");
for(int i=0; i<N; i++) {
scanf("%d", &mode);
printf("a[%2d] = ", i+1);
fflush(stdin);
Сброс остатков ввода (на случай, если будет введён
scanf("%d", &a[i]);
"мусор", который не может быть считан в переменную
} while(mode!=0 && mode!=1);
fflush(stdin);
целочисленного типа)
}
if (mode==0) // случайное заполнение массива
}
{
...
// вывод массива
}
printf("Ваш массив: ");
else // ручной ввод массива
for(int i=0; i<N; i++)
{
printf("%d ", a[i]);
...
...
}

3. Задача про пятаки и трёшки

// прямое решение на основе остатка от деления
Задача
банкомата:
заданную
int
A, для
B; ////
искомое
число
пятаков
исумму
трёшекденег (натуральное число
int A,
B;
искомое
число
пятаков
и трёшек
больше
int x = семи)
n % 5; выдать с помощью максимального числа пятаков и,
int A, B; // искомое число пятаков и трёшек
for
(int
i = 0; i < 5; i++)
if (x
== 0)
если
придётся,
некоторого
числа
трёшек.
int x = n % 5;
{
if ((n - i * 3) % 5 == 0)
switch (x)
A = nB / =5;i;
{
B = 0;
// решение
через подбор количества пятёрок
case 0:
}
...
Aelse
= (n - B * 3) / 5;
A = n / 5;
B = 0;
if (x == 1)
int n;
A, scanf("%d",
B; // искомое
число
пятаков ицелое
трёшек
int
&n);
//
исходное
>7
break;
{
case
1:
A = (n - 6) / 5;
A = (n - 6) / 5;
for A,
(B BB;
= =0;
B++)
2; ;искомое
int
//
число пятаков и трёшек
B =0;2;(n - B * 3) % 5 != 0; B++) ;
for (B =
} if ((n - B * 3) % 5 == 0)
break;
else break;
case 2:
for (A if
= n/5;
A--)
(x == A>=0;
2)
A = (n - 12) / 5;
{
A = if
(n ((n
- B -* A3)* /5)5;% 3 == 0)
B = 4;
A = (n - 12) / 5;
break;
break;
B = 4;
int }A, B; // искомое число пятаков и трёшек
case 3:
A = (n - 3) / 5;
B = (n else
- A * 5) / 3;
B = 1;
int G[5]
if =(x{==0,3)2, 4, 1, 3 };
break;
B = G[n{ % 5];
default:
printf("%d
+ /-3*%d",
A*= 3)
(n
3)
A = (n -= B5*%d
5; / 5;n, A, B);
A = (n - 9) / 5;
B = 1;
...
B = 3;
}
break;
else
}
{
A = (n - 9) / 5;
B = 3;
}

4. Произведение матриц

// произведение прямоугольных матриц константного размера
const int N=7, M=4, L=5;
int a[N][M], b[M][L], c[N][L];
// инициализация
...
// вывод массива
...
// инициализация
...
// вывод массива
...
массива a
a на экран
массива b
b на экран
// произведение матриц
for(int i=0; i<N; i++)
for(int j=0; j<L; j++)
{
int s = 0;
for(int k=0; k<M; k++)
s += a[i][k]*b[k][j];
c[i][j] = s;
}
// вывод результата на экран
...

5. Перебор всех расстановок

// общий случай: получение всех расстановок
// единиц в массиве произвольной длины
Математическая постановка задачи: получить
все варианты
#include <stdio.h>
#include <conio.h>
расстановок единиц в множестве из N элементов.
const int N=10;
Постановка задачи для программиста: перебрать
все способы
int a[N];
заполнения массива длины N нулями и единицами.
void main()
// частный случай: получение всех расстановок единиц
{
// в массиве длиной N<31
for(int n=0; n<(1<<N); n++)
{
...
// вывод массива
for(int n=0; n<(1<<N); n++)
printf("\r%d: ", n);
{
for(int i=0; i<N; i++)
for(int i=0; i<N; i++)
printf("%d", a[i]);
a[i] = (n & (1<<i))>0 ? 1 : 0;
for(int i=0; i<N; i++)
if (a[i]==1) // переполнение
a[i] = 0;
else // прибавление единицы
{
a[i] = 1;
break;
}
// вывод массива
printf("\r%d: ", n);
for(int i=0; i<N; i++)
printf("%d", a[i]);
Вопросы:
}
1) Почему
... алгоритм для общего случая работает быстрее?
2) Почему во втором алгоритме массив нужно выводить
до обработки массива?
3) Какой из алгоритмов удобнее взять за основу для
решения задачи расстановки трёхзначных чисел?
}
_getch();
}