正整数のゲーデル数化？ in C++ DouKaku?

正整数のゲーデル数化？

正の整数 n を引数としてとり， 2^d1 * 3^d2 * 5^d3 ... * pk^dk を返す関数
goedel を定義してください．

ただし，n を10進表現で k 桁の数としたときの各桁の数が数列 [d1,d2,d3,...,dk]
をなすとし，dk が 1 の位，d1 が 10^(k-1) の位です．また，pk は k番目の素数です．

goedel   9  ⇒ 2^9             ⇒  512
goedel  81  ⇒ 2^8 * 3^1       ⇒  768
goedel 230  ⇒ 2^2 * 3^3 * 5^0 ⇒  108

see: ゲーデル数

post comment

Posted feedbacks - C++

とりあえずお題通りに（桁が変わると一意じゃないのを見越してタイトルに？が付いてるのと解釈）。とりあえず解が出せるのは5桁までかな....6桁だと64bitでも溢れる気がする。桁数が少ないので素数は計算せず。

#include <complex>

static unsigned int prime[] = {2, 3, 5, 7, 11};

unsigned int digit(unsigned int n, unsigned int base)
{
    unsigned d = 1;
    for (; n > (base - 1); n /= base) { d++; }
    return d;
}

unsigned long long goedel(unsigned int n)
{
    unsigned long long ans = 1;
    for (unsinged int d = digit(n, 10); d > 0; d--, n /= 10)
        ans *= (unsigned long long)std::pow((double)prime[d - 1], (int)(n % 10));
    return ans;
}

DouKaku?

正整数のゲーデル数化？

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq