算法题每日一练---第16天：好好学习

一、问题描述

汤姆跟爷爷来中国旅游。一天，他帮助中国的小朋友贴标语。他负责贴的标语是分别写在四块红纸上的四个大字：“好、好、学、习”。但是汤姆不认识汉字，他就想胡乱地贴成一行。

请你替小汤姆算一下，他这样乱贴，恰好贴对的概率是多少？

答案是一个分数，请表示为两个整数比值的形式。例如：1/3 或 2/15 等。如果能够约分，请输出约分后的结果。

二、题目要求

考察

数学思想，全排列公式应用
建议用时5~15min

三、问题分析

题目出现了四个汉字，分别为好、好、学、习，不同的汉字有三个，相同的汉字有两个。题目要求我们在所有的排列组合中，找到正确的一种，问题的规模不是很大，深搜(DFS)对于这样一道问题来说明显不适用。

主要用下面两种方法：

1.暴力法

直接用全排列一步解决，输出所有可能的结果，从中判断最正确的情况。

全排列公式：

do{
}while(next_permutation(a,a+10));

全排列公式头文件algorithm，或者使用万能头文件bits/stdc++.h

注意

使用全排列的时候，要保证数组的最小的顺序，否则输出会不完整。

2.直接分析法

正确排列的话一共有四个位置，其中第一个字 好 排列正确的概率为1/2，第二个字 好 排列正确的概率为1/3，第三个字 学 排列正确的概率为1/2，习 因为是最后一个字，概率为1。

四个概率彼此相乘：1/2* 1/3 * 1/2=1/12，因此结果就为1/12。

四、编码实现

#include<iostream>#include<algorithm>//全排列头文件 usingnamespacestd;
intmain()
{
inti,n=4,ans=0;
inta[4]={1,1,2,3};//分别使用数字代表好好学习 do    {
for(i=0;i<4;i++)//输出结果         {
cout<<a[i]<<" ";
        }
cout<<"\n";
ans++;//总排列数++     }while(next_permutation(a,a+n));//全排列列出所有可能的结果 cout<<ans;//输出结果 return0;
}

五、输出结果

输出具体结果为：1/12