c++ - 找到具有特定数字(7)的最接近的特定数字

Question

好吧，我必须编写一个程序来找到给定数字 N 中正好有“K”个 7 的最近数。

例如，如果输入是:

N K
1773 3

输出:

1777

哦，还有一件事是 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;
}

Answer 1

你的问题不是编程问题而是数学问题。

让m = 1+E(log10(N)) ，即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 .您可以通过使用公共(public)前缀来完成这种情况，然后生成所有 7后缀(特殊情况:从前缀中再删除一个并添加 7 9 7 7 ... 7 )。参见 special case在代码中。

• K < mK : 有两个可能的数字。

  让我们分解 N : N = a1 a2 ... ap 7 b1 b2 ... bq , 其中

  • a1 ... ap是p [0..9] 中的数字和
  • b1 ... bq是q [0..9] \ {7} 中的数字

  让A = a1 ... ap 6 9 ... 9和 B = a1 ... ap 8 0 ... 0 ( q 数字在 6 或 8 之后)。然后，N' = closestToN(A,B) .如果两个数字同样接近，则选择由您决定。

抱歉数学格式不正确。代码现在可以更容易编写。 Here is my implementation :

#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，因此在大多数实现中它应该适合您的数据范围.