原文:

给定两条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 中的卡车数量,并将其存储在变量计数中。
  • st 的字符:
    • 如果 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)