如题，今天专业课老师提的一个很有意思的问题。
问题内容：
有一个4x4棋盘，左上角和右下角各有一个棋子，一个棋子移动完后另一个棋子才能移动，棋子每次只会向上下左右的其中一个方向移动一格，若向边界方向移动则移动后的位置在另一边的最远处（比如棋子在左上角向上移动，它就会到左下角），问平均移动多少次两个棋子会撞上（在同一位置）
要求用C++代码编程并输出结果。
ps：不是作业，真的是老师随口提的一个问题。其他编程语言的大佬也可以来看看呀。
假设移动n次后，(n->无限大)。那么可以看做，一个棋子落在某个位置的概率是1/16.那么两个棋子在同一位置就是1/16X1/16=1/256。那么平均256次有一次会撞上。
#include <bits/stdc++.h>
using namespace std;
int xx[] = {1, -1, 0, 0};
int yy[] = {0, 0, 1, -1};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n = 4;
int m = 100000;
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(seed);
uniform_int_distribution<int> dist(0, 3);
int sum = 0;
for(int j=0;j<m;j++){
vector<vector<int> > mp(n + 1, vector<int> (n + 1));
vector<vector<int> > mp2(n + 1, vector<int> (n + 1));
bool f = false;
int ans = 0;
function<void(int, int, int, int)> Dfs = [&](int x1, int y1, int x2, int y2){
if(mp[x1][y1] || mp2[x2][y2]) return;
if(f) return;
// cout << x1 << ' ' << y1 << ' ' << y1 << ' ' << y2 << '\n';
mp[x1][y1] = 1;
mp2[x2][y2] = 1;
int num = 0;
int num2 = 0;
// cout << num << ' ' << num2 << '\n';
if(num < 4){
int dx = x1;
int dy = y1;
int dx2 = x2;
int dy2 = y2;
for(int i=0;i<4;i++){
int dx = x1 + xx[i];
int dy = y1 + yy[i];
if(dx == 0) dx += n;
if(dy == 0) dy += n;
if(dx == n + 1) dx -= n;
if(dy == n + 1) dy -= n;
if(mp[dx][dy] == 1) num += 1;
// cout << dx << ' ' << dy << ' ';
dx = x2 + xx[i];
dy = y2 + yy[i];
if(dx == 0) dx += n;
if(dy == 0) dy += n;
if(dx == n + 1) dx -= n;
if(dy == n + 1) dy -= n;
if(mp2[dx][dy] == 1) num2 += 1;
// cout << dx << ' ' << dy << '\n';
}
while(num < 4 && num2 < 4){
int k = dist(rand_num);
dx = x1 + xx[k];
dy = y1 + yy[k];
if(dx == 0) dx += n;
if(dy == 0) dy += n;
if(dx == n + 1) dx -= n;
if(dy == n + 1) dy -= n;
// cout << x1 << ' ' << y1 << ' ' << y1 << ' ' << y2 << '\n';
if(dx == x2 && dy == y2){
f = true;
return;
}
if(!mp[dx][dy]){
num += 1;
ans += 1;
num2 = 0;
for(int i=0;i<4;i++){
dx = x2 + xx[i];
dy = y2 + yy[i];
if(dx == 0) dx += n;
if(dy == 0) dy += n;
if(dx == n + 1) dx -= n;
if(dy == n + 1) dy -= n;
if(mp2[dx][dy] == 1) num2 += 1;
// cout << dx << ' ' << dy << '\n';
}
while(num2 < 4){
k = dist(rand_num);
dx2 = x2 + xx[k];
dy2 = y2 + yy[k];
if(dx2 == 0) dx2 += n;
if(dy2 == 0) dy2 += n;
if(dx2 == n + 1) dx2 -= n;
if(dy2 == n + 1) dy2 -= n;
// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
if(dx2 == dx && dy2 == dy){
f = true;
return;
}
if(!mp2[dx2][dy2]){
num2 += 1;
ans += 1;
Dfs(dx, dy, dx2, dy2);
}
}
}
}
}
};
Dfs(1, 1, n, n);
// cout << ans << '\n';
sum += ans;
}
cout << sum * 1.0 / m;
return 0;
}
你觉得我的随机化搜索有没有问题，看起来好像在7.5附近
感觉不该标记，改一下
#include <bits/stdc++.h>
using namespace std;
int xx[] = {1, -1, 0, 0};
int yy[] = {0, 0, 1, -1};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n = 4;
int m = 1000;
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(seed);
uniform_int_distribution<int> dist(0, 3);
int t = 100;
double res = 0.0;
while(t--){
int sum = 0;
for(int j=0;j<m;j++){
vector<vector<int> > mp(n + 1, vector<int> (n + 1));
vector<vector<int> > mp2(n + 1, vector<int> (n + 1));
bool f = false;
int ans = 0;
int ok = 0;
function<void(int, int, int, int, int)> Dfs = [&](int x1, int y1, int x2, int y2, int op){
if(f) return;
if(ans >= 10000) return;
if(op == 0){
int k = dist(rand_num);
int dx = x1 + xx[k];
int dy = y1 + yy[k];
if(dx == 0) dx = n;
if(dy == 0) dy = n;
if(dx == n + 1) dx = 1;
if(dy == n + 1) dx = 1;
ans += 1;
if(dx == x2 && dy == y2){
f = true;
return;
}
Dfs(dx, dy, x2, y2, op ^ 1);
}else{
int k = dist(rand_num);
int dx = x2 + xx[k];
int dy = y2 + yy[k];
if(dx == 0) dx = n;
if(dy == 0) dy = n;
if(dx == n + 1) dx = 1;
if(dy == n + 1) dy = 1;
ans += 1;
if(dx == x1 && dy == y1){
f = true;
return;
}
Dfs(x1, y1, dx, dy, op ^ 1);
}
};
Dfs(1, 1, n, n, 0);
// cout << ans << '\n';
if(ans != 10000) sum += ans;
}
// cout << sum * 1.0 / m << '\n';
res += sum * 1.0 / m;
}
cout << fixed << setprecision(5) << res / 100 << '\n';
return 0;
}
让这两个人乱走，结果好像在120左右，去除掉极端情况，可能需要作图看一下极限
也有可能是计算每个格子的期望然后加和，可能也能得到答案
我说一下我的思路，首先考虑，相遇的总次数，然后累加所有的相遇情况的步数，最后总步数除以总次数。总步数好算。剩下考虑总的相遇情况的次数。假如次数恒定，结果就是恒定的，假如次数不恒定，那结果我就不知道了
这个问题的解法，是以A在左上角，并且B在右下角为初始条件，经过n次移动后相遇，记录相遇时的移动次数，作为一个样本。然后从初始位置开始，再次模拟随机移动，产生下一个样本。通过大量的随机试验，统计平均次数。
一开始以为是持续移动，没有每次从初始位置开始，所以统计数为16。
按照这种测试方法，大量试验的统计数概率，大约是18.67。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
uint32_t move2meet(void)
{
uint32_t move_cnt = 0;
int ax = 0, ay = 0;
int bx = 3, by = 3;
int move_x[4] = {0,0,3,1}; // 上下左右
int move_y[4] = {3,1,0,0};
int dir;
// 每次循环是A走一步和B走一步，相当于2步
do {
move_cnt++;
dir = rand() % 4;
ax = (ax + move_x[dir]) % 4;
ay = (ay + move_y[dir]) % 4;
if (ax == bx && ay == by) {
break;
}
move_cnt++;
dir = rand() % 4;
bx = (bx + move_x[dir]) % 4;
by = (by + move_y[dir]) % 4;
if (ax == bx && ay == by) {
break;
}
} while (!(ax == bx && ay == by));
return move_cnt;
}
void cal(int loop)
{
int i;
uint32_t move_sum = 0;
for (i = 0; i < loop; ++i) {
move_sum += move2meet();
}
printf("loop %d, move_sum %d, average %0.2f\n", loop, move_sum, (float)move_sum/loop);
}
int main()
{
srand((unsigned)time(NULL));
cal(1000);
cal(10000);
cal(100000);
return 0;
}
loop 1000, move_sum 17934, average 17.93
loop 10000, move_sum 185250, average 18.52
loop 100000, move_sum 1866686, average 18.67