亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

POJ1496-Word Index

系統(tǒng) 1896 0

轉(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

那么

POJ1496-Word Index

?

? 然后就是關(guān)鍵了,長度為 2 的字符串,根據(jù)開頭字母不同,就有 25 種不同情況,編程去處理是很困難的。這里必須要用數(shù)學(xué)方法去處理。

POJ1496-Word Index


POJ1496-Word Index

?

所以用一個簡單的循環(huán)就能計算出 str 長度少的所有字符串個數(shù) 了,這就是數(shù)學(xué)的威力,把受限的取法轉(zhuǎn)換為不限制的取法

?

?

第三步,就是求長度等于 str ,但值比 str 小的字符串個數(shù)

這個看我程序的注釋更容易懂,所以這里就不再啰嗦了,值得注意的是這步我同樣利用了公式( 1 , 所以如果看到某些地方取字母的時候看上去好像沒有遵守“升序規(guī)則”,本來要限制取字母的地方卻沒有限制,那一定是用公式( 1 )變換了

?

第四步,把前面找到的所有字符串的個數(shù)之和再 +1 ,就是 str 的值

之所以 +1 ,是因為此前的所有操作都只是找 str 之前的字符串,并不包括 str 本身

?

然后到了最后,剩下一個問題就是怎樣得到每一個 的值,這個我發(fā)現(xiàn)很多同學(xué)都是利用打表做的, 利用的就是 組合數(shù) 楊輝三角 的關(guān)系 (建立一個二維數(shù)組 C[n]

--

就能看到他們之間關(guān)系密切??!區(qū)別就是頂點的值,楊輝三角為 1 ,組合數(shù)為 0

其實這個“關(guān)系”是有數(shù)學(xué)公式的

POJ1496-Word Index


?

其實組合數(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 }

POJ1496-Word Index


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦?。。?/p>

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国产成人高清一区二区私人 | 国产精品亚洲综合 | 欧美性生活视频免费 | 特一级黄 | 久艹在线观看视频 | 亚洲图片一区二区 | 久久天天躁狠狠躁夜夜中文字幕 | 欧美不卡精品中文字幕日韩 | 国产精品久久久影院 | 欧美黄色网址 | 午夜 福利 | 亚洲欧美精品一区二区 | 99九九精品国产高清自在线 | 成人免费视频一区二区三区 | 亚洲精品视频免费 | 日本爱爱网 | 欧美一级在线观看 | 午夜精品久久影院蜜桃 | 日日摸夜夜添夜夜添毛片 | 久久精品视频99 | 免费观看男女羞羞的视频网站 | jizz成熟丰满老女人 | 成人观看网站a | 日日夜夜噜噜 | 欧美在线一级毛片观看 | 久久91亚洲精品久久91综合 | 日韩不卡视频在线观看 | 伊人久久综合谁合综合久久 | 日韩在线手机看片免费看 | 美女粉逼 | 欧美精品国产日韩综合在线 | 国产精品嫩草影院99av视频 | 伊人免费网 | 国产99久9在线 | 午夜特级毛片 | 美国毛片一级视频在线aa | 正在播放国产乱子伦视频 | 免费国产成人综合 | 99国产超薄丝袜足j在线播放 | 久久国产成人精品麻豆 | 久久久久久夜精品精品免费 |