好吧,我必须编写一个程序来找到给定数字 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;
}
最佳答案
你的问题不是编程问题而是数学问题。
让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,因此在大多数实现中它应该适合您的数据范围.
关于c++ - 找到具有特定数字(7)的最接近的特定数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15173713/