文章/答案/技术大牛

发布

社区首页 >问答首页 >查找具有特定数字(7)的最接近的特定数字

问查找具有特定数字(7)的最接近的特定数字
EN

Stack Overflow用户

提问于 2013-03-02 19:04:16

回答 3查看 789关注 0票数 1

嗯，我必须写一个程序来找出给定数字N的最接近的数字，它恰好有"K“7。

例如，如果输入为：

N K
1773 3

输出：

哦，还有一件事是N最多可以是100,000,000,000，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;
}

c++

arrays

numbers

digit

回答 3

Stack Overflow用户

回答已采纳

发布于 2013-03-02 20:00:03

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

设为m = 1+E(log10(N))，即N的十进制书写中的位数(通过计算位数可能比使用对数更快)。

设mK为N中7的个数。

让N'作为输出数字。

我看到了4个案例：

K >= m：然后是digits).
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。您可以通过使用通用前缀，然后生成一个all 7后缀(特殊情况:从前缀中再删除一个并添加7 9 7 7 ... 7)来完成此操作。参见code.
K < mK中的special case：有两个可能的数字。

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

- `a1 ... ap` are `p` numbers in `[0..9]` and
- `b1 ... bq` are `q` numbers in `[0..9] \ {7}`

让A = a1 ... ap 6 9 ... 9和B = a1 ... ap 8 0 ... 0 (6或8后面的q数字)。然后是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，因此在大多数实现中，它对于您的数据范围应该是合适的。

票数 2

Stack Overflow用户

发布于 2013-03-02 19:33:52

一些问题：

ans=i记录一些数字经过几次划分后，你需要记录原始的i
You循环只有一个方向，你需要同时在两个方向上检查
遍历所有数字从根本上来说太慢了
- 如果数字是100 000 000 000并且k= 14，你需要检查22 222 222 222 223 (100 000 000 000-77 777 777 777)数字，这不是viable

旁注- the maximum for long long is 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

票数 1

Stack Overflow用户

发布于 2013-03-02 21:59:55

这个算法怎么样？

将数字转换为字符串。
计算其中的7个数。
如果数字中的7小于K，则将数字从最右边到左边逐个更改为7，直到达到K，然后转到步骤5。
如果数字大于K，则仅当数字为7时才从最右边到左边逐个更改为6，直到达到K，然后转到步骤5。

<代码>H19将其转换回整数。<代码>H210G211

根据杜克林的回答，long long是可用的。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/15173713

复制

相似问题

问查找具有特定数字(7)的最接近的特定数字
EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问查找具有特定数字(7)的最接近的特定数字EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问查找具有特定数字(7)的最接近的特定数字
EN