問題タブ [rational-numbers]

私はかつて面接の質問として以下を受け取りました：

私は正の整数nを考えています。O（lg n）クエリでそれを推測できるアルゴリズムを考え出します。それぞれの質問はあなたが選んだ数であり、私は「低い」、「高い」、または「正しい」のいずれかに答えます。

この問題は、修正された二分探索によって解決できます。この探索では、nを超えるものが見つかるまで2の累乗をリストし、その範囲で標準の二分探索を実行します。これについて私がとてもクールだと思うのは、ブルートフォースだけでなく、無限のスペースで特定の数をすばやく検索できることです。

しかし、私が持っている質問は、この問題のわずかな修正です。正の整数を選択する代わりに、0から1までの任意の有理数を選択するとします。私の質問は、私が選んだ有理数を最も効率的に決定するためにどのアルゴリズムを使用できるかということです。

現在、私が持っている最善の解決策は、すべての有理数の二分探索木であるスターン・ブロコット木を暗黙的に歩くことによって、最大でO（q）時間でp/qを見つけることができます。ただし、整数の場合に取得したランタイムに近いランタイムを取得したいと考えていました。おそらく、O（lg（p + q））やO（lg pq）のようなものです。この種のランタイムを取得する方法を知っている人はいますか？

私は当初、区間[0、1]の標準的な二分探索を使用することを検討しましたが、これでは、ほとんどすべての有理数が欠落している、繰り返されない2分表現の有理数しか見つかりません。有理数を列挙する他の方法を使用することも考えましたが、比較が大きい/等しい/小さいだけでは、この空間を検索する方法が見つからないようです。

Verilog コードで有理数を使用する必要があります。リソースを探しましたが、この問題について何も見つかりませんでした。Verilog で有理数を定義するにはどうすればよいですか。

聞いたことがありません。ほとんどの言語は、intの除算が丸であるか、浮動小数点数であるように見えます。スキームに問題があり、他の言語では使用されていないことがわかりましたか？

プロパティを持つ有理数を見つけるためのプログラムを書かなければなりません。プロパティをチェックするコードを書きましたが、今ではすべての有理数をチェックする方法がわかりません。で試してみました

しかし、それは決して終わりません！そして、それはあまりにも多くを逃します。だから私はこれを試しました

しかし、これはたまにしか機能しません。どうすればこれを解決できますか？

私の仕事は、合理的なクラスを開発することです。500 と 1000 が私の入力である場合、(½) は私の出力でなければなりません。私はそれを見つけるために自分でプログラムを書きました。

解決策を見つけるための別の最良の方法はありますか、または私のプログラムはすでに最良の方法ですか?

私はプログラミング コンテストに参加しており、問題の 1 つに「入力データに 10 進数形式の小数が含まれていた」というものがあり0.75ます。

それを解析するのDoubleは簡単ですが (私はreadそのために使用できます)、精度が失われるのは苦痛です。Double比較には非常に注意する必要があります(私はそうではありませんでした) Rational。Haskell にはデータ型があるため、これは冗長に思えます。

それを使用しようとすると、次の形式の文字列を提供する必要があることがわかりました: read、明らかに持っていません。Rationalnumerator % denominator

したがって、質問は次のとおりです。

分数の 10 進数表現を に解析する最も簡単な方法は何Rationalですか?

オンラインジャッジに追加のライブラリをインストールできないため、外部依存関係の数も考慮する必要があります。

The Haskell 98 Reportには、次のように書かれています

浮動リテラルには、小数点の前後に数字が含まれている必要があります。これにより、小数点を別のドット文字の使用と間違えることがなくなります。

これは他にどのような用途がありますか？そのような法的表現は想像できません。

（動機を明確にするために：私は多くの人が のような数字を書いていることを知っています9.0が0.7、私はこれと完全に仲良くすることはできません0.7。.7しかし、末尾の 0 を書き出すことは、ある量が 10 分の 1 まで正確であることを明示しない限り、私にはまったく間違っているように感じ9.0ます。

---

空白で囲まずに関数合成を書くことは合法であることを忘れていました! もちろん、可能性はありますが、浮動リテラルを貪欲に解析することでこの問題を回避できます。たとえば、replicate 3 . pred$8≡ ((replicate 3) . pred) 8but replicate 3.pred$8≡(replicate 3.0 pred)8です。

空白なしで整数リテラルがa のすぐ隣に立つ必要がある式はありませんか?.

限られた精度のユーザー入力をおそらく反復する有理数に変換するために、Farey 分数近似を実装します。
http://mathworld.wolfram.com/FareySequence.html

シーケンス内で最も近いファレー分数を簡単に見つけることができ、Stern-Brocot ツリーを構築して中央分数を再帰的に検索することで Fn を見つけることができます。
http://mathworld.wolfram.com/Stern-BrocotTree.html

ただし、シーケンス Fn の分数を見つけるために私が思いついた方法は、非常に非効率的です:
(疑似)

ほとんどの場合、n = 10^m で m >1 のシーケンス Fn を定義します。

したがって、おそらくシーケンスを一度構築してキャッシュするのが最善かもしれません...しかし、それを導出するためのより良い方法があるはずです。

編集:
この論文には有望なアルゴリズムがあります:
http://www.math.harvard.edu/~corina/publications/farey.pdf

実装してみます。
問題は、彼らの「最も効率的な」アルゴリズムは、前の 2 つの要素を知る必要があることです。どのシーケンスの要素 1 も 1/n であることは知っていますが、2 番目の要素を見つけるのは難しいようです...

EDIT2:
どのようにこれを見落としたのかわかりません:
F0 = 1/nの
場合 x > 2 の場合
F1 = 1/(n-1)

したがって、すべての n > 2 について、最初の 2 つの分数は常に
1/n, 1/(n-1) になり、Patrascu のソリューションを実装できます。

したがって、この質問に対する答えは、ベンチマークを使用して、このソリューションが最適であるかどうかを証明する必要があります..

Cで10進数を有理数近似する方法を知っていますか（ラットMatlab関数と同様）？

アップデート

倍数のP/Q近似が必要な場合、簡単な修正は次のようになります。

エラーは（数値/係数）未満であり、無視できます。

浮動小数点数が与えられた場合、私はString小数に近い有理数の表現を取得しようとしています（与えられた許容範囲内でεは問題ありません）。私の現在のアプローチは次のとおりです。

慣れていない場合はApintMath.pow、任意の長さの数値でも機能します。これは、小数点以下数千桁の小数を変換しようとしているためです。私のアルゴリズムのパフォーマンスはひどいです。

私はこれを2つのことに起因しますが、それ以上の可能性があります。

1. 分数を取得するための私のアプローチはかなり素朴です。もっと良い方法があると確信しています。
2. 分数は単純化されていないため、この分数を使用した後続の計算では、多くの時間が無駄になる可能性があります。

これをどのように行いますか？私が話していない他の分野で私を遅くしているものはありますか？