• ベストアンサー
  • すぐに回答を!

符号の決定

  • 質問No.7832579
  • 閲覧数54
  • ありがとう数1
  • 気になる数0
  • 回答数2
  • コメント数0

お礼率 71% (399/560)

アルゴリズムの設計と解析II の82ページです。

条件:文字はすべて否負の整数とする。さらに、
f > g
f = (f_1)*2^k + (f_2)
g = (g_1)*2^k + (g_29
(f_2) < 2^k
(g_2) < 2^k
(f_1) <= (g_1)^2
f = qg + r
r < g
(f_1) = (q_1)*(g_1) + (r_1)
(r_1) < (g_1)

このとき、
(g_1)*(2^k)*(q - q_1) = (f_2) + (r_1)*(2^k) - q*(g_2) - r
が成立し(確かに成立します。)

q - (q_1) <= 0

を簡単に示すことが出来る。のだそうですが
示せません。

助けて下さい。

質問者が選んだベストアンサー

  • 回答No.2
  • ベストアンサー

ベストアンサー率 23% (3656/15482)

って~か,
q - (q_1) <= 0
を示すのに
(g_1)*(2^k)*(q - q_1) = (f_2) + (r_1)*(2^k) - q*(g_2) - r
なんていらんよねぇ.

ほぼ当たり前なわけだし.
お礼コメント
uyama33

お礼率 71% (399/560)

ありがとうございました。

q=q_1 + k

として、

f = (q_1 + k)g +r

を計算したら、

f_2 > 2^k

となりました。
投稿日時:2012/12/07 17:45

その他の回答 (全1件)

  • 回答No.1

ベストアンサー率 23% (3656/15482)

最悪背理法を使えば
q_1 ≧ q
が示せる.
結果を報告する
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。
関連するQ&A

その他の関連するQ&Aをキーワードで探す

ピックアップ

ページ先頭へ