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）がありますが、「ゼロ」の使用は避けています。

入力: "aa" = 27、"ab" = 28 などのエンコードされた単語。
出力: ASCII 文字列

outString := ""
コード化されている間 Word > 0 Do
  lastLetter = encodedWord % 27;
  エンコードされた単語 = エンコードされた単語 / 27;
  outString := toChar(lastLetter + 64) + outString;
終末期
outString を返します。
于 2011-12-07T00:44:20.633 に答える
0

ベースを2の累乗（この場合は32）にすることで、わずかに多くのスペースを使用し、実行時間を短縮することでトレードオフを行うことができます。

このようにして、乗算、除算、およびmodの代わりに、シフトと論理演算を使用できます。

例えば：

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 に答える
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

「パワー」関数、特に浮動小数点関数を使用しないことをお勧めします。

以下は、'a' = 0、'z' = 25、'aa' = 26 などを設定し、整数の加算、乗算、および除算 (浮動小数点なし) のみを使用して機能します。エンコードされた文字ごとに必要な乗算は 1 つだけであり、デコードされた文字ごとに必要な除算は 1 つだけです。

#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;
}

イデオンコードはこちら

于 2011-12-07T01:15:03.047 に答える