且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

CountDiv(Codility)挑战算法的性能问题

更新时间:2022-02-06 23:40:56

使用循环是蛮力,而像这样的挑战无法通过蛮力来完成.

Using a loop is brute-force, and challenges like this cannot be done with brute-force.

这意味着您必须计算结果.像这样的挑战通常是数学问题,而不是编程问题,所以戴上数学帽子.

Which means you have to calculate the result. Challenges like this are more often a math question more than a programming question, so put you math hat on.

所以考虑一下.在整数范围内,计算有多少可以被 K 整除.如果我让你手动(允许使用简单的计算器),而不使用计算机来计算暴力破解,你会怎么做?例如.求 111999 之间能被 13

So think about it. In a range of integers, calculate how many are divisible by K. If I asked you to do this manually (using a simple calculator is allowed), without using a computer to brute-force it, how would you doing it? E.g. find how many integers between 111 and 999 that are divisible by 13

提示

找到范围内可以被 K 整除的第一个数字,以及范围内可以被 K 整除的最后一个数字.对于上面的例子,这将是 117988代码>.

Find the first number in the range that is divisible by K, and the last number in the range that is divisible by K. For the example above, that would be 117 and 988.

现在计算从第一个整数到最后一个整数有多少个整数可以被 K 整除,记住同时计算它们.那么,117988 之间有多少个整数可以被 13 整除?

Now calculate how many integers are divisible by K from first to last integer, remembering to count both of them. So, how many integers between 117 and 988 are divisible by 13?

答案:(988 - 117)/13 + 1 = 871/13 + 1 = 67 + 1 = 68