数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究不改变元音和辅音的相对位置就能排列单词吗？
假设我们有一个字符串包含 n 个元素（n < 10）。我们必须找到在不改变元音和辅音的相对位置的情况下排列字符串的方法数。
方法很简单。我们必须数出给定字符串中元音和辅音的数量，然后我们必须找到我们仅能用元音排列的方法数，随后找到仅用辅音排列的方法数，最后将这两个结果相乘以取得总的方法数。
算法
arrangeWayCount(str)
Begin define an array ‘freq’ to store frequency. count and place frequency of each characters in freq array. such that freq[‘0’] will hold frequency of letter ‘a’, freq[1] will hold frequency of ‘b’ and so on. v := number of vowels, and c := number of consonants in str vArrange := factorial of v for each vowel v in [a, e, i, o, u], do vArrange := vArrange / factorial of the frequency of v done cArrange := factorial of c for each consonant con, do cArrange := cArrange / factorial of the frequency of con done return vArrange * cArrange End
示例
#include <iostream>
using namespace std;
long long factorial(int n){
if(n == 0 || n == 1)
return 1;
return n*factorial(n-1);
}
long long arrangeWayCount(string str){
long long freq[27] = {0}; //fill frequency array to 0
int v = 0, c = 0;
for (int i = 0; i < str.length(); i++) {
freq[str[i] - 'a']++;
if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u') {
v++;
}else
c++;
}
long long arrangeVowel;
arrangeVowel = factorial(v);
arrangeVowel /= factorial(freq[0]); // vowel a
arrangeVowel /= factorial(freq[4]); // vowel e
arrangeVowel /= factorial(freq[8]); // vowel i
arrangeVowel /= factorial(freq[14]); // vowel o
arrangeVowel /= factorial(freq[20]); // vowel u
long long arrangeConsonant;
arrangeConsonant = factorial(c);
for (int i = 0; i < 26; i++) {
if (i != 0 && i != 4 && i != 8 && i != 14 && i != 20)
arrangeConsonant /= factorial(freq[i]); //frequency of all characters except vowels
}
long long total = arrangeVowel * arrangeConsonant;
return total;
}
main() {
string str = "computer";
long long ans = arrangeWayCount(str);
cout << "Possible ways to arrange: " << ans << endl;
}输出
Possible ways to arrange: 720
更新于： 2020 年 7 月 2 日
106 次浏览
广告