轉載請注明出處：優 YoU ? http://user.qzone.qq.com/289065406/blog/1301474058
大致題意：（與
POJ1850
基本一致）
輸出某個 str 字符串在字典中的位置，由于字典是從 a=1 開始的，因此 str 的位置值就是 在 str 前面所有字符串的個數 +1
規定輸入的字符串必須是升序排列。不降序列是非法字符串
要求用循環輸入，輸入若干組字符串，若輸入非法字符串則輸出
0
，但不結束程序，這是和
POJ1850
最猥瑣的區別，很多同學只注意到規定
str
的長度不同，以為把
str
數組長度改一下直接復制就能
AC
拿下一題了，殊不知老是
WA
卻找不到原因，大概就是這里出問題了
本題 Str 最長為 5 個字符
?
解題思路：
組合數學題，不知道為什么會被歸類到遞推數學，可能是因為楊輝三角和組合數之間的關系。。。
第一步當然首先判斷輸入的 str 是否是升序序列
若符合第一步，則首先計算比 str 長度少的所有字符串個數
假設 str 為 vwxyz ，則其長度為 5
那么
?
?
然后就是關鍵了，長度為
2
的字符串，根據開頭字母不同，就有
25
種不同情況，編程去處理是很困難的。這里必須要用數學方法去處理。
?
所以用一個簡單的循環就能計算出
比
str
長度少的所有字符串個數
了，這就是數學的威力，把受限的取法轉換為不限制的取法
第三步，就是求長度等于
str
，但值比
str
小的字符串個數
這個看我程序的注釋更容易懂，所以這里就不再啰嗦了，值得注意的是這步我同樣利用了公式（
1
）
,
所以如果看到某些地方取字母的時候看上去好像沒有遵守“升序規則”，本來要限制取字母的地方卻沒有限制，那一定是用公式（
1
）變換了
第四步，把前面找到的所有字符串的個數之和再
+1
，就是
str
的值
之所以
+1
，是因為此前的所有操作都只是找
str
之前的字符串，并不包括
str
本身
然后到了最后，剩下一個問題就是怎樣得到每一個
--
就能看到他們之間關系密切啊！區別就是頂點的值，楊輝三角為 1 ，組合數為 0 ）
其實這個“關系”是有數學公式的
?
其實組合數也可以直接用計算方法做 (n 的規模可以至少擴展到 1000) ，不過這里 n 的規模只有 26 ，打表應該是更快的，有興趣學習用計算方法做組合數的同學可以聯系我，這個要用另外的數學方法處理。
我 QQ289065406 ??? O( ∩ _ ∩ )O 哈哈 ~
最終感想：必須要知道關于組合數 nCm 的公式才能很簡單解這題的，特別是公式（ 1 ），會害死一堆人的。。。。。。。初級的數學題就這么難了，感概某些大牛說：水題一道！ Orz
?
?
1
//
Memory Time
2
//
208K 0MS
3
4
#include
<
iostream
>
5
#include
<
string
>
6
using
namespace
std;
7
8
int
c[
27
][
27
]
=
{
0
};
9
10
/*
打表，利用楊輝三角計算每一個組合數nCm
*/
11
12
void
play_table(
void
)
13
{
14
for
(
int
i
=
0
;i
<=
26
;i
++
)
15
for
(
int
j
=
0
;j
<=
i;j
++
)
16
if
(
!
j
||
i
==
j)
17
c[i][j]
=
1
;
18
else
19
c[i][j]
=
c[i
-
1
][j
-
1
]
+
c[i
-
1
][j];
20
c[
0
][
0
]
=
0
;
21
return
;
22
}
23
24
int
main(
int
i,
int
j)
25
{
26
play_table();
27
28
char
str[
6
];
29
while
(cin
>>
str)
30
{
31
int
len
=
strlen(str);
32
33
/*
檢查str是否符合升序排列
*/
34
35
bool
flag
=
false
;
36
for
(i
=
1
;i
<
len;i
++
)
37
if
(str[i
-
1
]
>=
str[i])
38
{
39
cout
<<
0
<<
endl;
40
flag
=
true
;
//
本題要求循環輸入多組str
41
}
//
而且即使str不符合字典要求（如aab,ba等）也不能結束輸入循環
42
//
只有當程序結束時輸入才終止，這是與POJ1850的最隱蔽區別
43
44
if
(
!
flag)
45
{
46
int
sum
=
0
;
//
str的值，初始為0
47
48
/*
計算長度比str小的字符串個數
*/
49
50
for
(i
=
1
;i
<
len;i
++
)
51
sum
+=
c[
26
][i];
//
c[26][i]表示 長度為i的字符串的個數
52
53
/*
計算長度等于len，但值比str小的字符串個數
*/
54
55
for
(i
=
0
;i
<
len;i
++
)
//
i為str的指針，對每一個位置枚舉 允許選擇的字符ch
56
{
57
char
ch
=
(
!
i)
?
'
a
'
:str[i
-
1
]
+
1
;
//
ch = str[i-1]+1 根據升序規則，當前位置的ch至少要比str前一位置的字符大1
58
while
(ch
<=
str[i]
-
1
)
//
ch<=str[i]-1 根據升序規則，當前位置的ch最多只能比 str這個位置實際上的字符 小1
59
{
60
sum
+=
c[
'
z
'
-
ch][len
-
1
-
i];
//
'z'-ch ： 小于等于ch的字符不允許再被選擇，所以當前能夠選擇的字符總數為'z'-ch
61
ch
++
;
//
len-1-i ： ch位置后面（不包括ch）剩下的位數，就是從'z'-ch選擇len-1-i個字符
62
}
63
}
64
65
cout
<<++
sum
<<
endl;
//
此前的操作都是尋找比str小的所有字符串的個數，并不包括str本身，因此這里要+1
66
}
67
}
68
return
0
;
69
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
