Для отличавшихся (но по детским причинам не для всех) на какой-то там олимпиаде в прошлое занятие граждан повторял про алгоритмы с возвратом.
Из принципиально «нового» — объяснил про область применимости этих алгоритмов: любые задачи, в которых решение можно строить пошагово, оснащённые способом убедиться, что конкретное пока недостроенное решение уже сейчас не приведёт ни к какому правильному решению при любом ходе процесса его достройки до полного. Менее абстрактно: «если мы поняли, что едем на поезде в сторону окончания направления без ветвлений и наша станция назначения не находится в данном ответвлении, то стоит вернуться на шаг (несколько шагов) назад и скорректировать свои действия».
Из технического: напомнил про эквивалентность конструкций
for (…) {
if (“condition”) {
some;
actions;
here;
}
}
for (…) {
if (!“condition”)
continue;
some;
actions;
here;
}
Изучали алгоритмы с возвратом на примере классических задач с N ферзями и конём (адын штук). Также (у)поминались различные графы, схемы метро, карты, Леонард Эйлер и значение приставки а в некоторых словах.
Пример к объяснению про ферзей:
/*
* Handles new column on the chessboard.
*
* Arguments:
* - column: column number;
* - d: chessboard contents, 2D array,
* xi(i, j) defines its real layout;
* - N: chessboard dimensions.
*/
void move(int column, int *d, int N)
{
int j;
if (column >= N) {
print_board(d, N);
return;
}
for (j = 0; j < N; j++) {
if (!check_vert(j, column, d, N))
continue;
d[xi(j, column)] = 1;
move(column + 1, d, N);
d[xi(j, column)] = 0;
}
return;
}
Чуть абстрактная сказка про коня:
struct knight_moves {
int dx, dy;
} h[] = { {1, 2}, {2, 1}, {-1, 2}, {2, -1},
{1, -2}, {-2, 1}, {-1, -2}, {-2, -1} };
/*
* Tries next moves of the knight.
*
* Arguments:
* - n: number of the current move, 0-based;
* - x, y: knight coordinates;
* - d: chessboard contents, 2D array,
* xi(i, j) defines its real layout;
* - N: chessboard dimensions.
*/
void move(int n, int x, int y, int *d, int N)
{
int i;
if (n >= N*N) {
print_board(d, N);
return;
}
for (i = 0; i < sizeof(h)/sizeof(h[0]); i++) {
int next_x, next_y;
next_x = x + h[i].dx;
next_y = y + h[i].dy;
if (!check_move(next_x, next_y, d, N))
continue;
d[xi(next_y, next_x)] = 1;
move(n + 1, next_x, next_y, d, N);
d[xi(next_y, next_x)] = 0;
}
}
Дорассказывал, кому не успел, про битовые поля и операции, да про структуры. Код, относящийся к этим вопросам, разбиравшийся на уроке:
#define F_CP866 0x01
#define F_CP1251 0x02
#define F_KOI8R 0x04
#define T_CP866 0x08
#define T_CP1251 0x10
#define T_KOI8R 0x20
...
int main(char *argv[], int argc)
{
int mode = 0;
...
if (!strncmp(argv[1], "cp866"))
mode = mode | F_CP866;
else if (!strncmp(argv[1], "cp1251"))
mode |= F_CP1251;
else if (!strncmp(argv[1], "koi8-r"))
mode |= F_KOI8R;
else {
fprintf(stderr, "Bad source encoding '%s'.\n", argv[1]);
exit(1);
}
...
if (mode & F_KOI8R) {
<... обрабатываем случай раскодирования из KOI8-R ...>
}
}
struct from_args {
char *name; /* Encoding name */
unsigned char mask; /* Bit mask, OR-flavor */
};
...
int main(char *argv[], int argc)
{
struct from_args from_a[] = {
{"cp866", F_CP866},
{"cp1251", F_CP1251},
{"koi8-r", F_KOI8R}
};
unsigned char mode = 0;
int i, matched;
...
for (i = 0, matched = 0; i < sizeof(from_a)/sizeof(from_a[0]); i++) {
if (!strncmp(argv[1], from_a[i].name)) {
mode |= from_a[i].mask;
matched = 1;
break;
}
}
if (!matched) {
fprintf(stderr, "Bad source encoding '%s'.\n", argv[1]);
exit(1);
}
}
#define COUNTOF(a) (sizeof(a)/sizeof((a)[0]))
for (i = 0; i < COUNTOF(from_a); i++) {
if (!strncmp(argv[1], from_a[i].name)) {
mode |= from_a[i].mask;
break;
}
}
if (i == COUNTOF(from_a) {
fprintf(stderr, "Bad source encoding '%s'.\n", argv[1]);
exit(1);
}
#undef COUNTOF
Второй, намного лучше:
struct from_args {
char *name; /* Encoding name */
unsigned char mask; /* Bit mask, OR-flavor */
};
...
int main(char *argv[], int argc)
{
struct from_args from_a[] = {
{"cp866", F_CP866},
{"cp1251", F_CP1251},
{"koi8-r", F_KOI8R},
{NULL, 0}
};
struct from_args *pfa = &from_a[0];
unsigned char mode = 0;
...
while (pfa->name) {
if (!strncmp(argv[1], pfa->name)) {
mode |= pfa->mask;
break;
}
pfa++;
}
if (!pfa->name) {
fprintf(stderr, "Bad source encoding '%s'.\n", argv[1]);
exit(1);
}
...
}
Рассказывал про манипуляцию битами внутри целых типов, экономию целого байта (берегущего мегабайт, естественно), битовые поля, маски и операции.
Разбирали программу, которая принимает как минимум два аргумента-переключателя режимов (в двух группах — перекодировщик, в одной — заполнялка массивов с режимом транспозиции массива):
В паре групп успел рассказать про структуры: записную книжку, ее реализацию с помощью четырех «прошитых» общим индексом массивов:
char *names[]; char *addrs[]; char *phones[]; int ages[]; names[0] = "Volodia Ulianov"; addrs[0] = "Red square"; phones[0] = "None" ages[0] = 147;
Ну и про избавление от такой напасти посредством введения-таки структур:
struct pb_entry {
char *name;
char *addr;
char *phone;
int age;
};
...
int main(void)
{
struct pb_entry e, *pe;
struct pb_entry p_book[100];
e.name = "Eygene";
e.addr = "Kurchatov square, 1";
e.phone = "+7 499 196-77-77";
e.age = 36;
p_book[0] = e;
pe = &e;
if (CURRENT_YEAR > 2017)
pe->age += (CURRENT_YEAR - 2017);
...
p_book[1] = *pe;
...
}
«Напоминалка»: