寻找“像样”的数字算法的原理？

Question

寻找“像样”的数字算法的原理？

pythonalgorithmpython-3.x

9

问题

福尔摩斯对他的头号敌人莫里亚蒂感到非常焦虑。他为制服莫里亚蒂所做的努力都没有奏效。近日，福尔摩斯正在与沃森医生一起研究一个问题。沃森提到CIA最近在他们的超级计算机"The Beast"上遇到了奇怪的问题。

今天下午，福尔摩斯收到莫里亚蒂的便条，称他已经在"The Beast"中注入了病毒。此外，这张纸条上还印着数字N。经过一番计算，福尔摩斯发现去除病毒的关键是拥有N位数的最大"Decent"数。

一个"Decent"数必须满足：

其数字为3或5或二者兼有。
不允许使用其他数字。
数字3出现的次数可被5整除。
数字5出现的次数可被3整除。

与此同时，“The Beast”的毁灭倒计时正在快速运行。你能在福尔摩斯之前拯救“The Beast”并找到密码吗？

输入格式第一行包含整数T，表示测试用例的数量。接下来是T行，每行包含一个整数N，即数字位数。

输出格式拥有N位数的最大Decent数。如果不存在这样的数字，请告诉福尔摩斯他错了，并打印“-1”

约束条件 1<=T<=20 1<=N<=100000

示例输入

样例输出

-1
555
33333
55555533333

解释: 当N=1时，不存在这样的数字。

当N=3时，只有555是可能的数字。

当N=5时，只有33333是可能的数字。

当N=11时，55555533333和所有数字排列组合都是有效的数字，其中给定的数字是最大的一个。

答案

for _ in range(int(input())):
    n = int(input())
    c = 5*(2*n%3)
    if c > n:
        print(-1)
    else:
        print('5' * (n-c) + '3'*c)

问题

有人能解释一下背后的原因吗？具体来说，'c'变量的赋值是在做什么？

来源：https://www.hackerrank.com/challenges/sherlock-and-the-beast

- Amorphous

2

首先，如果n是3的倍数，则2*n%3将为0，如果n-1是3的倍数，则为2，如果n+1是3的倍数，则为1。因此，在这三种情况下，c将分别为0，10或5。（如果还不清楚，请打印出[5 *（2 * n％3）for n in range（20）]。）请注意，c有什么用处 - 您有n-c个5和c个3。这足以弄清楚吗？ - abarnert

4个回答

4

好的，思路如下。

1.确定需要多少个5和3，应优先选择5。虽然排序不影响结果，但如果5放在前面，数字会更大。 2.所需3的数量应是满足约束条件的最小值，因为这样将有更多的5，从而得到更大的数字。 3.3的数量必须能被5整除。这意味着没有必要使用超过10个3，只需考虑0、5或10个3。这是因为你希望留下的数字数量是3的倍数，以满足其他约束条件。如果15个3有效，则0个3同样有效；如果20个有效，则5个也是；如果25个有效，则10个也是。一般来说，从3的数量中减去15仍然可以使约束条件满足。 4.因此，5的数量必须为n-0、n-5或n-10，并且我们希望得到一个可被3整除的数字。计算式c = 5*(2*n%3)将给您0个3和n个5，如果n已经被3整除；如果n比3的倍数多1，则会得到10个3和n-10个5。此时n-10仍然可以被3整除，依此类推。 5.唯一需要测试的是计算出来的c个3和n-c个5是否满足隐含的约束条件：n-c应为非负数。如果是负数，则没有解决方案；如果是非负数，则这是一个有效的解决方案，将5放在前面会得到最大的解决方案。

这是一类“编程”问题中相当广泛的问题之一，测试的目的并不是看您是否能敲出一些完成任务的代码，而是看您是否可以逻辑上把问题简化到极致，并且可以非常高效地解决它。

- chiastic-security

0

x = int(raw_input())
while x!= 0 :
    y=int(raw_input())
    z=y
    while(z%3!=0):
        z-=5
    if(z<0):
        print '-1'
    else:
        print z*'5'+(y-z)*'3'
    x = x-1

如果一个数字（比如66317）不能被3整除，那么它的模数只能是0、1或2。如果我将这个数字减去5，就相当于让它成为3的倍数，而剩下的数字将是5的倍数，因为我从这个数字中减去了5。

模数0表示数字可被整除，模数1表示需要减去5两次，模数2表示需要减去5一次。

- Ankur

0

我认为数学有所帮助，我查阅了不同部分和历史的资料。我的解决方案第一次通过了所有15个测试，因此虽然我没有使用数学，但我的方法可能会对您有所帮助。我将10及以下的情况视为边缘情况，直接硬编码处理。超过10的情况，我将其除以3以获得最多的“555”。当然，在除以3时，余数只能是0、1或2。当余数为零时，只需写下相应数量的555即可。当余数为1时，减去3个555即可获得10个三个的空位。当余数为2时，减去1个555即可留下5个33333的空位。

3个if语句用于处理余数。 10个if语句用于处理边缘情况。 1个if语句用于处理约束条件。 1个for循环。

- Richard Bradley Smith

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ben · Accepted Answer

一种数学解决方案：

令a = '5'的长度，b = '3'的长度。因此

a + b = N

我们知道3可以整除a，5可以整除b，因此令a = 3n，b = 5m

3n+5m = N

这是一个丢番图方程式 (http://en.wikipedia.org/wiki/Diophantine_equation)，其中一个解为(n0, m0) = (2N, -N)，通解为

(n,m) = (5k+2N, 3K-N)，k为任意整数

现在的问题是要最小化数量3k-N (因为你想要更多的'5')，以便使3k-N > 0。这相当于找到k，使得3k是从N开始的下一个3的倍数。

例如，如果N = 10或11，我们正在寻找3k = 12，或者k = 4。

因此，3k-N是N和下一个3的倍数之间的距离。解题者声称3k-N=2N%3，通过计算N%3 = 0, 1和2的情况，证明了这一点。记录一下，在表达式'2N％3'中的“2”并不是唯一的，它可以适用于序列2、5、8、11…中的任何数字，为什么作者选择了这个特定的表达式，我不知道。

您还可以考虑在这种情况下N%3表示N与下一个较小的3的倍数之间的距离。