質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.84%

  • Python 3.x

    4862questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • アルゴリズム

    371questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Python べき乗根の計算方法

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 173

yhmr

score 38

 質問

整数のべき乗根を求める際、誤差が含まれないような計算方法はありますでしょうか?
もしくは、誤差が計算結果になるべく影響しないような回避方法はありますでしょうか?

* 追記 *
『少数全てを整数として扱いたい』のではなく、『誤差だけを回避したい』というイメージでしょうか。

>>> 216 ** (1/3)
5.999999999999999 # 6となってほしい…


""" 以下、追記 """

>>> 217 ** (1/3)
6.009245006917366
>>> 215 ** (1/3)
5.990726414895092 # これらの結果は少数として扱いたい…

 背景

AtCoder ABC097のB問題を、Pythonで以下の様に実装しております。
サンプルは通ったものの、一つのテストケースでWAとなりました。

import math

x = int(input())
slv = lambda b, p: math.floor(b ** (1/p)) ** p
print(max([slv(x, p) for p in range(2, 10)]))

原因を調べたところ、入力を「216」や「343」としたとき、b ** (1/p)に(丸め?)誤差が含まれていることがわかりました。

 試したこと

上記コードのmath.floor内の計算を、

1: math.pow(b, 1/p)
2: b ** Fraction(1, p)


などと試してはみました。が、解決はしませんでした。

 所感

WAが起こっている原因の調査のために、他のアルゴリズム(逐一べき乗を計算する)で実装を行ったため課題自体は解決できたものの、このアルゴリズムで何とかできないものなのかと引っかかっています…
ただ、質問内容自体も乱暴な気がしますし、ここまで書いてこのアルゴリズムは諦めるべきかもという気がしてきました…

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+6

『計算誤差を小さくする』ことは可能でも、『計算誤差をなくす』ことは出来ないです。
検算によって整数の計算に持ち込むのが確実かと。

>>> def func(num, n):
...     root = num ** (1/n)
...     return num == round(root) ** n
...
>>> func(216, 3)
True

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/18 14:39

    組み込みでroundがありましたか・・・知らなかった

    キャンセル

  • 2018/05/18 15:11

    ご回答ありがとうございます。hayataka2049さんのご回答と同じく、質問に記載したべき根の計算をすることができました!
    なんとなく想像はついていたものの、やはり『計算誤差をなくす』ことはできないのですね。

    ただし、私の質問の仕方が良くなかったため、ご提示いただいた方法では最終目的のコードに対応することができませんでした…
    最大のべき乗数を求める際に少数の切り捨てを行うため、
     『計算誤差を小さくしたいものの、少数は少数として扱いたい』
    という、非常に乱暴なことを求めてしまっています…

    キャンセル

  • 2018/05/18 15:16

    上記funcの返り値がFalseであるときのrootの値も必要、ということでしょうか?
    プログラムとして美しいかは別として、真偽値と一緒にrootも返しちゃうのもアリかと。

    キャンセル

  • 2018/05/18 15:58

    (私の頭がついていかず)少し混乱してきましたが、こんな感じで意図したことができるようになりました。
    質問があまり適切ではなかったにも関わらず、お答えいただきありがとうございます!

    def func(num, n):
    root = num ** (1/n)
    return round(root) if num == round(root) ** n else root

    slv = lambda b, p: math.floor(func(b, p)) ** p
    print(max([slv(x, p) for p in range(2, 10)]))

    キャンセル

+2

整数がほしいのなら、ceilとfloorを計算して誤差が小さい方を選ぶとかで良いのでは?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/18 14:58

    ご回答ありがとうございます。ご提示いただいた方法で、質問に記載したべき根を求めることができました!

    ただ、これは、完全に私の質問の仕方が悪かったのですが、「背景」にあるアルゴリズムでは四捨五入での対応できないんですよね…
    最大のべき乗数を求めるために、少数の切り捨てを行っているため、すべての場合で四捨五入をしてしまうと、意図した動作ができないのです…

    キャンセル

  • 2018/05/18 15:31

    なるほど。ではceilとfloorを両方返して、xを超えないものだけ残して使うというのはどうでしょう

    キャンセル

  • 2018/05/18 15:41

    できたような気はしますが、保証しませんし、なんかけっきょく汚い感じに・・・
    X = int(input())

    slv = lambda b, p: [math.floor(b**(1/p))**p,
    math.ceil(b**(1/p))**p]

    lst = [x for x in chain.from_iterable([slv(X, p) for p in range(2, 10)])
    if X >= x]

    print(max(lst))

    キャンセル

  • 2018/05/18 15:48

    なかなかこんらんしてきました!
    が、こちらのコードでなんとなく意図した動作を行える気がします。自分なりにもう少しかみ砕いてみます…
    乱暴な要求にも関わらず、お答えいただき本当にありがとうございます!

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.84%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 解決済

    range(1, n+1)とrange(n,1,-1)の違い

    PHO7の水着の問題に苦戦しています 私は以下のコードは両方共結果が同じになると思っているのですが、どうやらpaizaさんの自動採点では後者のコードは弾かれてしまうようです。

  • 解決済

    argvの表示の仕方

    前提・実現したいこと pythonでとあるソースコードを書いています。 シェルから引数を持ってくる際にargvを使用しますが、 以下のように表示されます。 該当のソース

  • 解決済

    pythonのスライスについて

    a = b[:,0] このようなコードがあったとき、どのようなことがおこなわれますか? bはこのコードがなりたつ何かだとすると なにだったら成り立ちますか? すみません、間

  • 解決済

    Pythonのbuttonの表示結果をターミナルではなくフレームに

    from tkinter import * from tkinter import ttk def button_click(): show_selection() d

  • 解決済

    【質問】みんなのPython 第4版 chapter03 タプルの利点(p.134)

    現在 みんなのpython【第4版】を読み、写経をしながら学習をしています。 以下についてご教授ください。 「与えられた地点から最も近い県庁所在地を調べるプログラムを書い

  • 解決済

    pythonのリストに付いての質問

    pythonのリストに付いての質問です。 文字列が1500個入っているリストがあります。先頭から0,1番目をそれぞれ変数x,yに入れていき2番めを抜かして3,4をx,yに追加。5を

  • 解決済

    Python 3.x 辞書のキー値によって変換する場合の高速化

    Pythonにて、辞書(dict({key,value})を使って、list型の全要素をValue値に変換する際の、 高速化が可能かどうかをご教授いただきたいです。 dict1

  • 解決済

    python csvファイル改行削除

    csvファイル ['abc\ndef\nghi','jkl\nmno\npqr','stu\nvwx\nyz'] 改行コードを削除したい。 readerで読み込んだファイルは削除で

同じタグがついた質問を見る

  • Python 3.x

    4862questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • アルゴリズム

    371questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。