The Archeologist’s Dilemma

PC/UVa IDs: 110503/701

分析:5.4节《进制及其转换》提到:把一个a进制整数x转化成b进制整数y的“自左向右”方法是:首先求出y的最高位dl
(dl + 1) * b ^ k > x >= dl * b ^ k
在本题中令x = 2 ^ e,已知十进制y的高n位,则有:
(dl + 1) * 10 ^ k > 2 ^ e > dl * 10 ^ k
其中
k + 1 > 2n
因为要满足“已知的位数n严格少于丢失的位数”。我们可以从k = 2n开始尝试求以上不等式的整数解e,但e仍需满足:
(d(l – 1) + 1) * 10 ^ (k – 1) > (2 ^ e – dl * 10 ^ k) >= d(l – 1) * 10 ^ (k – 1)
及d(l – 2)…直到d(1)的一系列不等式。所有n位都满足的整数e即正解。但还有一个问题:什么时候不存在解?笔者无法证明解始终存在,有线索的读者或可给出。
另外,还有一个比较简单的实现方法:根据公式
N * 10 ^ k < 2 ^ e < (N + 1) * 10 ^ k
其中N为已知的10进制数(即y的高n位),可以实现比较简单的验算,例如这样;但根据UVa的测试结果,笔者的实现大概比后者快40%左右。

#include <iostream>
#include <vector>
#include <cmath>

#define MAX_SIZE 10

long double LOG2 = log(2);
long double LOG2_10 = log(10) / LOG2;

using namespace std;

inline vector<char> to_vec(unsigned int n) {
  vector<char> v;
  v.reserve(MAX_SIZE);
  while (n) {
    v.push_back(n % 10);
    n /= 10;
  }
  return v;
}

unsigned int power_of_2(unsigned int n) {
  unsigned int e = 0;
  vector<char> v = to_vec(n);
  int dl = v.back();    //The highest digit.
  int k = 2 * v.size(); //dl * 10 ^ k
  long double log2_dl = log(dl) / LOG2;
  long double log2_dl_plus = log(dl + 1) / LOG2;
  long double k_log2_10 = k * LOG2_10;
  while (true) {
    //(dl + 1) * 10 ^ k > 2 ^ e >= dl * 10 ^ k
    e = ceil(log2_dl + k_log2_10);
    if (e < log2_dl_plus + k_log2_10) {
      //The next digit, dm, if it exists, must satisfy
      //(dm + 1) * 10 ^ (k - 1) > (2 ^ e - (dl * 10 ^ k)) >= dm * 10 ^ (k - 1)
      //And the next next digit repeats this pattern.
      unsigned int s = dl;
      long double m_log2_10 = k_log2_10;
      int i = v.size() - 2;
      for (; i >= 0; i--) {
        s *= 10;
        s += v[i];
        m_log2_10 -= LOG2_10;
        if (e < log(s) / LOG2 + m_log2_10 || e >= log(s + 1) / LOG2 + m_log2_10)
          break;
      }
      if (i < 0)
        break;
    }
    k_log2_10 += LOG2_10;
  }
  return e;
}

int main() {
  unsigned int n;
  while (cin >> n) {
    cout << power_of_2(n) << endl;
  }
  return 0;
}

《The Archeologist’s Dilemma》有1个想法

  1. Pingback: 目录 | 狂童

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>