2

所以我想我会自学 C++，但我似乎对这门语言没有任何问题，但坦率地说，我很愚蠢。

所以我的想法是这样的。如果我说 a=1、b=2、z=26、aa=27 等，我可以将单词映射到数字，在哈希表中使用布尔值（当然是位屏蔽）并拥有 O(1) 拼写检查器。所以写起来完全没有问题。我的算法是这样的：

int pos;
word_key_t char_key;
word_key_t key = 0;
const char *raw = word.c_str();

cout << "Entering getKey loop with " << raw << endl;
for (pos = 0; raw[pos] != '\0'; pos++) {
    if (raw[pos] >= 'A' && raw[pos] <= 'Z') {
        char_key = raw[pos] - 'A';
    } else if (raw[pos] >= 'a' && raw[pos] <= 'z') {
        char_key = raw[pos] - 'a';
    } else {
        throw new runtime_error("Unrecognised Character");
    }

    key += (char_key + 1) * (pow(CHARS_IN_ALPHABET, pos));
}

cout << "word: " << raw << " ,score: " << key << endl;
return key;

它似乎工作，

a=1 b=2 ab=53 ac=79。

我相信这是正确的。

但是，我在尝试对其进行解码时遇到了问题。这是我最好的尝试，但它不起作用。我相信我需要使用 pow(26,position) 并从字符串的末尾递减，但我只是在努力实现这一点。这是一些可行的独立代码，但会做错事：

#include <iostream>
#include <inttypes.h>
#include <string.h>

typedef uint32_t word_key_t;
const int CHARS_IN_ALPHABET = 26;
const int BUFFER_SIZE = 255; //ignore this for now.

using namespace std;

string reverseKey(const word_key_t key); //broken algo

int main(int argc, char** argv) {
        reverseKey(53); // 53 = ab
        return 0;
}

//disassemble a word_key_t into it's original string. returns lowercase only
string reverseKey(const word_key_t key)
{

  char chr, buffer[BUFFER_SIZE];
  word_key_t keyc = key, isolated, pos = BUFFER_SIZE;

  cout << "key: " << keyc << endl;

  while (keyc != 0) {
      isolated = (keyc - 1) % ((word_key_t)CHARS_IN_ALPHABET + 1);
      cout << "key: " << keyc << ", isolated: " << isolated << endl;
      chr = (char)'a' + isolated - 1;
      cout << "isolated character: " << chr << endl;
      keyc = (keyc - isolated) / CHARS_IN_ALPHABET;
      cout << "new key: " << keyc << endl;
      pos++;
  }

  string s("test");
  return s;

}

如果有人能推动我找到正确的伪代码来解决这个问题，我将不胜感激。我有点发疯了，并失去了解决方案的情节。我只是看不到它。有些东西告诉我 2logX / 2log26，我想我只需要一些更聪明的眼睛。然后我可以回去学习 C++。`在此处输入代码

4

5 回答 5

2

稍后进行一些编辑。我确实误解了键值的生成。我认为密钥字母的生成将是：

while ( key )
   {
   int char_key = key % 26;
   char c = 'a' + (char)( char_key - 1 );
   key /= CHARS_IN_ALPHABET;      
   }

虽然我仍然不认为密钥的原始计算是正确的。我仍然认为关键计算应该是：

key = CHARS_IN_ALPHABET * key + char_key + 1;

以相反的顺序处理raw[]数组以避免以相反的顺序提取它们。

于 2011-12-07T00:37:07.963 回答
1

您实际上有一个以 27 为底的数字（aa = a*26 + b），但避免使用“零”。

输入：encodedWord 使得 "aa" = 27、"ab" = 28 等。
输出：ASCII 字符串

输出字符串：=“”
而codedWord > 0 做
  最后一个字母 = 编码字 % 27;
  编码字 = 编码字 / 27；
  outString := toChar(lastLetter + 64) + outString;
结束时
返回输出字符串；
于 2011-12-07T00:44:20.633 回答
0

您的问题实际上恢复到基数到基数的转换，在您的情况下从基数 10 到基数 26。不同之处在于 a=0、b=1 等等（0=第一个符号）。

另一个说明是您没有还原转换后的字符串 (ba=53)。

这是完整的代码（第一个元素是 0，而不是 1 iea=0）

就像在您的代码中一样，转换后的字符串中的字符不会反转（就像它们应该在正常的基础到基础转换中一样）

#include <stdio.h>
int power(int x, int times){
    int result = 1;
    while (times--) result *= x;
    return result;
}
void convert(int n, char *s){
    int i = 0;
    do {
        s[i++] = (n % 26) + 'a';
    } while ((n /= 26) > 0);
    s[i] = 0;
}
int convertBack(char *s){
    int i = 0;
    int n = 0;
    while (s[i]) {
        n += ( (s[i]-'a') * power(26, i));
        i++;
    }
    return n;
}
void main(){
    char s[100];
    convert(53, s);
    printf("Converted:%s\n",s);
    printf("Convert back=%d", convertBack(s));
}
于 2011-12-07T01:06:04.187 回答
0

我建议不要使用任何“power”函数，尤其是浮点函数。

以下设置 'a' = 0、'z' = 25、'aa' = 26 等，并且仅适用于整数加法、乘法和除法（无浮点）。每个编码的字符只需要一次乘法，每个解码的字符只需要一次除法。

#include <cctype>
#include <iostream>
#include <string>
#include <algorithm>

template <class T>
T encode(const char* s)
{
  T result = 0;
  while (*s != 0)
  {
    result *= 26;
    result += std::tolower(*s) - 'a';
    ++s;
  }
  return result;
}

template <class T>
std::string decode(T x)
{
  std::string s;
  while (x != 0)
  {
    s += x % 26 + 'a';
    x /= 26;
  }
  std::reverse(s.begin(), s.end());
  return s;
}

int main() 
{
  std::cout << decode(encode<unsigned int>("tbce")) << std::endl;
}

Ideone 代码在这里

于 2011-12-07T01:15:03.047 回答
0

您可以使用稍微更多的空间进行权衡，并通过使基数为 2 的幂（在您的情况下为 32）来获得更好的执行时间。

这样您就可以使用移位和逻辑运算来代替乘法、除法和取模。

例如：

void convert(int n, char *s){
    int i = 0;
    do {
        s[i++] = (n && 0x1F) + 'a';
    } while ((n >>= 5) > 0);
    s[i] = 0;
}

int convertBack(char *s){
    int i = 0;
    int n = 0;
    while (s[i]) {
        n += ( (s[i]-'a') >> 5*i;
        i++;
    }
    return n;
}

并且主要应该与 kcsoft 建议的相同。

于 2011-12-07T02:31:11.853 回答