找到特定数量最接近的数字里面有具体的数字（7） [英] Find the nearest number of specific number which has specific digit (7)
问题描述
好吧，我必须写一个程序，找出其中恰好有K7S给出数N最接近的数字。
例如，如果输入的是：
ñķ
1773 3
输出：
1777
哦，还有一件事是，N可以是100 000 000 000 000最大的，将长长足以处理呢？
我的code，到目前为止这是不工作：（
的#include＆LT;＆iostream的GT;
使用命名空间std;
诠释的main（）
{
无符号长一长，我;
INT B，NUM = 0，挖，TMP;
霉素＆GT;＆GT a取代;＆GT; B;
I = A + 1;
做
{
NUM = 0;
TMP = I;
而（TMP大于0）
{
挖TMP = 10％;
TMP = TMP / 10;
如果（DIG == 7）
NUM ++;
}
我++;
}
而（NUM＆LT; B）;
COUT＆LT;＆LT; I-1;
返回0;
}
您的问题不是编程问题，而是一个数学问题。
让 M = 1 + E（log10的（N）），即位数的 n中的十进制书面号（这将是可能更快地计数数字来计算它比使用对数）。
让 mK的是 7 在 N 。
让 N'是输出数量。
我见第4的情况：
-
K＆GT; = M：那么N'= 7..7（氏/ code>位）。 -
K == mK的：那么N'= N -
K＆GT; mK的且K;米：那么您更换所有非 - 以77数字，从最开始显著数字。例如：N = 1 357 975，K = 4 = GT; N'= 1 357 777。警告：有一个特殊的情况下，如果你有一个8，例如：N = 80，N = 79。您可以通过使用一个共同的preFIX，然后生成所有的7后缀（特殊情况下做到这一点的情况下：从preFIX删除一个越来越添加7 9 7 7 7 ...）。参见特殊情况在code。 -
K＆LT; mK的：有两种可能的数字让我们分解
N：N = A1 + A2 ......美联社7 B1，B2，... BQ，其中-
A1 ... AP在P数字[0..9] -
B1 ... BQ在①数字[0..9] \\ {7}
让
A = A1 ... AP 6 9 9 ...和B = A1 ...美联社8 0 0 ...（①在6或8 ）。然后，N'= closestToN（A，B）。如果这两个数字都同样接近，选择权在你。 -
的对不起，我数学不好的格式。的
在code现在可以更容易编写。 这是我实现：
的#include＆LT;＆iostream的GT;无符号长长getClosestWith7（无符号长N久，无符号整型K）
{
//数字计数
无符号长长TMP = N;
无符号整型m = 0时，MK = 0;
而（TMP大于0）
{
如果（TMP％10 == 7）mK的++;
TMP / = 10;
M +;
} //不同的情况
如果（K == mK的＆放大器;＆安培; N！= 0）
返回N;
否则，如果（K＆GT; = M ||ñ== 0）//隐：K = mK的
{
无符号长长R = 0;
而（K＆0）
{
R = 10 * R + 7;
K--;
}
返回ř;
}
否则，如果（K＆GT;可）//隐：K = MK，K＆LT;米
{
无符号长长R = N;
无符号长长S = 0;
M = 0;
而（谷＆LT; K）
{
如果（R％10 = 7！）mK的++;
R / = 10;
M +;
}
如果（R％10 == 8）//特例
S = 79 + 100 *（R / 10）;
而（M 0）
{
R = 10 * R + 7;
如果（S = 0＆放大器;！＆放大器; M＆→1）//特例
S = 10 * S + 7;
M--;
}
收益率（R＆LT; N＆放大器;＆安培; N - R＆LT; N - S）|| （R＆GT; = N＆放大器;＆安培; R - N＆LT; N - S）？ R：S;
}
否则//隐：K＆LT; mK的
{
//生成a和b
无符号长长= N;
无符号长长B = 0;
M = 0;
而（mK的＆GT; K）
{
如果（一个10％== 7）mK--;
一个/ = 10;
M +;
}
B = 10 * A + 8;
一个= 10 * A + 6;
M--;
而（M 0）
{
一个= 10 * A + 9;
B = 10 * B + 0;
M--;
} //比较（如果相等返回最低）
返回N - A＆LT; = B - N？ A：B;
}
}＃定义CLOSEST7（N，K）\\
性病::法院LT＆;＆LT; N =＆LT;＆LT; N'LT;＆LT; K =＆所述;＆下; K＆LT;＆LT; =将N'=＆所述;＆下; getClosestWith7（N，K）LT;＆LT; \\ n诠释的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）;
}
有关你关于问题长长：这取决于编译器。通常情况下，这种类型的大小为64位，这样你就可以从0到2 ^ 64存储 - 1（无符号），这是18 446 744 073 709 551 615，让您的数据范围上大多数实现它应该是确定
Well, I have to write a program to find the NEAREST number of given number N which has exactly "K" 7s.
For example, if input is:
N K
1773 3
Output:
1777
Oh, one more thing is that N can be 100 000 000 000 000 maximum, will long long be enough to handle this?
My code so far which is not working :(
#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;
}
Your problem is not a programming problem but a math problem.
Let m = 1+E(log10(N)), ie the number of digits in the decimal writing of N (it will be probably faster to compute it by counting digits than using a logarithm).
Let mK be the number of 7 in N.
Let N' be the output number.
I see 4 cases:
K >= m: thenN' = 7..7(Kdigits).K == mK: thenN' = N.K > mK and K < m: then you replace all non-7digits with7, starting from the least significant digits. Ex:N = 1 357 975 , K = 4 => N' = 1 357 777. Warning : there is a special case, if you have a8, ex:N = 80, N' = 79. You can do this case by using a common prefix, and then generating an all7suffix (special case: remove one more from the prefix and add7 9 7 7 ... 7). Seespecial casein the code.K < mK: there are two possible numbers.Lets decompose
N:N = a1 a2 ... ap 7 b1 b2 ... bq, wherea1 ... aparepnumbers in[0..9]andb1 ... bqareqnumbers in[0..9] \ {7}
Let
A = a1 ... ap 6 9 ... 9andB = a1 ... ap 8 0 ... 0(qdigits after the6or the8). Then,N' = closestToN(A,B). If both numbers are equally close, the choice is up to you.
Sorry for the bad math formatting. The code can now be more easy to write. 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);
}
For your question about long long: it depends on the compiler. Often, the size of this type is 64 bits, so you can store number from 0 to 2^64 - 1 (unsigned), which is 18 446 744 073 709 551 615, so it should be ok for your data range on most implementations.
这篇关于找到特定数量最接近的数字里面有具体的数字（7）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
