admin 管理员组

文章数量: 893893

使用蒙特卡罗法解决道填图题目

题目

如下所示，有6个圈，将1，2，3，4，5，6分别填入以下圈中，使所有连线上的和相同。

分析

由于数据量很小，完全可以尝试穷举法来解决问题。考虑到题目不需要列出所有的解，所以我们不需要写个六层循环来穷举出所有的解，只需使用蒙特卡罗法，进行随机测试，命中一个解即可。

具体实现可以使用数组完成，如下图所示：

这里使用数组 d a t a data data 中的第 i i i 个元素分别表示不同圈的数字，只要满足条件： d a t a [ 0 ] + d a t a [ 3 ] + d a t a [ 5 ] = = d a t a [ 1 ] + d a t a [ 3 ] + d a t a [ 4 ] = = d a t a [ 2 ] + d a t a [ 4 ] + d a t a [ 5 ] data[0] + data[3] + data[5] == data[1] + data[3] + data[4] == data[2] + data[4] + data[5] data[0]+data[3]+data[5]==data[1]+data[3]+data[4]==data[2]+data[4]+data[5] 则输出结果跳出循环；否则，循环继续，直到满足条件为止。

实现

class Demo1{public static void main(String[] args){int[] data = {1, 2, 3, 4, 5, 6};int testTimes = 0;while(true){testTimes ++;for(int i = 0; i < data.length; i++){int p = (int)(Math.random() * data.length);int temp = data[i];data[i] = data[p];data[p] = temp;}if(data[0] + data[3] + data[5] == data[1] + data[3] + data[4] && data[0] + data[3] + data[5] == data[2] + data[4] + data[5]){for(int v: data)System.out.print(v + "\t");break;}}System.out.println("\tTotal test times: " + testTimes);}
}

注：为了了解循环的次数，使用了一个自加的testTimes进行计数。

结果

1       2       3       6       4       5               Total test times: 8
1       5       3       4       2       6               Total test times: 9
1       3       5       6       2       4               Total test times: 39
5       4       6       3       2       1               Total test times: 1
4       2       6       5       3       1               Total test times: 34
2       4       6       5       1       3               Total test times: 7
5       6       4       1       2       3               Total test times: 2
4       2       6       5       3       1               Total test times: 12
4       6       2       1       3       5               Total test times: 12
6       4       2       1       5       3               Total test times: 9
6       5       4       1       3       2               Total test times: 23
2       1       3       6       5       4               Total test times: 5
3       1       2       5       6       4               Total test times: 7
6       4       5       2       3       1               Total test times: 11
4       6       5       2       1       3               Total test times: 131
4       5       6       3       1       2               Total test times: 51

根据运行结果，我们可以以下最终结果。

同时，我们还发现，循环次数非常随机，最少只需要1次即可获得解，而最多需要131次，两者巨大，说明随机性非常强。

本文标签： 使用蒙特卡罗法解决道填图题目

版权声明：本文标题：使用蒙特卡罗法解决道填图题目 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687603986h120116.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。