2023-09-23：用go語言，假設(shè)每一次獲得隨機(jī)數(shù)的時(shí)候，這個(gè)數(shù)字大于100的概率是P。 嘗
2023-09-23：用go語言，假設(shè)每一次獲得隨機(jī)數(shù)的時(shí)候，這個(gè)數(shù)字大于100的概率是P。
嘗試N次，其中大于100的次數(shù)在A次~B次之間的概率是多少?
0 < P < 1, P是double類型，
1 <= A <= B <= N <= 100。
來自左程云。
答案2023-09-23：
首先，我們可以使用動(dòng)態(tài)規(guī)劃來解決這個(gè)問題。我們可以定義一個(gè)二維數(shù)組dp，其中dp[i][j]表示在i次嘗試中，獲得j次大于100的隨機(jī)數(shù)的概率。
然后，我們可以使用遞歸的方式計(jì)算dp[i][j]。具體地說，我們可以將每一次嘗試分為兩種情況：獲得大于100的隨機(jī)數(shù)和獲得小于等于100的隨機(jī)數(shù)。如果我們獲得大于100的隨機(jī)數(shù)，則剩余的i-1次嘗試中，我們需要獲得j-1次大于100的隨機(jī)數(shù)；如果我們獲得小于等于100的隨機(jī)數(shù)，則剩余的i-1次嘗試中，我們還需要獲得j次大于100的隨機(jī)數(shù)。我們可以使用更大的P表示獲得大于100的隨機(jī)數(shù)的概率，用1-P表示獲得小于等于100的隨機(jī)數(shù)的概率。
遞歸的邊界條件是如果i為0且j為0，則表示已經(jīng)沒有剩余的嘗試次數(shù)，并且已經(jīng)獲得了所需的j次大于100的隨機(jī)數(shù)，所以概率為1；如果i為0且j不為0，則表示已經(jīng)沒有剩余的嘗試次數(shù)，但是還沒有滿足所需的j次大于100的隨機(jī)數(shù)，所以概率為0。
為了避免重復(fù)計(jì)算，我們可以使用一個(gè)二維數(shù)組dp來保存計(jì)算過的結(jié)果。在每次計(jì)算前，先檢查dp[i][j]是否已經(jīng)計(jì)算過，如果是，則直接返回結(jié)果。
最后，在主函數(shù)中，我們可以調(diào)用probability函數(shù)來計(jì)算概率，并打印結(jié)果。
總的時(shí)間復(fù)雜度和額外空間復(fù)雜度分別為O(N^2)，因?yàn)樾枰?jì)算dp數(shù)組的所有元素。
go完整代碼如下：
package?main
import?"fmt"
func?probability(P?float64,?N?int,?A?int,?B?int)?float64?{
????dp?:=?make([][]float64,?N+1)
????for?i?:=?0;?i?<=?N;?i++?{
????????dp[i]?=?make([]float64,?N+1)
????????for?j?:=?0;?j?<=?N;?j++?{
????????????dp[i][j]?=?-1
????????}
????}
????ans?:=?0.0
????for?j?:=?A;?j?<=?B;?j++?{
????????ans?+=?process(P,?1-P,?N,?j,?dp)
????}
????return?ans
}
func?process(more,?less?float64,?i,?j?int,?dp?[][]float64)?float64?{
????if?i?<?0?||?j?<?0?||?i?<?j?{
????????return?0
????}
????if?i?==?0?&&?j?==?0?{
????????return?1
????}
????if?dp[i][j]?!=?-1?{
????????return?dp[i][j]
????}
????ans?:=?more*process(more,?less,?i-1,?j-1,?dp)?+?less*process(more,?less,?i-1,?j,?dp)
????dp[i][j]?=?ans
????return?ans
}
func?main()?{
????P?:=?0.6
????N?:=?100
????A?:=?30
????B?:=?50
????fmt.Println(probability(P,?N,?A,?B))
}
rust完整代碼如下：
fn?probability(p:?f64,?n:?i32,?a:?i32,?b:?i32)?->?f64?{
????let?mut?dp:?Vec<Vec<f64>>?=?vec![vec![-1.0;?(n?+?1)?as?usize];?(n?+?1)?as?usize];
????let?mut?ans?=?0.0;
????for?j?in?a..=b?{
????????ans?+=?process(p,?1.0?-?p,?n,?j,?&mut?dp);
????}
????ans
}
fn?process(more:?f64,?less:?f64,?i:?i32,?j:?i32,?dp:?&mut?Vec<Vec<f64>>)?->?f64?{
????if?i?<?0?||?j?<?0?||?i?<?j?{
????????return?0.0;
????}
????if?i?==?0?&&?j?==?0?{
????????return?1.0;
????}
????if?dp[i?as?usize][j?as?usize]?!=?-1.0?{
????????return?dp[i?as?usize][j?as?usize];
????}
????let?ans?=?more?*?process(more,?less,?i?-?1,?j?-?1,?dp)?+?less?*?process(more,?less,?i?-?1,?j,?dp);
????dp[i?as?usize][j?as?usize]?=?ans;
????ans
}
fn?main()?{
????let?p?=?0.6;
????let?n?=?100;
????let?a?=?30;
????let?b?=?50;
????println!("{}",?probability(p,?n,?a,?b));
}
c++完整代碼如下：
double?process(double?more,?double?less,?int?i,?int?j,?std::vector<std::vector<double>>&?dp);
double?probability(double?P,?int?N,?int?A,?int?B)?{
????std::vector<std::vector<double>>?dp(N?+?1,?std::vector<double>(N?+?1,?-1));
????double?ans?=?0;
????for?(int?j?=?A;?j?<=?B;?j++)?{
????????ans?+=?process(P,?1?-?P,?N,?j,?dp);
????}
????return?ans;
}
double?process(double?more,?double?less,?int?i,?int?j,?std::vector<std::vector<double>>&?dp)?{
????if?(i?<?0?||?j?<?0?||?i?<?j)?{
????????return?0;
????}
????if?(i?==?0?&&?j?==?0)?{
????????return?1;
????}
????if?(dp[i][j]?!=?-1)?{
????????return?dp[i][j];
????}
????double?ans?=?more?*?process(more,?less,?i?-?1,?j?-?1,?dp)?+?less?*?process(more,?less,?i?-?1,?j,?dp);
????dp[i][j]?=?ans;
????return?ans;
}
int?main()?{
????double?P?=?0.6;
????int?N?=?100;
????int?A?=?30;
????int?B?=?50;
????std::cout?<<?probability(P,?N,?A,?B)?<<?std::endl;
????return?0;
}
c完整代碼如下：
double?probability(double?P,?int?N,?int?A,?int?B);
double?process(double?more,?double?less,?int?i,?int?j,?double**?dp);
double?probability(double?P,?int?N,?int?A,?int?B)?{
????double**?dp?=?(double**)malloc((N?+?1)?*?sizeof(double*));
????for?(int?i?=?0;?i?<=?N;?i++)?{
????????dp[i]?=?(double*)malloc((N?+?1)?*?sizeof(double));
????}
????for?(int?i?=?0;?i?<=?N;?i++)?{
????????for?(int?j?=?0;?j?<=?N;?j++)?{
????????????dp[i][j]?=?-1;
????????}
????}
????double?ans?=?0;
????for?(int?j?=?A;?j?<=?B;?j++)?{
????????ans?+=?process(P,?1?-?P,?N,?j,?dp);
????}
????for?(int?i?=?0;?i?<=?N;?i++)?{
????????free(dp[i]);
????}
????free(dp);
????return?ans;
}
double?process(double?more,?double?less,?int?i,?int?j,?double**?dp)?{
????if?(i?<?0?||?j?<?0?||?i?<?j)?{
????????return?0;
????}
????if?(i?==?0?&&?j?==?0)?{
????????return?1;
????}
????if?(dp[i][j]?!=?-1)?{
????????return?dp[i][j];
????}
????double?ans?=?more?*?process(more,?less,?i?-?1,?j?-?1,?dp)?+?less?*?process(more,?less,?i?-?1,?j,?dp);
????dp[i][j]?=?ans;
????return?ans;
}
int?main()?{
????double?P?=?0.6;
????int?N?=?100;
????int?A?=?30;
????int?B?=?50;
????printf("%f\n",?probability(P,?N,?A,?B));
????return?0;
}
