下面的代码构成了一个完整可编译的示例。
您的问题是关于从随机生成器中丢弃位。让我们看看如何编写一个不丢弃位的随机比特对源代码。它要求
RAND_MAX的形式为2^
n−1，但这个想法可以扩展以支持任何
RAND_MAX >= 3。
#include <cassert>
#include <cstdint>
#include <cstdlib>
class RandomBitSource {
int64_t bits = rand();
int64_t bitMask = RAND_MAX;
static_assert((int64_t(RAND_MAX + 1) & RAND_MAX) == 0, "No support for RAND_MAX != 2^(n-1)");
public:
auto get2Bits() {
if (!bitMask)
bits = rand(), bitMask = RAND_MAX;
else if (bitMask == 1)
bits = (bits * (RAND_MAX+1)) | rand(), bitMask = (RAND_MAX+1) | RAND_MAX;
assert(bitMask & 3);
bitMask >>= 2;
int result = bits & 3;
bits >>= 2;
return result;
}
};
然后，随机游走的实现可以如下所示。请注意，
' 数字分隔符是 C++14 的一个很方便的特性。
#include <vector>
using num_t = int;
struct Coord { num_t x, y; };
struct Walk {
std::vector<Coord> points;
num_t min_x = {}, max_x = {}, min_y = {}, max_y = {};
Walk(size_t n) : points(n) {}
};
auto makeWalk(size_t n = 250'000)
{
Walk walk { n };
RandomBitSource src;
num_t x = 0, y = 0;
for (auto& point : walk.points)
{
const int bits = src.get2Bits(), b0 = bits & 1, b1 = bits >> 1;
x = x + (((~b0 & ~b1) & 1) - ((b0 & ~b1) & 1));
y = y + (((~b0 & b1) & 1) - ((b0 & b1) & 1));
if (x < walk.min_x)
walk.min_x = x;
else if (x > walk.max_x)
walk.max_x = x;
if (y < walk.min_y)
walk.min_y = y;
else if (y > walk.max_y)
walk.max_y = y;
point = { x, y };
}
return walk;
}
通过更多的努力，我们可以将其制作成一个交互式的Qt应用程序。按下回车键会生成一张新的图片。
该图像以显示屏的本机分辨率查看，即它映射到物理设备像素。该图像不进行缩放。相反，在需要时旋转以更好地适应屏幕的方向（纵向 vs 横向）。这是为了横屏监视器爱好者 :)
#include <QtWidgets>
QImage renderWalk(const Walk& walk, Qt::ScreenOrientation orient)
{
using std::swap;
auto width = walk.max_x - walk.min_x + 3;
auto height = walk.max_y - walk.min_y + 3;
bool const rotated = (width < height) == (orient == Qt::LandscapeOrientation);
if (rotated) swap(width, height);
QImage image(width, height, QPixmap(1, 1).toImage().format());
image.fill(Qt::black);
QPainter p(&image);
if (rotated) {
p.translate(width, 0);
p.rotate(90);
}
p.translate(-walk.min_x, -walk.min_y);
auto constexpr hueStep = 1.0/720.0;
qreal hue = 0;
int const huePeriod = walk.points.size() * hueStep;
int i = 0;
for (auto& point : walk.points) {
if (!i--) {
p.setPen(QColor::fromHsvF(hue, 1.0, 1.0, 0.5));
hue += hueStep;
i = huePeriod;
}
p.drawPoint(point.x, point.y);
}
return image;
}
#include <ctime>
int main(int argc, char* argv[])
{
srand(time(NULL));
QApplication a(argc, argv);
QLabel view;
view.setAlignment(Qt::AlignCenter);
view.setStyleSheet("QLabel {background-color: black;}");
view.show();
auto const refresh = [&view] {
auto *screen = view.screen();
auto orientation = screen->orientation();
auto pixmap = QPixmap::fromImage(renderWalk(makeWalk(), orientation));
pixmap.setDevicePixelRatio(screen->devicePixelRatio());
view.setPixmap(pixmap);
view.resize(view.size().expandedTo(pixmap.size()));
};
refresh();
QShortcut enter(Qt::Key_Return, &view);
enter.setContext(Qt::ApplicationShortcut);
QObject::connect(&enter, &QShortcut::activated, &view, refresh);
return a.exec();
}
