wish_me's blog

By wish_me, history, 7 years ago, In English

Given a number n and a pattern that follows like:

(1 to 26): a,b,c,….z

(27 to 52): aa,ab,ac,…az

(52 to 78): ba,bb,bc,…bz

. . . za,zb,zc,…zz

aaa,aab,aac,…aaz

aba,abb,abc,… . . . find the nth pattern

  • Vote: I like it
  • -12
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it
#include <bits/stdc++.h>

using namespace std;

int main(){
    string res;
    string a="abcdefghijklmnopqrstuvwxyz";
    int n, tmp=1;
    cin >> n;
    int div[9];
    for(int i=0; i<=7; i++){
        div[i]=tmp;
        tmp*=26;
    }
    for(int i=7; i>=0; i--){
        if(n/div[i]) res=res+a[n/div[i]-1];
        n=n%div[i];
    }
    cout << res;
}
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually I think this is what has been used in EXCEL...

One can find that the first 26 columns in EXCEL are denoted as A,B,...,Z while the next 26 ones are written as AA,AB,AC,....,AZ, and so on.

We can build a 26-ary tree to obtain an intuitive understanding of this problem. The root node is NULL, and it has 26 child nodes, denoted as A,B,...,Z. Next, node A has 26 child nodes A,B,....,Z, and node B has 26 child nodes A,B,...,Z, and node C has 26 child nodes A,B,...,Z, and so on. In a word, each node in the tree has exactly 26 child nodes, A,B,...,Z.

If we start from the root node and walk along the branches to some other node, all the nodes that have been visited just form the pattern A,B,...,Z,AA,AB,...,AZ,...

Moreover, if we assign index 0 to the root node, and increase the index from top to bottom and left to right, i.e., the child nodes of the root node are counted as 1,2,...,26, and so on, to calculate the n-th pattern is just to find out the route from root node to the node with index n.

For some node with index i, its child nodes have indices 26*i+1, 26*i+2,...,26*i+26. Thus, given node with index n, we can adopt this relationship to find out the route up to the root node, and output the letters that have been visited.

Similarly, given any pattern, like "AAC", we can also calculate its index.