Code POJ - 1850 （組合數學）

Code

  POJ - 1850 

Transmitting and memorizing information is a task that requires different coding systems for the best use of the available space. A well known system is that one where a number is associated to a character sequence. It is considered that the words are made only of small characters of the English alphabet a,b,c, ..., z (26 characters). From all these words we consider only those whose letters are in lexigraphical order (each character is smaller than the next character). 

The coding system works like this: 

• The words are arranged in the increasing order of their length. 

• The words with the same length are arranged in lexicographical order (the order from the dictionary). 

• We codify these words by their numbering, starting with a, as follows: 

a - 1 

b - 2 

... 

z - 26 

ab - 27 

... 

az - 51 

bc - 52 

... 

vwxyz - 83681 

... 

Specify for a given word if it can be codified according to this coding system. For the affirmative case specify its code. 

Input

The only line contains a word. There are some constraints: 

• The word is maximum 10 letters length 

• The English alphabet has 26 characters. 

Output

The output will contain the code of the given word, or 0 if the word can not be codified.

Sample Input

bf      

Sample Output

55      

思路：主要想清楚，隻要選出一定的字母，那麼他們的順序就一定确定下來了，接下來就是找排列數的問題了，具體解釋看代碼      

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int c[27][27] = {0};//儲存組合數
//打表，利用楊輝三角計算每一個組合數
void play_table(){
    int i,j;
    for(i = 0; i <= 26; i++){
        for(j = 0; j <= i; j++){
            if(j == 0 || j == i)
                c[i][j] = 1;
            else
                c[i][j] = c[i-1][j-1] + c[i-1][j];
        }
    }
    c[0][0] = 0;
    return ;
}

int main(){
    play_table();//打表
    int i,j;
    char str[13];
    scanf("%s",str);
    int len = strlen(str);//字元串長度
    for(i = 1; i < len; i++){//檢查字元串是否符合要求
        if(str[i-1] >= str[i]){
            printf("0\n");
            return 0;
        }
    }
    //先求出，除掉最後一位字母的全部升序排列種類，因為除去最後一位字母，前面任意長度的種類都是在這個長度下的全部種類數
    //因為隻有種類滿了，才會有下一位字母嘛

    int sum = 0;
    for(i = 1; i < len; i++){
        sum += c[26][i];   //這句話做何了解：因為要求是升序的，是以一旦為選出了幾個字母，那麼這幾個字母的順序就确定了，所有
                           //我們要做的僅僅隻是在26個字母中選出我需要的字母個數，即可是以直接c[26][i]
    }
    //下面要進行最後對總長度序列的種類計算，因為總長度序列的種類數一般不會是這個長度下總的全部種類數，是以要從頭一個一個計算
    //那麼思路是什麼呢？
    //先從第一個字母看假設是序列是ebcdf，第一個是e，那麼肯定要計算比e小的字母為開頭的排列種類數，那麼比e小的話有a，b，c，d
    //那麼是不是就可以分别讓這四個字母開頭（這個字母就确定下來了），然後算它之後剩下的那一串字母的排列數，那剩下的這串的排列數怎麼算？
    //首先增序，所有我們可以選的字母肯定要大于已經确定的這個開頭的字母了對吧，那麼為們可以選擇的字母數就是26-‘開頭字母’，選多少個呢，
    //那肯定是選剩下字元串的長度個啦，因為題目要求遞增，是以一旦你選出來了，那麼順序一定是确定了，不需要擔心我選出來的不是遞增的

    for(i = 0; i < len; i++){
        char ch;
        if(i == 0)
            ch = 'a';   //如果是第一個，他的前面沒有字母那麼就從a開始看好了
        else
            ch = str[i-1]+1;          //否則，從那裡開始看呢？肯定是目前位置的前一個字元的下一個開始看了，因為至少要比前一個大1嘛，這句話可能不好了解，舉個栗子
                                      //a e k m z 這個字元串，假設目前為看到k這個字母，前一個是e，k這個位置還有誰可以開頭呢，首先肯定大于e
                                      //所有要從‘e’+1為開頭算起，也就是f，是以才有了str[i-1]+1，懂了吧
        while(ch <= str[i]-1){        //還是剛才的栗子，枚舉開頭是不是肯定要枚舉到比k小的那個字母也就是j，你可能問為什麼不能把k算上，因為以k為開頭的
                                      //排列數不一定是所有的排列數可能排到中間字元串就停了，而他之前的一定是所有的可以用組合數直接相加，是以以k開頭的要放到下一輪中判斷
            sum += c['z'-ch][len-i-1]; //這裡的道理前面已經解釋了,注意這裡要寫成z-ch，字元之間運算，否則結果會錯誤
            ch++;
        }
    }
    printf("%d\n",sum+1);             //正如之前說的，每次找到都是他之前的種類數，是以最後加上他本身
    return 0;
}