轉(zhuǎn)載請注明出處:優(yōu) YoU ? http://user.qzone.qq.com/289065406/blog/1301474058
大致題意:(與
POJ1850
基本一致)
輸出某個 str 字符串在字典中的位置,由于字典是從 a=1 開始的,因此 str 的位置值就是 在 str 前面所有字符串的個數(shù) +1
規(guī)定輸入的字符串必須是升序排列。不降序列是非法字符串
要求用循環(huán)輸入,輸入若干組字符串,若輸入非法字符串則輸出
0
,但不結(jié)束程序,這是和
POJ1850
最猥瑣的區(qū)別,很多同學(xué)只注意到規(guī)定
str
的長度不同,以為把
str
數(shù)組長度改一下直接復(fù)制就能
AC
拿下一題了,殊不知老是
WA
卻找不到原因,大概就是這里出問題了
本題 Str 最長為 5 個字符
?
解題思路:
組合數(shù)學(xué)題,不知道為什么會被歸類到遞推數(shù)學(xué),可能是因為楊輝三角和組合數(shù)之間的關(guān)系。。。
第一步當(dāng)然首先判斷輸入的 str 是否是升序序列
若符合第一步,則首先計算比 str 長度少的所有字符串個數(shù)
假設(shè) str 為 vwxyz ,則其長度為 5
那么
?
?
然后就是關(guān)鍵了,長度為
2
的字符串,根據(jù)開頭字母不同,就有
25
種不同情況,編程去處理是很困難的。這里必須要用數(shù)學(xué)方法去處理。
?
所以用一個簡單的循環(huán)就能計算出
比
str
長度少的所有字符串個數(shù)
了,這就是數(shù)學(xué)的威力,把受限的取法轉(zhuǎn)換為不限制的取法
第三步,就是求長度等于
str
,但值比
str
小的字符串個數(shù)
這個看我程序的注釋更容易懂,所以這里就不再啰嗦了,值得注意的是這步我同樣利用了公式(
1
)
,
所以如果看到某些地方取字母的時候看上去好像沒有遵守“升序規(guī)則”,本來要限制取字母的地方卻沒有限制,那一定是用公式(
1
)變換了
第四步,把前面找到的所有字符串的個數(shù)之和再
+1
,就是
str
的值
之所以
+1
,是因為此前的所有操作都只是找
str
之前的字符串,并不包括
str
本身
然后到了最后,剩下一個問題就是怎樣得到每一個
--
就能看到他們之間關(guān)系密切??!區(qū)別就是頂點的值,楊輝三角為 1 ,組合數(shù)為 0 )
其實這個“關(guān)系”是有數(shù)學(xué)公式的
?
其實組合數(shù)也可以直接用計算方法做 (n 的規(guī)模可以至少擴展到 1000) ,不過這里 n 的規(guī)模只有 26 ,打表應(yīng)該是更快的,有興趣學(xué)習(xí)用計算方法做組合數(shù)的同學(xué)可以聯(lián)系我,這個要用另外的數(shù)學(xué)方法處理。
我 QQ289065406 ??? O( ∩ _ ∩ )O 哈哈 ~
最終感想:必須要知道關(guān)于組合數(shù) nCm 的公式才能很簡單解這題的,特別是公式( 1 ),會害死一堆人的。。。。。。。初級的數(shù)學(xué)題就這么難了,感概某些大牛說:水題一道! 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 /* 打表,利用楊輝三角計算每一個組合數(shù)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 ; // 本題要求循環(huán)輸入多組str
41 } // 而且即使str不符合字典要求(如aab,ba等)也不能結(jié)束輸入循環(huán)
42 // 只有當(dāng)程序結(jié)束時輸入才終止,這是與POJ1850的最隱蔽區(qū)別
43
44 if ( ! flag)
45 {
46 int sum = 0 ; // str的值,初始為0
47
48 /* 計算長度比str小的字符串個數(shù) */
49
50 for (i = 1 ;i < len;i ++ )
51 sum += c[ 26 ][i]; // c[26][i]表示 長度為i的字符串的個數(shù)
52
53 /* 計算長度等于len,但值比str小的字符串個數(shù) */
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 根據(jù)升序規(guī)則,當(dāng)前位置的ch至少要比str前一位置的字符大1
58 while (ch <= str[i] - 1 ) // ch<=str[i]-1 根據(jù)升序規(guī)則,當(dāng)前位置的ch最多只能比 str這個位置實際上的字符 小1
59 {
60 sum += c[ ' z ' - ch][len - 1 - i]; // 'z'-ch : 小于等于ch的字符不允許再被選擇,所以當(dāng)前能夠選擇的字符總數(shù)為'z'-ch
61 ch ++ ; // len-1-i : ch位置后面(不包括ch)剩下的位數(shù),就是從'z'-ch選擇len-1-i個字符
62 }
63 }
64
65 cout <<++ sum << endl; // 此前的操作都是尋找比str小的所有字符串的個數(shù),并不包括str本身,因此這里要+1
66 }
67 }
68 return 0 ;
69 }
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
