3

下限Lと上限Uが与えられているという質問に行き詰まっています。
ここで、整数の10進表現で、X数字4が出現Aし、数字7が出現するとしますB。問題は、 forの最大値を持つもの
を見つけることです。 それを解決するための効率的なアルゴリズムはありますか？XA*BL<=X<=U

4

2 に答える 2

5

問題を正しく理解した場合、以下が機能するはずです。

  • すべての数値の桁数が同じであると想定します（たとえば、Lの桁数がUより少ない場合は、最初に0を入力するだけです）。
  • Z = U - Lとします。
  • ここで、最初の（/最高/左端の）桁から最後の桁に移動します。i番目の桁を見る場合、 L（i）、U（i）、Z（i）、およびX（i）を対応する桁とします。
    • 0であるすべての先行Z （i）について、 X（i）= L（i）に設定します（選択の余地はありません）。
    • 最初の0ではないZ（i）チェック：区間[ L（i）、U（i）-1]に4または7がありますか？はいの場合はX（i）を4または7とし、そうでない場合はX（i）= U（i）-1とします。
    • ここで、残りのXを4と7で埋めて、これまでにさらに7を割り当てた場合は4を選択し、その逆も同様です。

たぶん、例はこれを理解するのに役立ちます：

U =5000およびL = 4900の場合。

ここで、 Z =0100です。

設定したアルゴリズムから

  • X（1）= L（1）= 4（選択の余地はありません）
  • X（2）= U （2）-1 = 9（ Zの最初の0以外の数字）
  • X（3）= 7（すでに4があります）
  • X（4）= 4（任意に選択可能）

2 * 1=2の目的でX = 4974につながる

于 2012-06-06T12:22:09.550 に答える
-1

アルゴリズムはすでに考えられているようです。それを少しずつ分解し、各部分を解決するだけです。私は通常、コメントを付けてそこで行ったようなことを書き、コードを書くのに適切なバイトサイズになるまでそれらを分解します。

動作させると、必要に応じて最適化できます。

于 2012-06-05T14:08:42.587 に答える