0

私は番号Aを持っています（数字0、1、2、3から構築）。最小のxとyを見つけたいのですが、x ^ yiを実行すると、Aよりも小さい最大の数が得られます。

x ^ y <= x^yは最大です

さらに、xとyは10進数であってはならず、「整数」のみである必要があります。

例えば：

A = 7 => x^y = 2^2
A = 28 => x^y = 3^3
A = 33 => x^y = 2^5

等

編集： コメントでizomorphiusが示唆しているように、x=Aおよびy=1の解は常にありますが、それは望ましい結果ではありません。xとyをできるだけ近い数にしたい。

4

2 に答える 2

2

素朴な解決策は次のようになります。

a^yある定数に対して行うことによるAに「最も近いが高くない」数aは次のとおりです。

afloor(log_a(A))[ここでlog_a(A)、を底とする対数は、ほとんどのプログラミング言語と同様に計算できます]aAlog(A)/log(a)

a範囲内のすべてのsを繰り返すことにより[2,A)、この数を見つけることができます。

このソリューションはO(A * f(A))、f(A)パウ/ログの複雑さです

PS指数（）を1より大きくしたい場合はy、範囲内で単純に反復することができます[2,sqrt(A)]-時間計算量を-に減らし、O(sqrt(A) * f(A))指数が1より大きい数値のみを取得します。

于 2012-11-14T13:10:05.437 に答える
1

あなたが何を求めているのかは明確ではありませんが、私は推測しようとします。

z^z = aまず、実数の方程式を解きzます。それぞれ、切り捨てuと切り上げを行いますv。z3つの候補の中(u,u)から(v,u)、(u,v)を超えない最大のものを選択しますa。

例：ケースを検討しa = 2000ます。z^z = 2000数値解法（下記参照）で解き、近似解を得z = 4.8278228255818725ます。u = 4を取得するために切り上げv = 5ます。これで、、、の3つの候補ができまし4^4 = 256た。それらはすべて、よりも小さいので、最大の答えを与えるもの、つまり、を採用します。4^5 = 10235^4 = 6252000x = 4y = 5

これがPythonコードです。関数solve_approxはあなたが望むことをします。に適していa >= 3ます。私はあなたが事件a = 1にそしてa = 2あなた自身で対処できると確信しています。

import math

def solve(a):
    """"Solve the equation x^x = a using Newton's method"""
    x = math.log(a) / math.log(math.log(a)) # Initial estimate
    while abs (x ** x - a) > 0.1:
        x = x - (x ** x - a) / (x ** x * (1 + math.log(x)))
    return x

def solve_approx(a):
    """"Find two integer numbers x and y such that x^y is smaller than
    a but as close to it as possible, and try to make x and y as equal
    as possible."""
    # First we solve exactly to find z such that z^z = a
    z = solve(a)
    # We round z up and down
    u = math.floor(z)
    v = math.ceil(z)
    # We now have three possible candidates to choose from:
    # u ** zdwon, v ** u, u ** v
    candidates = [(u, u), (v, u), (u, v)]
    # We filter out those that are too big:
    candidates = [(x,y) for (x,y) in candidates if x ** y <= a]
    # And we select the one that gives the largest result
    candidates.sort(key=(lambda key: key[0] ** key[1]))
    return candidates[-1]

ここに小さなデモがあります：

 >>> solve_approx(5)
 solve_approx(5)
 (2, 2)
 >>> solve_approx(100)
 solve_approx(100)
 (3, 4)
 >>> solve_approx(200)
 solve_approx(200)
 (3, 4)
 >>> solve_approx(1000)
 solve_approx(1000)
 (5, 4)
 >>> solve_approx(1000000)
 solve_approx(1000000)
 (7, 7)
于 2012-11-14T13:56:03.040 に答える