// generate a random "walk" of letters from A to Z in a 2D grid, assuming a
// character set with contiguous values of uppercase letters (e.g. ASCII);
// stops if the "walker" gets stuck
// example of a successful walk:
// A . . . I J K . . .
// B C F G H . L . . .
// . D E . . . M . . .
// . . . . . O N . . .
// . . . . . P . . . .
// . . . . . Q . . . .
// . . . . . R S . . .
// . . . . . . T U . .
// . . . . . . . V W Z
// . . . . . . . . X Y
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <ctype.h>
#define GRID_SIZE 10
// movement directions
#define DIR_NUM 4
#define UP 0
#define LEFT 1
#define DOWN 2
#define RIGHT 3
#define ANY (-1)
bool can_move(int dir, size_t rpos, size_t cpos, size_t rows, size_t cols,
char grid[rows][cols]);
void generate_random_walk(size_t rows, size_t cols, char grid[rows][cols]);
void print_array(size_t rows, size_t cols, char grid[rows][cols]);
int main(void)
{
char grid[GRID_SIZE][GRID_SIZE] = { 0 };
generate_random_walk(GRID_SIZE, GRID_SIZE, grid);
print_array(GRID_SIZE, GRID_SIZE, grid);
return 0;
}
void print_array(size_t rows, size_t cols, char grid[rows][cols])
{
for (size_t r = 0; r < rows; ++r) {
for (size_t c = 0; c < cols; ++c) {
char grid_c = grid[r][c];
printf(" %c ", isalpha(grid_c) ? grid_c : '.');
}
putchar('n');
}
}
// checks all the directions by default (ANY)
bool can_move(int dir, size_t rpos, size_t cpos, size_t rows, size_t cols,
char grid[rows][cols])
{
bool cangoup = (rpos > 0) && grid[rpos - 1][cpos] == 0;
bool cangoleft = (cpos > 0) && grid[rpos][cpos - 1] == 0;
bool cangodown = (rpos < rows - 1) && grid[rpos + 1][cpos] == 0;
bool cangoright = (cpos < cols - 1) && grid[rpos][cpos + 1] == 0;
switch (dir) {
case UP: return cangoup;
case LEFT: return cangoleft;
case DOWN: return cangodown;
case RIGHT: return cangoright;
default: return cangoup || cangoleft || cangodown || cangoright; // ANY
}
}
void generate_random_walk(size_t rows, size_t cols, char grid[rows][cols])
{
size_t rpos, cpos;
srand((unsigned int) time(NULL));
rpos = cpos = 0;
grid[0][0] = 'A';
for (char c="B"; c <= 'Z' && can_move(ANY, rpos, cpos, rows, cols, grid); c++) {
// move in a random direction
for (int dir;;) {
dir = rand() % DIR_NUM;
if (can_move(dir, rpos, cpos, rows, cols, grid)) {
switch (dir) {
case UP: --rpos; break;
case LEFT: --cpos; break;
case DOWN: ++rpos; break;
case RIGHT: ++cpos; break;
default:
printf("Impossible movement direction.n");
exit(EXIT_FAILURE);
}
break; // break out of the loop
}
}
// leave a trail
grid[rpos][cpos] = c;
}
}
Подводя итог, эта программа печатает сетку со случайным блужданием заглавных букв по порядку. Если «шагающий» не может двигаться в любом направлении из-за недостатка пространства вокруг него (вверх, вниз, влево и вправо), ходьба прекращается.
Помимо общих советов относительно моего кода, которые вы можете мне дать, меня интересуют две вещи:
Я читал, что функции обычно не должны принимать более 2–3 параметров; Как вы думаете, мои функции действительно «страдают» от приема более трех параметров, и если да, как мне это смягчить?
Должен ли я использовать
size_t
при переходе по массиву или подобному, или я должен использоватьint
вместо? Я прочитал здесь, на Stack Exchange, различные мнения по этому поводу: некоторые люди говорятsize_t
всегда следует использовать, поскольку это, по сути, неопределенное поведение, если размер массива больше, чемMAX_INT
и т. д., в то время как другие говорят, что неподписанные и подписанные типы не следует смешивать (и мне обычно приходится использовать их в выражениях, которые подвергаются обычным арифметическим преобразованиям), и это основной источник ошибок. С прагматической точки зрения, я считаю, что мне следует использовать обычныйint
. Я заметил еще одну вещь: если мне действительно нужно использовать эти счетчики для выполнения некоторых вычислений: в этих случаях у меня действительно нет выхода, и то, что я в конечном итоге делаю, просто кастинг и молитва, надеясь, что массив имеет разумный размер (т. е. что мойsize_t
счетчик, или результат выражения не выходит за пределы представимого диапазона дляint
). Я думаю, это даже хуже, чем использоватьint
с самого начала, так как интерфейс чтоsize_t
Тип предоставляет не соответствует, поэтому мой код «лжет» и себе, и читателю.
Обратите внимание, что я бы использовал enum
вместо #define
определения направлений, но моя книга еще не дошла до них, поэтому я думаю, что нам не следует сосредотачиваться на этом. Кроме того, в том же упражнении я рассмотрел и другие вопросы, но представленный там код / подход несколько отличается.
1 ответ
Ответы на ваши вопросы
Я читал, что функции обычно не должны принимать более 2–3 параметров.
Я бы не стал слишком об этом беспокоиться. Однако, если у вас есть много параметров, вам следует подумать, действительно ли они необходимы, и, возможно, есть ли способ сгруппировать их в struct
, и передавать ли это по значению или по указателю. Например, вашему коду может быть полезно создать struct
для хранения координат, например:
typedef struct {
size_t row;
size_t col;
} vec2;
Затем вы можете уменьшить количество передаваемых параметров:
bool can_move(int dir, vec2 pos, vec2 size, char grid[size.row][size.col])
Это не должно изменить сгенерированный машинный код, но сделает его более читаемым.
Должен ли я использовать
size_t
при переходе по массиву или подобному, или я должен использоватьint
вместо?
Я бы рекомендовал использовать size_t
. В частности, size_t
гарантированно будет достаточно большим, чтобы вместить размер любого массива, и поэтому вы должны также использовать его для индекса массива. Он также беззнаковый, что упрощает проверку границ. Смешивание size_t
а также int
это, конечно, плохо, убедитесь, что у вас включены предупреждения компилятора, чтобы компилятор мог предупредить вас о таких проблемах и исправить все предупреждения, которые вы видите.
то, что я в конечном итоге делаю, это просто молюсь и молюсь,
Не делай этого! Используйте типы последовательно и избегайте ненужных приведений. Похоже, вы все еще изучаете C, вы, вероятно, выучите все подробности в какой-то момент, и тогда вместо этого вы будете рассуждать об этих вещах. Если вам все еще нужно где-то провести кастинг, и вы не уверены, что это безопасно, спросите Переполнение стека.
Избегайте ненужных предварительных деклараций
Если вы измените порядок, в котором функция появляется в исходном файле, вам больше не нужны форвардные объявления. Это позволяет избежать повторения, а также позволяет избежать потенциальных ошибок.
Использовать enum
или же static const
переменные
Обратите внимание, что я бы использовал
enum
вместо#define
определения направлений,
Правильно, используя enum
здесь было бы намного лучше.
но моя книга до них еще не дошла, так что я думаю, нам не стоит заострять внимание на этом.
Мы должны, поскольку другие люди также могут прочитать ваш вопрос здесь, и они не могут быть ограничены тем, насколько далеко они находятся в конкретной книге! Но это нормально, если вы хотите проигнорировать это на данном этапе. Но помимо enum
s, еще одна возможность избежать использования #define
использовать static const
переменные:
static const int UP = 0;
static const int LEFT = 1;
...
static const int ANY = -1;
Преимущество этого состоит в том, что эти константы теперь имеют правильный тип, и вам не нужно беспокоиться о том, как работает макро-подстановка, поэтому меньше шансов забыть круглые скобки, как если бы вы правильно добавили к ANY
.
Вам все еще нужно использовать #define
для GRID_SIZE
хотя, к сожалению, const
переменная недостаточно хороша для C, поскольку размер при объявлении множество (если это не VLA).
Приятнее for
-заявления
Реализация случайного блуждания выглядит неплохо. Тем не менее for
петли в generate_random_walk()
для меня это выглядит немного странно. Внешний for
-loop начинается в B
вместо A
. Я бы лучше написал так, чтобы это выглядело так:
for (char c="A"; c <= 'Z'; c++) {
...
}
Потому что в этом случае четко указано, что вы хотите выполнить цикл из 'A'
к 'Z'
в одной строке. Внутренний for
-statement тоже странный, он ничего не делает, кроме delcare переменной. По сути, это бесконечный цикл и более идеальный способ записи, использующий while (true)
. Я бы структурировал это примерно так:
for (char c="A"; c <= 'Z'; c++) {
grid[rpos][cpos] = c;
if (!can_move(ANY, ...)) {
break;
}
while (true) {
int dir = rand() % DIR_NUM;
...
}
}
Другой вариант — изменить can_move()
поэтому он попытается сделать случайный ход и вернется true
в случае успеха или false
если бы он больше не мог двигаться. Затем его также следует переименовать, например, в try_random_move()
и используйте указатели для rpos
а также cpos
поэтому они могут быть изменены:
bool try_random_move(size_t *rpos, size_t *cpos, ...) {
bool cangoup = (*rpos > 0) && grid[*rpos - 1][*cpos] == 0;
bool cangoleft = (*cpos > 0) && grid[*rpos][*cpos - 1] == 0;
bool cangodown = (*rpos < rows - 1) && grid[*rpos + 1][*cpos] == 0;
bool cangoright = (*cpos < cols - 1) && grid[*rpos][*cpos + 1] == 0;
if (!(cangoup || cangoleft || cangodown || cangoright)) {
return false;
}
while (true) {
int dir = rand() % DIR_NUM;
...
}
}
потом generate_random_walk()
упрощается до:
void generate_random_walk(size_t rows, size_t cols, char grid[rows][cols])
{
size_t rpos = 0;
size_t cpos = 0;
for (char c="A"; c <= 'Z'; c++) {
grid[rpos][cpos] = c;
if (!try_random_move(&rpos, &cpos, rows, cols, grid)) {
break;
}
}
}
Как избежать «бесконечного» цикла
Вы выбираете случайное направление, а затем проверяете, возможно ли движение в этом направлении. Если нет, вы пробуете другое случайное направление. Проблема в том, что для выбора правильного направления может потребоваться много попыток, так как со случайными числами никогда не знаешь. Возможный способ избежать повторения случайных попыток — просто попробовать все оставшиеся возможности. Однако вы должны быть осторожны, чтобы не вводить случайная предвзятость в вашем алгоритме.
Большое спасибо за каждую мелочь. У меня есть несколько дополнительных вопросов по поводу некоторых советов: 1. «Если вы измените порядок, в котором функция появляется в исходном файле, вам больше не нужны форвардные объявления». В чем заключается реальный недостаток форвардных деклараций? Прямо сейчас они очень полезны, потому что мне даже не нужно думать о порядке объявления функций — зачем мне вообще? Вы думаете, что эти функции чрезмерно «загрязняют» пространство имен?
— JCC
2. Причина
for
цикл начинается с'B'
потому что если я начну с'A'
, Идентификатор всегда необходимо проверить в цикле,c == 'A'
, потому что обычно вы не можете попасть в позицию (0, 0) (ты уже там). Вы думаете, что это лишняя лишняя проверка каждый итерация цикла не имеет значения? (Я знаю, что использовал эти 4bool
s в той другой функции, которая всегда оцените около 8 сравнений, что также является ненужным вычислением.) В качестве общего принципа приемлем ли этот шаблон:for (int i = 0; ...) { if (i == 0) dosomething(); /*rest of the loop*/ }
?— JCC
3. Не вопрос, а комментарий к
try_random_move
: это именно то, что я сделал бы, просто мы еще не сделали указатели, но хорошо, что вы включили это, чтобы люди это знали. На самом деле у меня есть вопрос: я не уверен, почему мне следует избегать таких вещей, какfor (int dir;;)
потому что здесь я проясняю декларация что я буду использовать толькоdir
внутри этогоfor
цикл, сохраняя при этом бесконечный цикл. Я думаю, что это очень удобно, потому что это одно объявление, которое не повторяется снова и снова (что является своего рода раздражением).— JCC
1. Вы можете сделать опечатку в форвардном объявлении. Дело не в загрязнении пространства имен, используйте
static
для этого. 2. Если вы начинаете цикл сc = 'A'
, первое, что вы делаете в теле, это безоговорочно пишетеc
в текущую позицию в сетке, поэтому нет необходимости в явной проверке. 3. Объявление переменной внутри телаfor
-loop не «повторяется снова и снова». Место в стеке резервируется для него только один раз, даже без включенной оптимизации компилятора (см. godbolt.org/z/ea7fcP667 для примера).— Г. Сон
1. Итак, вы говорите, что возможное несоответствие между объявлением в прототипе функции и определением может привести к ошибкам? Это то, что ты имеешь в виду?
— JCC
Показывать 3 больше комментариев