斐波那契數(shù)列
- 求斐波那契數(shù)列矩陣乘法的方法
1）斐波那契數(shù)列的線性求解（O(N)）的方式非常好理解;
2）同時利用線性代數(shù)润樱，也可以改寫出另一種表示:
| F(N) , F(N-1) | = | F(2), F(1) | * 某個二階矩陣的N-2次方;
3）求出這個二階矩陣俩滥，進而最快求出這個二階矩陣的N-2次方; - 類似斐波那契數(shù)列的遞歸優(yōu)化
如果某個遞歸迹淌，除了初始項之外屡江，具有如下的形式
F(N) = C1 * F(N) + C2 * F(N-1) + … + Ck * F(N-k) ( C1…Ck 和k都是常數(shù))并且這個遞歸的表達式是嚴(yán)格的沟优、不隨條件轉(zhuǎn)移的巢钓。
那么都存在類似斐波那契數(shù)列的優(yōu)化病苗，時間復(fù)雜度都能優(yōu)化成O(logN)
- 斐波那契數(shù)列可用遞歸，動態(tài)規(guī)劃症汹，求解做到O(logn)硫朦，但是用快速冪可以做到O(logn)。
1.快速冪：
比如求a^75次方背镇，一般方法a連續(xù)相乘75次咬展，這樣就太慢了。我們可以這樣計算瞒斩，冪指數(shù)75的二進制形式是1001011破婆，定義一個變量res = 1,一個t變量 t= a1,從如果此時冪指數(shù)二進制位最右邊是1那么把t和res相乘，如果不是一那么不進行相乘計算胸囱，且此時讓t和t相乘得到第二輪的t,如此往復(fù)當(dāng)冪指數(shù)為0時就得到了a75次方祷舀。
2.斐波拉切數(shù)列的遞推式：|F(n).F(n-1)=|F(2).F(1)||矩陣|^n-2
3.推廣：F(n) = C1F(n) +C2F(n-1) +...+CzF(n-k) C1、C2旺矾、Cz..和k都是常數(shù)蔑鹦，則都有O(logn)的解。
public class Fbo {
// 遞歸
public static int f(int n){
if(n <= 0){
return 0;
}
if(n <= 2){
return 1;
}
return f(n - 1) + f(n - 2);
}
// 動態(tài)規(guī)劃
public static int dp(int n){
if(n <= 0){
return 0;
}
if(n <= 2){
return 1;
}
int one = 1;
int two = 1;
int cur = 0;
for (int i = 2; i < n; i++) {
cur = one + two;
one = two;
two = cur;
}
return cur;
}
// 快速冪方法
// 有線性代數(shù)德 => |Fnfn-1| = |F2F1|*(矩陣)^n-k(k=2)
public static int quickM(int n){
if(n <= 0){
return 0;
}
if(n <= 2){
return 1;
}
int[][] matrix = new int[][]{{1,1},{1,0}};
int[][] ints = matrixPower(matrix, n - 2);
return ints[0][0] + ints[1][0];
}
// 求矩陣的n次冪
public static int[][] matrixPower(int[][] m, int p) {
int[][] res = new int[m.length][m[0].length];
for (int i = 0; i < res.length; i++) {
res[i][i] = 1;
}
// res = 矩陣中的1
int[][] tmp = m;// 矩陣1次方
for (; p != 0; p >>= 1) {
if ((p & 1) != 0) {
res = muliMatrix(res, tmp);
}
tmp = muliMatrix(tmp, tmp);
}
return res;
}
// 兩個矩陣相乘
public static int[][] muliMatrix(int[][] m1, int[][] m2) {
int[][] res = new int[m1.length][m2[0].length];
for (int i = 0; i < m1.length; i++) {
for (int j = 0; j < m2[0].length; j++) {
for (int k = 0; k < m2.length; k++) {
res[i][j] += m1[i][k] * m2[k][j];
}
}
}
return res;
}
public static void main(String[] args) {
System.out.println(f(8));
System.out.println(dp(8));
System.out.println(quickM(8));
}
}
一個人可以一次往上邁1個臺階箕宙，也可以邁2個臺階返回這個人邁上N級臺階的方法數(shù)嚎朽。
一階臺階有一種方法，邁一步柬帕，二階臺階有兩種方法兩次一步哟忍，一次兩步..=> f(1) = 1,f(2) = 2... =>n階臺階f(n) = f(n-1)+f(n-2),就是斐波拉切數(shù)列變形狡门，只是第二項的值不一樣是二。第一年農(nóng)場有1只成熟的母牛A锅很，往后的每年：
1）每一只成熟的母牛都會生一只母牛
2）每一只新出生的母牛都在出生的第三年成熟
3）每一只母牛永遠不會死
返回N年后牛的數(shù)量
遞推式：f(0) = 1,f(1) = 2,f(2) = 3,f(3) = 4,=> f(n) = f(n-1)+ f(n-3),是一個三階的問題矩陣是一個三階矩陣其馏。給定一個數(shù)N，想象只由0和1兩種字符爆安，組成的所有長度為N的字符串如果某個字符串,任何0字符的左邊都有1緊挨著,認(rèn)為這個字符串達標(biāo)
返回有多少達標(biāo)的字符串叛复。
定義一個函數(shù)f(i)，表示在i的前面一定是1返回此時i個數(shù)達標(biāo)的情況扔仓，
情況一如果i位置是0那么i+1職位只可能是1,所以讓i+2位置返回多少種方法f(i-2),情況二如果i位置是1那么讓i+1位置去決策方法數(shù)f(i+1)
所以地推式：f(n) = f(n+1)+f(n+2),又是一個斐波拉切數(shù)列問題褐奥。
蓄水池算法
解決的問題：
假設(shè)有一個源源吐出不同球的機器，只有裝下10個球的袋子翘簇，每一個吐出的球撬码，要么放入袋子，要么永遠扔掉如何做到機器吐出每一個球之后版保，所有吐出的球都等概率被放進袋子里呜笑。
流程：先10個球直接進入袋子里面，然后當(dāng)后面的球繼續(xù)進入袋子的時候彻犁，讓這個球以球的編號10/k（f函數(shù)叫胁，f(k)1-k等概率返回一個數(shù)，返回1-10進袋子）的概率進入袋子中袖裕，并且讓袋子中的一個且等概率隨機的被拋出袋子曹抬。這樣所有球進入袋子的概率都相等。
/**
* 假設(shè)有一個源源吐出不同球的機器急鳄，
* 只有裝下10個球的袋子谤民，每一個吐出的球，要么放入袋子疾宏，要么永遠扔掉
* 如何做到機器吐出每一個球之后张足，所有吐出的球都等概率被放進袋子里
*/
public class Reservoir {
// 袋子
private static int[] bag;
private static int count;
private static int n ;
public Reservoir(int n){
// 用戶需要的n大小的袋子所有進入袋子的概率都是 n/num,如果機器吐出球的數(shù)量num,
this.bag = new int[n];
this.count = 0;
this.n = n;
}
public static void add(int a){
if(count < n){
bag[count] = a;
}else if(rand(count+1) <= n){
// 隨機淘汰一個
bag[rand(n)-1] = a;
}
count ++;
}
// 一個隨機函數(shù)輸入i返回1 ~ i的數(shù)字
private static int rand(int i){
return (int)(Math.random() * i) + 1;
}
}
隨機函數(shù)
- 給定一個隨機源函數(shù)f可以返回17，設(shè)計一個結(jié)構(gòu)可以返回110坎藐。
利用給定隨機源生成一個 等概率返回0,1利用二進制返回需要范圍數(shù)字为牍。設(shè)計g函數(shù)，比如17岩馍，調(diào)用f返回123碉咆，那么代表0，返回456蛀恩，那么代表1疫铜，返回7無效重新隨機，110需要四位二進制双谆，調(diào)用四次g函數(shù)壳咕，得到四位二進制席揽，值的范圍在015,如果生的數(shù)不是110中的數(shù)，那么重新調(diào)用g生成,否則返回值谓厘，那么就可以等概率返回1~10了幌羞。
/**
* 利用1到7隨機函數(shù)，設(shè)計1~10的隨機函數(shù)
*/
public class OneToTenRandom {
public static int random(){
int g;
while (true){
g = g();
if(g == 0 || g >=11){
continue;
}
break;
}
return g;
}
private static int g(){
int res = 0;
int count = 0;
while (count < 4){
int temp = oneToSevenRandom();
if(temp>=1 && temp <=3 ){
res |= 0;
}else if(temp >= 4 && temp <= 6) {
res |= 1;
}else{
continue;
}
count++;
if(count < 4){
res <<= 1;
}
}
return res;
}
//1~7隨機生成函數(shù)
private static int oneToSevenRandom(){
return (int)(Math.random() * 7) + 1;
}
public static void main(String[] args) {
int[] arr = new int[11];
for(int i = 0;i < 1000000;i++){
arr[random()]++;
}
int count = 0;
for(int t : arr){
System.out.println("count:"+count+"=>" +t);
count++;
}
}
}
- 已知函數(shù)f返回0的概率是p,返回1的概率是1-p,設(shè)計一個隨機函數(shù)等概率返回1~10竟稳。
調(diào)用2次函數(shù)f属桦，則返回的可能，可能的結(jié)果是 01 他爸，11 地啰，10 ，00
01 的概率 p(1-p),11的概率(1-p)^2,10的概率p(1-p),00的概率p^2讲逛，
由于01和10的概率是相等的，我們利用這兩可以等概率獲取1和0岭埠，的到01代表1盏混，的到10代表0，那么我們獲取到四位二進制就可以代表一個0~15的數(shù)了惜论，每次只返回滿足條件的數(shù)就可以了许赃。
public class P {
// 等概率返回1 ~ 10
public static int random2(){
int count = 0;
int res = 0;
while (true){
while (count < 4){
int g = g();
res |= g;
if(count < 3){
res <<= 1;
}
count ++;
}
if(res == 0 || res >=11){
res = 0;
count = 0;
continue;
}
break;
}
return res;
}
// g函數(shù)等概率返回1 和 0
private static int g(){
int f;
int f2;
while (true){
f = f();
f2 = f();
if((f == 0 && f2 ==0)
|| (f == 1 && f2 == 1)){
continue;
}
break;
}
return (f == 0 && f2 == 1) ? 1 : 0;
}
// 返回0的概率是p,返回1的概率是1-p,
// 假設(shè)p是0.3
private static int f(){
// 調(diào)用h函數(shù)如果返回1~3那么返回0，如果返回4~10 返回1
int res;
if(h()>=1 && h()<=3){
res = 0;
}else{
res = 1;
}
return res;
}
// 等概率返回1 ~ 10
private static int h(){
return (int)(Math.random() * 10)+1;
}
public static void main(String[] args) {
int[] arr = new int[11];
for(int i = 0;i < 100000;i++){
arr[random2()]++;
}
int count = 0;
for(int t : arr){
System.out.println("count:"+count+"=>" +t);
count++;
}
}
}
