1

さて、正確に「K」個の 7 を持つ特定の数 N の最も近い数を見つけるプログラムを作成する必要があります。

たとえば、入力が次の場合:

N K
1773 3

出力：

1777

ああ、もう 1 つ、N は最大で 100 000 000 000 000 になる可能性がありますが、これを処理するには long long で十分でしょうか?

これまでのところ動作していない私のコード:(

#include <iostream>
using namespace std;
int main()
{
    unsigned long long a, i;
    int b, num=0, dig, tmp;
    cin>>a>>b;
    i=a+1;
    do
    {
        num=0;
        tmp=i;
        while (tmp>0)
        {
            dig=tmp%10;
            tmp=tmp/10;
            if (dig==7)
            num++;
        }
        i++;
    }
    while(num<b);
    cout<<i-1;
    return 0;
}
4

3 に答える 3

2

あなたの問題はプログラミングの問題ではなく、数学の問題です。

Let m = 1+E(log10(N))、つまり の 10 進数表記の桁数N(対数を使用するよりも桁数を数えて計算する方がおそらく高速です)。

の数mKを と7しNます。

を出力N'数とします。

私は4つのケースを見ます:

  • K >= m: 次にN' = 7..7(K桁)。
  • K == mK：その後N' = N。
  • K > mK and K < m: 次に、最下位桁から順に、すべての非7数字をに置き換えます。7例: N = 1 357 975 , K = 4 => N' = 1 357 777. 警告 : がある場合は特殊なケースがあります。8例: N = 80, N' = 79. この場合、共通の接頭辞を使用してから、すべての7接尾辞を生成します (特殊なケース: 接頭辞からもう 1 つ削除して を追加します7 9 7 7 ... 7)。special caseコードで参照してください。

  • K < mK: 可能な数は 2 つあります。

    分解しましょうN: N = a1 a2 ... ap 7 b1 b2 ... bq, where

    • a1 ... apとはp数字です[0..9]
    • b1 ... bqのq数字です[0..9] \ {7}

    and (または の後の数字)A = a1 ... ap 6 9 ... 9とします。次に、. 両方の数値が等しく近い場合、選択はあなた次第です。B = a1 ... ap 8 0 ... 0q68N' = closestToN(A,B)

数学の書式設定が悪くてすみません。 コードをより簡単に記述できるようになりました。ここに私の実装があります:

#include <iostream>

unsigned long long getClosestWith7(unsigned long long n, unsigned int k)
{
    // Count number of digits
    unsigned long long tmp = n;
    unsigned int m = 0, mK = 0;
    while(tmp > 0)
    {
        if(tmp % 10 == 7) mK++;
        tmp /= 10;
        m++;
    }

    // Distinct cases
    if(k == mK && n != 0)
        return n;
    else if(k >= m || n == 0) // implicit: k != mK
    {
        unsigned long long r = 0;
        while(k > 0)
        {
            r = 10 * r + 7;
            k--;
        }
        return r;
    }
    else if(k > mK) // implicit: k != mK, k < m
    {
        unsigned long long r = n;
        unsigned long long s = 0;
        m = 0;
        while(mK < k)
        {
            if(r % 10 != 7) mK++;
            r /= 10;
            m++;
        }
        if(r % 10 == 8) // special case
            s = 79 + 100 * (r / 10);
        while(m > 0)
        {
            r = 10 * r + 7;
            if(s != 0 && m > 1) // special case
                s = 10 * s + 7;
            m--;
        }
        return (r < n && n - r < n - s) || (r >= n && r - n < n - s) ? r : s;
    }
    else // implicit : k < mK
    {
        // Generate a and b
        unsigned long long a = n;
        unsigned long long b = 0;
        m = 0;
        while(mK > k)
        {
            if(a % 10 == 7) mK--;
            a /= 10;
            m++;
        }
        b = 10 * a + 8;
        a = 10 * a + 6;
        m--;
        while(m > 0)
        {
            a = 10 * a + 9;
            b = 10 * b + 0;
            m--;
        }

        // Compare (return lowest if equal)
        return n - a <= b - n ? a : b;
    }
}

#define CLOSEST7( N , K ) \
    std::cout << "N = " << N << ", K = " << K << " => N' = " << getClosestWith7(N,K) << "\n"

int main()
{
    CLOSEST7(1773,3);
    CLOSEST7(83,1);
    CLOSEST7(17273,3);
    CLOSEST7(1273679750,6);
    CLOSEST7(1773,1);
    CLOSEST7(83,5);
    CLOSEST7(0,2);
    CLOSEST7(0,0);
}

についての質問についてlong longは、コンパイラに依存します。多くの場合、この型のサイズは 64 ビットであるため、0 から 2^64 - 1 (符号なし) までの数値を格納できます。これは 18 446 744 073 709 551 615 であり、ほとんどの実装ではデータ範囲で問題ありません。 .

于 2013-03-02T12:00:03.393 に答える
1

いくつかの問題：

  • ans=i数回に分けて録音iするので、オリジナルを録音する必要がありますi
  • 一方向にのみループします。同時に両方向にチェックインする必要があります
  • すべての数値をループするのは基本的に遅すぎる
    • 数値が 100 000 000 000 000 で k = 14 の場合、22 222 222 222 223 (100 000 000 000 000-77 777 777 777 777) の数値を確認する必要がありますが、これは実行できません。

補足 - long long の最大値は 9223372036854775807です。

動作するはずの疑似コードを次に示します。

num = number of 7s in input
if (num == k)
  print input
if (num < k)
  a = input with (k-num) non-7 digits from least significant digit set to 7
    let x = last position set
  b = substring(input, 1, position)
  c = b + 1
  d = b - 1
  ba = concat(b, substring(a, position, end))
  ca = concat(c, substring(a, position, end))
  da = concat(d, substring(a, position, end))
  if (abs(input - ba) <= abs(input - ca) &&
      abs(input - ba) <= abs(input - da))
    print b
  else
  if (abs(input - ca) <= abs(input - ba) &&
      abs(input - ca) <= abs(input - da))
    print c
  else
    print d
if (num > k)
  x = (k-num)th 7 from least significant digit
  a = input with x set to 6 and all less significant digits to 9
  b = input with x set to 8 and all less significant digits to 0
  if (input - a > b - input)
    print b
  else
    print a
于 2013-03-02T11:33:52.303 に答える
0

このアルゴリズムはどうですか？

  1. 数値を文字列に変換します。

  2. その中の7の数を数えます。

  3. Kよりも7が少ない場合は、Kに達するまで、数字を右端から左に1つずつ7に変更してから、手順5に進みます。

  4. Kより7が多い場合は、7の場合に限り、右端から左に1つずつ6に変更し、Kに達するまで手順5に進みます。

  5. それを整数に変換し直します。

long longDukelingの答えによると使用可能です。

于 2013-03-02T13:59:54.597 に答える