Algorytm: Drukowanie poprawnego indeksu dla sekwencji znaków

Question

Podczas przygotowań do egzaminu natrafiłem na następujący problem:

Wyobraź sobie alfabet słów. Przykład:

a ==> 1 
b ==> 2 
c ==> 3 
... 
z ==> 26 
ab ==> 27 
ac ==> 28 
... 
az ==> 51 
bc ==> 52 
and so on. 

sekwencja znaków musi być w porządku rosnącym wyłącznie (czyli „ab” jest ważny, ale „BA” nie).

Pytanie: Podać dowolne słowo, wydrukować jego indeks, jeśli jest prawidłowy i 0, jeśli nie.

Input Output 
ab 27 
ba 0 
aez 441 

Wszelkie wskazówki dotyczące rozwiązania tego problemu byłyby mile widziane.

Answer 1

Podam kilka wskazówek:

• można znaleźć wzór na liczbę takich słów o określonej długości k?
• Teraz popraw długość k i literę l. Ile słów o długości k zaczyna się od l czy są one?

Podpowiedź: Pascal trójkąt. Jeśli potrzebujesz więcej wskazówek, może pomóc http://en.wikipedia.org/wiki/Combinadic. Jeśli potrzebujesz wdrożenia, można uzyskać inspirację z funkcji zdefiniowanej w rankingu (języka Python) https://github.com/sagemath/sagelib/blob/master/sage/combinat/choose_nk.py

Answer 2

1. upewnij się, że dane wejściowe są tylko literami. Niepowodzenie, jeśli nie.
2. Ustaw pętlę na podstawie długości ciągu minus 1.
3. "Odejmij" wartość pierwszej litery w ciągu od następnej. Jeśli wartość jest równa zero lub dodatnia, oznacza to, że ciąg nie jest rosnący, więc zwróć 0.
4. Powtórz, przesuwając w górę ciąg znaków o jedną literę na raz, sprawdzając kolejną literę.
5. Jeśli dojdziesz do końca, jest to rosnący ciąg znaków.

Nie wspominałem o algorytmie obliczania wartości wskaźnika, tylko przypadku wyjścia. Ale daje on początek we właściwym kierunku, a obliczanie indeksu odbywa się według tych samych zasad.

Więcej informacji:

Początek liczenia w górę na pierwszej literze. Kiedy naciśniesz "z", zresetuj do następnego poprawnego ciągu i kontynuuj zliczanie -> "aa" się nie policzy. Dodaj do następnego, które tutaj jest "ab". Po naciśnięciu "az", spróbuj "ba" - zawieść, dodawaj kolejne litery, aż otrzymasz poprawny ciąg "bc" i zacznij znowu odliczać. To jak licznik, który liczy się w górę.

Dang wolno, ale powinien działać, ponieważ to, co robisz ręcznie, aby uzyskać odpowiedź.

BTW, jest znacznie bardziej eleganckie rozwiązanie zasugerował przez @hivert który byłby prawie natychmiastowy obliczyć ...