原文:
给定两条t2 s 和 t ,其中 s 代表车辆从左向右移动的第一条车道, t 代表车辆从右向左移动的第二条车道。车辆可以是 b(自行车)、 c(汽车),也可以是 t(卡车)。任务是找出两辆卡车相撞的概率。
示例:
输入: s = "tccbcttb ",t = "btccbbtt" 输出: 0.194444 解释: 总碰撞= 7 总事故= 36 因此,概率可按 7/36 = 0.19444 计算。
输入: s = "btt ",t = " btcbt " t3】输出: 0.25000
插图:
s = "tccbcttb", t = "btccbbtt"
possible cases | accidents | collision
-----------------------------------------
tccbcttb | |
btccbbtt | 8 | 1
| |
tccbcttb | |
btccbbtt | 7 | 3
| |
tccbcttb | |
btccbbtt | 6 | 1
| |
tccbcttb | |
btccbbtt | 5 | 0
| |
tccbcttb | |
btccbbtt | 4 | 0
| |
tccbcttb | |
btccbbtt | 3 | 0
| |
tccbcttb | |
btccbbtt | 2 | 1
| |
tccbcttb | |
btccbbtt | 1 | 1
total number of accidents: 8 7 6 5 4 3 2 1=36
total number of collision: 1 3 1 0 0 0 1 1=7
probability: 7/36=0.19444
方法:按照以下步骤解决问题:
- 找出有利结果的总数作为碰撞总数(卡车之间的事故)和可能结果的总数(碰撞总数)作为事故总数。
- 初始化一个变量答案等于 0 来存储碰撞计数。
- 计算字符串 t 中的卡车数量,并将其存储在变量计数中。
- s 和 t 的字符:
- 如果 s[i] 等于‘t’,将答案增加计数。
- 如果 t[i] 等于“t”,则按 1 递减计数。
- 现在,计算可能结果的总数(事故总数)。如果将字符串 a 向右或字符串 b 向左移动一个单位,它就是所有重叠长度的总和。
- 假设弦的长度为 n ,弦 b 为 m 。那么,重叠的总数将是:
- 若 n > m 则为之和,即 m*(m 1)/2 。
- 否则为n (n 1)/2 (m–n) n。
- 求碰撞次数与事故次数之比的概率。
下面是上述方法的实现:
c
// c program for the above approach
#include
using namespace std;
// function to calculate total
// number of accidents
double count_of_accident(string a,
string b)
{
// string size
int n = a.size(), m = b.size();
if (n > m)
return (m * (m 1)) / 2;
else
return (n * (n 1))
/ 2
(m - n) * n;
}
// function to calculate count
// of all possible collision
double count_of_collision(string a,
string b)
{
int n = a.size(), m = b.size();
// stores the count of collisions
int answer = 0;
// total number of truck in lane b
int count_of_truck_in_lane_b = 0;
for (int i = 0; i < m; i )
if (b[i] == 't')
count_of_truck_in_lane_b ;
// count total number of collisions
// while traversing the string a
for (int i = 0; i < n && i < m; i ) {
if (a[i] == 't')
answer
= count_of_truck_in_lane_b;
if (b[i] == 't')
count_of_truck_in_lane_b--;
}
return answer;
}
// function to calculate the
// probability of collisions
double findprobability(string a,
string b)
{
// evaluate total outcome that is
// all the possible accident
double total_outcome
= count_of_accident(a, b);
// evaluate favourable outcome i.e.,
// count of collision of trucks
double favourable_outcome
= count_of_collision(a, b);
// print desired probability
cout << favourable_outcome
/ total_outcome;
}
// driver code
int main()
{
string s = "tccbcttb", t = "btccbbtt";
// function call
findprobability(s, t);
return 0;
}
java 语言(一种计算机语言,尤用于创建网站)
// java program for the above approach
import java.util.*;
class gfg
{
// function to calculate total
// number of accidents
static int count_of_accident(string a,
string b)
{
// string size
int n = a.length(), m = b.length();
if (n > m)
return (m * (m 1)) / 2;
else
return (n * (n 1))
/ 2
(m - n) * n;
}
// function to calculate count
// of all possible collision
static double count_of_collision(string a,
string b)
{
int n = a.length(), m = b.length();
// stores the count of collisions
double answer = 0;
// total number of truck in lane b
int count_of_truck_in_lane_b = 0;
for (int i = 0; i < m; i )
if (b.charat(i) == 't')
count_of_truck_in_lane_b ;
// count total number of collisions
// while traversing the string a
for (int i = 0; i < n && i < m; i )
{
if (a.charat(i) == 't')
answer
= count_of_truck_in_lane_b;
if (b.charat(i) == 't')
count_of_truck_in_lane_b--;
}
return answer;
}
// function to calculate the
// probability of collisions
static void findprobability(string a,
string b)
{
// evaluate total outcome that is
// all the possible accident
int total_outcome
= count_of_accident(a, b);
// evaluate favourable outcome i.e.,
// count of collision of trucks
double favourable_outcome
= count_of_collision(a, b);
// print desired probability
system.out.printf("o",favourable_outcome
/ total_outcome);
}
// driver code
public static void main(string[] args)
{
string s = "tccbcttb", t = "btccbbtt";
// function call
findprobability(s, t);
}
}
// this code is contributed by 29ajaykumar
python 3
# python3 program for the above approach
# function to calculate total
# number of accidents
def count_of_accident(a, b):
n = len(a)
m = len(b)
if (n > m):
return (m * (m 1)) / 2
else:
return ((n * (n 1)) / 2
(m - n) * n)
# function to calculate count
# of all possible collision
def count_of_collision(a, b):
# size of string
n = len(a)
m = len(b)
# stores the count of collisions
answer = 0
# total number of truck in lane b
count_of_truck_in_lane_b = 0
for i in range(0, m):
if (b[i] == 't'):
count_of_truck_in_lane_b = 1
# count total number of collisions
# while traversing the string a
i = 0
while (i < m and i < n):
if (a[i] == 't'):
answer = count_of_truck_in_lane_b
if (b[i] == 't'):
count_of_truck_in_lane_b -= 1
i = 1
return answer
# function to calculate the
# probability of collisions
def findprobability(a, b):
# evaluate total outcome that is
# all the possible accident
total_outcome = count_of_accident(a, b);
# evaluate favourable outcome i.e.,
# count of collision of trucks
favourable_outcome = count_of_collision(a, b);
# print desired probability
print(favourable_outcome / total_outcome)
# driver code
if __name__ == "__main__" :
s = "tccbcttb"
t = "btccbbtt"
# function call
findprobability(s, t)
# this code is contributed by virusbuddah_
c
// c# program for the above approach
using system;
class gfg
{
// function to calculate total
// number of accidents
static int count_of_accident(string a,
string b)
{
// string size
int n = a.length, m = b.length;
if (n > m)
return (m * (m 1)) / 2;
else
return (n * (n 1))
/ 2
(m - n) * n;
}
// function to calculate count
// of all possible collision
static double count_of_collision(string a,
string b)
{
int n = a.length, m = b.length;
// stores the count of collisions
double answer = 0;
// total number of truck in lane b
int count_of_truck_in_lane_b = 0;
for (int i = 0; i < m; i )
if (b[i] == 't')
count_of_truck_in_lane_b ;
// count total number of collisions
// while traversing the string a
for (int i = 0; i < n && i < m; i )
{
if (a[i] == 't')
answer
= count_of_truck_in_lane_b;
if (b[i] == 't')
count_of_truck_in_lane_b--;
}
return answer;
}
// function to calculate the
// probability of collisions
static void findprobability(string a,
string b)
{
// evaluate total outcome that is
// all the possible accident
int total_outcome
= count_of_accident(a, b);
// evaluate favourable outcome i.e.,
// count of collision of trucks
double favourable_outcome
= count_of_collision(a, b);
// print desired probability
console.write("{0:f4}", favourable_outcome
/ total_outcome);
}
// driver code
public static void main(string[] args)
{
string s = "tccbcttb", t = "btccbbtt";
// function call
findprobability(s, t);
}
}
// this code is contributed by sapnasingh4991
java 描述语言
output:
0.194444
时间复杂度:o(n) t5辅助空间:** o(1)
麻将胡了pg电子网站的版权属于:月萌api www.moonapi.com,转载请注明出处