# 概率模拟

### 随机模拟问题

https://www.jianshu.com/p/788ac5f312ff 使用这篇文章的模板作为可视化的模板，只需要填写逻辑就好了。

            AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Blue);
int w = canvasWidth / money.length;
for (int i = 0; i < money.length; i++) {
AlgorithmHelper.fillRectangle(graphics2D, i * w + 1, canvasHeight - money[i], w - 1, money[i]);
}

    private void run() {
while (true){
frame.render(money);
AlgorithmHelper.pause(DELAY);
for (int i = 0; i < money.length; i++) {
if (money[i] > 0){
int j = (int) (Math.random() * money.length);
money[i] -= 1;
money[j] += 1;
}
}
}
}

            for (int k = 0; k < 50; k++)
for (int i = 0; i < money.length; i++) {
if (money[i] > 0) {
int j = (int) (Math.random() * money.length);
money[i] -= 1;
money[j] += 1;
}
}

#### 蒙特卡洛方法

，正方形的面积

，上除于下，就可以得到

，首先可以随机一个点，看看这个点是落在了园内还是园外，如果打的点多，那么就是可以知道这个园的大概形状。

    private void run() {
for (int i = 0; i < N; i++) {
//System.out.println("run");
frame.render(circle, points);
AlgorithmHelper.pause(DELAY);
int x = (int)(Math.random() * frame.getCanvasWidth());
int y = (int)(Math.random() * frame.getCanvasHeight());
}
}

            AlgorithmHelper.setStrokeWidth(graphics2D, 3);
AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Blue);
AlgorithmHelper.strokeCircle(graphics2D, circle.getX(), circle.getY(), circle.getR());
for (int i = 0; i < points.size(); i++) {
Point p = points.get(i);
if (circle.contain(p)) {
AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Red);
} else {
AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Blue);
}
AlgorithmHelper.fillCircle(graphics2D, p.x, p.y, 3);
//System.out.println("draw");
}

# 排序可视化

#### SelectionSort

            int w = canvasWidth / data.N();
AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.LightBlue);
for (int i = 0; i < data.N(); i++) {
if (i < data.orderIndex) {
AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Red);
} else {
AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Grey);
}
if (i == data.currentIndex) {
AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Indigo);
}
if (i == data.currentComperent) {
AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.LightBlue);
}
AlgorithmHelper.fillRectangle(graphics2D, i * w, canvasHeight - data.get(i), w - 1, data.get(i));
}

}

Frame的画图函数主要构成部分，其余的都是模板，为了抽象性，所以把selection的数据集中起来形成一个新的类，包括了生成数据等等。

public class SelectionSortData {
private int[] numbers;
public int orderIndex = -1;
public int currentIndex = -1;
public int currentComperent = -1;

public SelectionSortData(int N, int randomBound) {
numbers = new int[N];
for (int i = 0; i < N; i++) {
numbers[i] = (int) (Math.random() * randomBound) + 1;
//System.out.println(numbers[i]);
}
}

public void setData(int orderIndex, int currentComperent, int currentIndex){
this.currentIndex = currentIndex;
this.currentComperent = currentComperent;
this.orderIndex = orderIndex;
}

public int N(){
return numbers.length;
}

public int get(int index){
if (index < 0 || index >= numbers.length){
throw new IllegalArgumentException("index is illgel!");
}
return numbers[index];
}

public void swap(int i, int j){
int t = numbers[i];
numbers[i] = numbers[j];
numbers[j] = t;
}

}

    private void run() {
data.setData(0,-1,-1);
frame.render(data);
AlgorithmHelper.pause(DELAY);

for (int i = 0; i < data.N(); i++) {
int midIndex = i;
data.setData(i, -1, midIndex);
frame.render(data);
AlgorithmHelper.pause(DELAY);

for (int j = i+1; j < data.N(); j++) {
data.setData(i, j, midIndex);
frame.render(data);
AlgorithmHelper.pause(DELAY);

if (data.get(j) < data.get(midIndex)){
midIndex = j;
data.setData(i, j, midIndex);
frame.render(data);
AlgorithmHelper.pause(DELAY);

}
}
data.swap(i, midIndex);
data.setData(i+1, -1, -1);
frame.render(data);
AlgorithmHelper.pause(DELAY);
}
data.setData(data.N(), -1,-1);
frame.render(data);
AlgorithmHelper.pause(DELAY);

}

#### InsertionSort

            int w = canvasWidth / data.N();
for (int i = 0; i < data.N(); i++) {
if (i < data.orderIndex){
AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Red );
}else {
AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Grey);
}
if (i == data.currentIndex){
AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.LightBlue);
}
AlgorithmHelper.fillRectangle(graphics2D, i * w, canvasHeight - data.get(i), w - 1, data.get(i));
}
}

    private void run() {
setData(-1, -1);
for (int i = 0; i < data.N(); i++) {
setData(i, i);
for (int j = i; j > 0 && data.get(j) < data.get(j - 1); j--) {
data.swap(j, j - 1);
setData(i+1, j-1);
}
setData(i, -1);
}
setData(data.N(), -1);
}

private void setData(int orderIndex, int currentIndex){
data.orderIndex = orderIndex;
data.currentIndex = currentIndex;
frame.render(data);
AlgorithmHelper.pause(DELAY);
}

#### MergeSort

public class MergeData {
private int[] numbers;
public int l, r;
public int mergeIndex;

public MergeData(int N, int randomBound) {
numbers = new int[N];
for (int i = 0; i < N; i++) {
numbers[i] = (int) (Math.random() * randomBound) + 1;
//System.out.println(numbers[i]);
}
}

public int N(){
return numbers.length;
}

public int get(int index){
if (index < 0 || index >= numbers.length){
throw new IllegalArgumentException("index is illgel!");
}
return numbers[index];
}

public void set(int index, int num){
if (index < 0 || index >= numbers.length){
throw new IllegalArgumentException("index is illgel!");
}
numbers[index] = num;
}

public void swap(int i, int j){
int t = numbers[i];
numbers[i] = numbers[j];
numbers[j] = t;
}

}

    private void run() {
setData(-1, -1, -1 );
Merge(0, data.N()-1);
setData(0, data.N()-1, -1);
}

private void Merge(int l, int r) {
if (l >= r) {
return;
}
setData(l, r, -1);
int mid = (l + r) / 2;
Merge(l, mid);
Merge(mid + 1, r);
merge(l, r, mid);
}

private void merge(int l, int r, int mid) {
int[] array = new int[r - l + 1];
for (int i = l; i <= r; i++) {
array[i - l] = data.get(i);
}
int i = l, j = mid + 1;
int index = l;
while (i <= mid && j <= r) {
if (array[i - l] < array[j - l]) {
data.set(index, array[i - l]);
i++;
index++;
} else {
data.set(index, array[j - l]);
j++;
index++;
}
setData(l, r, index);
}
if (i <= mid) {
for (int k = i; k <= mid; k++) {
data.set(index, array[k - l]);
index++;
setData(l, r, index);
}
} else if (j <= r) {
for (int k = j; k <= r; k++) {
data.set(index, array[k - l]);
index++;
setData(l, r, index);
}
}
}

#### QuickSort

public class QuickSortData {
private int[] numbers;
public int l, r;
public int Index;

public QuickSortData(int N, int randomBound) {
numbers = new int[N];
for (int i = 0; i < N; i++) {
numbers[i] = (int) (Math.random() * randomBound) + 1;
//System.out.println(numbers[i]);
}
}

public int N(){
return numbers.length;
}

public int get(int index){
if (index < 0 || index >= numbers.length){
throw new IllegalArgumentException(index + "index is illgel!");
}
return numbers[index];
}

public void set(int index, int num){
if (index < 0 || index >= numbers.length){
throw new IllegalArgumentException("index is illgel!");
}
numbers[index] = num;
}

public void swap(int i, int j){
int t = numbers[i];
numbers[i] = numbers[j];
numbers[j] = t;
}

}

    private void run() {
setData(-1, -1, -1);
QuickSort(0, data.N() - 1);
setData(0, data.N() - 1, -1);
}

private void QuickSort(int l, int r) {
if (l >= r) {
return;
}
setData(l, r, -1);
int mid = partition(l, r);
QuickSort(l, mid - 1);
QuickSort(mid + 1, r);
frame.render(data);
AlgorithmHelper.pause(DELAY);
}

private int partition(int l, int r) {
int v = data.get(l);
int i = l + 1;
int j = r;
setData(l, r, l);
while (true) {
while (i <= r && data.get(i) < v) {
i++;
}
while (j >= l + 1 && data.get(j) > v) {
j--;
}
if (i > j) {
break;
}
data.swap(i, j);
setData(l, r, l);
i++;
j--;
}
data.swap(j, l);
setData(l, r, j);
return j;
}

# 走迷宫

#### 显示迷宫

public class MazeData {
private char[][] maze;
private int N, M;
public static final char ROAD = '#';
public static final char WALL = ' ';
public MazeData(String fileName) {
if (fileName == null) {
throw new IllegalArgumentException("filename can't be null!");
}
Scanner scanner = null;
try {
File file = new File(fileName);
if (!file.exists()) {
throw new IllegalArgumentException("File is not exist!");
}
FileInputStream fileInputStream = new FileInputStream(file);
scanner = new Scanner(new BufferedInputStream(fileInputStream), "UTF-8");
String nm = scanner.nextLine();
String[] nmC = nm.trim().split("\\s+");
N = Integer.parseInt(nmC[0]);
M = Integer.parseInt(nmC[1]);
maze = new char[N][M];
for (int i = 0; i < N; i++) {
String line = scanner.nextLine();
if (line.length() != M) {
throw new IllegalArgumentException("Message of file is not completed!");
}
for (int j = 0; j < M; j++) {
maze[i][j] = line.charAt(j);
}
}
} catch (Exception e) {
e.printStackTrace();
} finally {
if (scanner != null) {
scanner.close();
}
}
}

public char getMaze(int i, int j) {
if (!inArea(i, j)) {
throw new IllegalArgumentException("out of range!");
}
return maze[i][j];
}

public boolean inArea(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M;
}

public int N() {
return N;
}

public int M() {
return M;
}
}

            int w = canvasWidth / data.M();
int h = canvasHeight / data.N();
for (int i = 0; i < data.N(); i++) {
for (int j = 0; j < data.M(); j++) {
if (data.getMaze(i, j) == MazeData.ROAD){
AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.LightBlue);
}else {
AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.White);
}
AlgorithmHelper.fillRectangle(graphics2D, j * w, i * h, w, h);
}
}

#### 深度优先

    private boolean go(int x, int y) {
if (!data.inArea(x, y)) {
throw new IllegalArgumentException("Paramenter is illgel!");
}
data.visited[x][y] = true;
setData(x, y, true);
if (x == data.getExitX() && y == data.getExitY()) {
return true;
} else {
for (int i = 0; i < 4; i++) {
int nexX = x + direction[i][0];
int nexY = y + direction[i][1];
if (data.inArea(nexX, nexY) &&
data.getMaze(nexX, nexY) == MazeData.ROAD &&
!data.visited[nexX][nexY]) {
if (go(nexX, nexY)) {
return true;
}
}

}
setData(x, y, false);
return false;
}
}

    private boolean go_iteration() {
Stack<Position> stack = new Stack<>();
Position entrance = new Position(data.getEntanceX(), data.getEntanceY());
stack.push(entrance);
data.visited[entrance.getX()][entrance.getY()] = true;
while (!stack.isEmpty()) {
Position position = stack.pop();
setData(position.getX(), position.getY(), true);
for (int i = 0; i < 4; i++) {
int newX = position.getX() + direction[i][0];
int newY = position.getY() + direction[i][1];

if (newX == data.getExitX() && newY == data.getExitY()) {
setData(newX, newY, true);
return true;
}

Position newPosition = new Position(newX, newY, position);
if (data.inArea(newPosition.getX(), newPosition.getY()) &&
data.getMaze(newPosition.getX(), newPosition.getY()) == MazeData.ROAD
&& !data.visited[newPosition.getX()][newPosition.getY()]) {
stack.push(newPosition);
data.visited[newPosition.getX()][newPosition.getY()] = true;
}
}
}
return false;
}

#### 广度优先

    private boolean go_level() {
Queue<Position> queue = new LinkedList<>();
Position position = new Position(data.getEntanceX(), data.getEntanceY());
data.visited[position.getX()][position.getY()] = true;
while (!queue.isEmpty()) {
Position position1 = queue.poll();
setData(position1.getX(), position1.getY(), true);
for (int i = 0; i < 4; i++) {
int newX = position1.getX() + direction[i][0];
int newY = position1.getY() + direction[i][1];

if (newX == data.getExitX() && newY == data.getExitY()) {
findPath(position1);
setData(newX, newY, true);
return true;
}
Position newPosition = new Position(newX, newY, position1);

if (data.inArea(newPosition.getX(), newPosition.getY()) &&
data.getMaze(newPosition.getX(), newPosition.getY()) == MazeData.ROAD
&& !data.visited[newPosition.getX()][newPosition.getY()]) {
data.visited[newPosition.getX()][newPosition.getY()] = true;
}
}
}
return false;
}

# 生成迷宫

0 条评论

• ### Data Structure_Visualization排序可视化走迷宫生成迷宫扫雷

选择排序很简单，遍历所有元素，查看一下他们的之后最小的元素和当前元素交换即可。模板函数使用上面的swing模板。为了更清楚显示出排序的过程，可以用不同颜色代表排...

• ### Data Structure_Visualization

选择排序很简单，遍历所有元素，查看一下他们的之后最小的元素和当前元素交换即可。模板函数使用上面的swing模板。为了更清楚显示出排序的过程，可以用不同颜色代表排...

• ### Data Structure_图图论带权图

交通运输，社交网络，互联网，工作的安排，闹区活动等等都可以用到图论处理。图可以分成两大类，一类是无向图，就是没有方向的，就好像两个人都互相认识一样，有向图就是单...

• ### 小根堆的Java实现

堆是完全二叉树的数组形式，由于堆没有指针指向，所以可以利用下标来模拟指向，假设 i 为父节点，那么 2i+1 为左孩子，2i+2 为右孩子。假设 i 为当前节点...

• ### 《一文说透数据结构》系列之什么是堆？看这一篇就够了

本文将首先介绍什么是堆，然后介绍了堆的插入和删除操作，最后给出了堆的代码实现，并进行了测试。

• ### 计算机视觉 OpenCV Android | Mat像素操作

下面演示对Mat对象中的每个像素点的值都进行取反操作，并且分别用这三种方法实现像素操作。

• ### 浅谈我对动态规划的一点理解---大家准备好小板凳，我要开始吹牛皮了~~~

前言 作为一个退役狗跟大家扯这些东西，感觉确实有点。。。但是，针对网上没有一篇文章能够很详细的把动态规划问题说明的很清楚，我决定还是拿出我的全部家当，来跟大家分...

• ### Leetcode 132 Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a p...

• ### 【自然框架】元数据的数据库结构的详细说明和示例（一）：项目描述部分

1、　Manage_Function（节点信息） 字段名 中文名 类型 大小 默认值 说明 FunctionID 节点ID int 4 1 主键 Pa...

• ### cf914D. Bash and a Tough Math Puzzle(线段树)

可以这么想，如果能成功的话，我们可以把那个数改成$1$，这样比$x$大的数就不会对答案产生影响了。