2

多くのプログラミング問題では、上記の制約が言及されています。私はこれをcodechefとSPOJで見ました。

例えば​​Link-1、Link-2など。(これら 2 つのサンプル リンクの OUTPUT セクションを参照してください)

この制約の意味は何ですか? そして、この制約が出力によって指定されていることを確認するにはどうすればよいですか?

4

4 に答える 4

11

絶対誤差は次のとおりです。

|computedAnswer - correctAnswer|

相対誤差は次のとおりです。

|(computedAnswer - correctAnswer) / correctAnswer|

直観的には、絶対誤差は、計算された答え (または近似値) が正しい (おそらく未知の) 答えからどれだけ離れているかです。相対誤差は、正解に対する絶対誤差の比率です。

したがって、レーザー レンジャーを使用して月までの距離を測定している場合でも、フォックス トロットで左足を正しく配置しようとしている場合でも、どちらの場合も絶対誤差は 0.5 メートルになる可能性があります。月の距離測定では、それはかなり良いでしょう。フォックストロットの場合、Dancing with the Stars を開始できます。

于 2013-03-03T22:12:06.903 に答える
3

Ted Hopp が言ったことに加えて、エラーを減らすためにおそらく重要な要因は、次の方法で浮動小数点のドリフト/不正確さを最小限に抑えることです。

  • 入力で機能する一連の操作を簡素化/評価することにより、浮動小数点計算の合計を削減します。(たとえば、数式をできる限り単純化します)。これは、浮動小数点エラーが後続の操作で複合化するためです。
  • 計算に最高精度 (倍精度など) を使用します。
  • または、小数型またはより数値的に健全なクラスを利用して、最後に浮動小数点値に評価することもできます。
于 2013-03-03T22:32:22.920 に答える
2

これは簡単なコンピューターの問題です: 1/3 を評価します。

浮動小数点や倍精度などの「通常の」コンピュータ数値を使用する場合、計算された 1/3 のバージョンは 0.3333 にはなりません....、それは 0.333333333332 または 0.333333333334 または同様のものになります。浮動小数点数または有限 10 進展開のいずれかとして表されます。1/3 を 10^-6 の相対誤差と絶対誤差の範囲内で評価することは確かに可能です。0.333333333332 と 0.333333333334 の両方がこの精度要件を満たしています。

したがって、答えが 10^-6 以内の精度であるというこの要件により、浮動小数点と倍精度のみを使用した正確な数値解がない問題に対して、浮動小数点と倍精度を使用したコンピューター ソリューションが可能になります。実際、これはほとんどすべての数値問題です。ほとんどの分数は正確に数値的に計算できません。コンピュータは近似値を使用します。

于 2013-03-04T06:26:02.360 に答える
1

問題提起者は次のように言っています。

sqrt((your_answer - their_answer)^2) < 1*10^-6

それならあなたは「正しい」

浮動小数点値を正確に比較することは非常に問題があります。これは、限られた精度のマシンでの丸めによるものです (つまり、1.0/3.0 のように、一部の数学の答えは有限の桁数で表すことができません)。

コンピュータ上で実行される問題の多くのソリューションは、反復的です。つまり、最初の推測から始めて、推測をどれだけ変更するかを計算します。次に、これを繰り返して、推測をどれだけ変更するかを計算します。この手順を繰り返すと、推測の変更量がどんどん小さくなります (収束します)。変化が指定された量よりも小さくなると、答えが収束したと見なされ、「正しい」答えが得られます。勾配まともなアルゴリズムは、この手法の典型的な例です。提供されたリンクを詳しく見ていませんが、おそらく答えを得るには反復解が必要です。この場合、解が収束したかどうかをテストするための制限として 1.0 * 10^-6 を使用する必要があります。

http://en.wikipedia.org/wiki/Gradient_descent

あなたが投稿したサイトへのリンクは、数値的な方法に役立つ問題のようです。

http://en.wikipedia.org/wiki/Numerical_analysis

いくつかの困難な問題を抱えた興味深いサイトのようです。

于 2013-03-03T23:41:55.457 に答える