```java
package net.zhaoxuyang.common.algorithm.random;
/**
*
* 蒙特卡羅算法
* <pre>
* 設p是一個實數,且 0.5 小于 p 小于 1,
* 如果蒙特卡羅算法對于問題的任一實例得到的正確解的概率不小于p,則稱該算法是正確的。
* </pre>
* @author zhaoxuyang
*/
public class MonteCarlo {
public static void main(String[] args) {
//int[] array = {1, 2, 1};
// System.out.println(majority(array, array.length, 0.99));
// System.out.println(majority(array, array.length, 0.99));
System.out.println(checkPrimeByWilson(5));
System.out.println(checkPrimeByWilson(6));
while(true){
System.out.println(checkPrimeByMoteCarlo(97));
}
}
/**
* 判斷一個數組是否存在主元素 一個含有n個元素的數組,當存在一個元素占比大于n/2時,稱該元素是數組的主元素。
*/
static boolean majority(int[] array, double n, double p) {
int k = (int) Math.ceil(Math.log(n) / Math.log(1 - 0.9));
for (int i = 1; i <= k; i++) {
if (checkMajority(array, n)) {
System.out.println(array[i]);
return true;
}
}
return false;
}
static boolean checkMajority(int[] array, double n) {
int randomIndex = (int) (Math.random() * n);
int item = array[randomIndex];
int k = 0;
for (int i = 0; i < n; i++) {
if (item == array[i]) {
k++;
}
}
return (k > 1.0 * n / 2);
}
/**
* 常規的判斷一個數是否為素數
*
* @param n
* @return
*/
boolean checkPrime(long n) {
int m = (int) Math.floor(Math.sqrt(n));
for (int i = 2; i <= m; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
/**
*
* <pre>
* Wilson定理有很高的理論價值,定義為:對于給定的正整數n,判定n是素數的充要條件是:
* (n-1)! === -1(mod n)
* 例如n = 5,6,7
* (5-1)!=24, 24 mod 5 = -1(mod 5),故5是素數
* (6-1)!=120, 120 mod 6 = 0(mod 6),故6不是素數
* (7-1)!=720, 720 mod 7 = -1(mod 7),故6不是素數
*
* </pre>
* @param n
* @return
*/
static boolean checkPrimeByWilson(long n) {
return fan(n - 1) % n == n - 1;
}
static long fan(long n) {
return n == 0 ? 1 : n * fan(n - 1);
}
static boolean checkPrimeByMoteCarlo(int n){
int m = (int) Math.floor(Math.sqrt(n));
int min = 2;
int max = m - 1;
int i = (int)(Math.random()*(max-min+1)+min);
System.out.println(i);
return n % i != 0;
}
}
```
- 1 設計接口
- 1.1 容器接口Container
- 1.2 背包接口Bag
- 1.3 棧接口Stack
- 1.4 隊列接口Queue
- 1.5 Union-Find算法接口UF
- 2 實現接口
- 2.1 結點類Node
- 2.2 數組迭代器ArrayIterator
- 2.3 鏈表迭代器ListIterator
- 2.4 背包(Bag)的實現
- 2.4.1 能動態調整數組大小的Bag
- 2.4.2 鏈式Bag的實現
- 2.5 棧(Stack)的實現
- 2.5.1 能動態調整數組大小的Stack
- 2.5.2 鏈式Stack的實現
- 2.6 隊列(Queue)的實現
- 2.6.1 能動態調整數組大小的Queue
- 2.6.2 鏈式Queue的實現
- 2.7 Union-Find算法的實現
- 2.7.1 DefaultUF
- 2.7.2 QuickFindUF
- 2.7.3 QuickUnionUF
- 2.7.4 WeightedQuickUnionUF
- 2.8 測試
- 2.8.1 測試Stack
- 2.8.2 測試Union-Find
- 3 排序算法
- 3.1 定義排序工具的類結構
- 3.2 選擇排序
- 3.3 插入排序
- 3.4 希爾排序
- 3.5 歸并排序
- 3.5.1 歸并排序的合并方法
- 3.5.2 自頂向下的歸并排序
- 3.5.3 自底向上的歸并排序
- 3.6 快速排序
- 3.6.1 常規快速排序
- 3.6.2 排序前先洗牌
- 3.6.3 快速排序的改進方法-小數據量轉成插入排序
- 3.6.4 快速排序的改進方法-三向切分
- 3.7 堆排序
- 3.8 最終的排序工具
- 4 搜索
- 4.1 二分搜索(binarySearch)
- 4.2 優先隊列(MaxPriorityQueue)
- 4.3 二叉查找樹(BST)
- 4.4 紅黑二叉查找樹(RedBlackBST)
- 4.5 B-樹(BTree)
- 5 圖
- 5.1 無向圖(Graph)
- 5.2 有向圖(Digraph)
- 6 貪心
- Dijkstra算法-單元最短路徑
- 7 動態規劃
- 7.1 最長公共子序列問題
- 7.2 0-1背包問題
- 7.3 加工順序問題
- 8 搜索法
- 8.1 圖的著色問題
- 8.2 深度優先搜索
- 8.3 回溯法
- 8.3.1 回溯法的算法框架
- 8.3.2 子集樹
- 8.3.3 排列樹
- 8.3.4 滿m叉樹(組合樹)
- 8.4 廣度優先搜索
- 8.5 分支限界法
- 9 隨機化算法
- 9.1 數值隨機化算法
- 9.2 蒙特卡羅算法
- 9.3 拉斯維加斯算法
- 9.4 舍伍德算法
- 10 數論算法
- 10.1 Stein求最大公約數
- 10.2 矩陣求斐波那切數列
- LeetCode刷題筆記