Алгоритм для деления плитки шоколада в равной степени
Попробуйте получить строку с помощью метода getResources():
String yourString = context.getResources().getString(R.string.yourResource);
3 ответа
Мне кажется, что вы ищете числа, которые без остатка делятся на все числа от 1 до n включительно. Это называется наименьшим общим кратным 1, ..., n. Квадрат, содержащий наименьшее общее кратное 1, ..., n квадратов, по определению может быть равномерно разделен на части размером 1, ..., n. Вы ищете максимум n разделений, что добавляет сложности к проблеме, которая может быть или не быть возможной.
Ваш пример для n = 4 - это НОК (4,3,2,1), что равно 12 . LCM (5,4,3,2,1) - 60. LCM (6,5,4,3,2,1) также 60.
Их всегда можно представить как 1xLCM (n, .. ., 1) прямоугольников и всегда можно разделить на 1, ..., n четных стопок в n-1 или меньшем количестве делений.
Например, когда n = 4, НОК (4,3,2,1) = 12. Прямоугольник
############
и может быть разделен следующим образом:
1: ############ // 0 cuts
2: ###### ###### // 1 cut
3: #### #### #### // 2 cuts
4: ### ### ### ### // 3 cuts (3 being n-1)
Since you can not cut multiple pieces at once, for any number of pieces m you want where m is in the set (1..n), you will always need m-1 cuts. Each cut creates one more piece, you start with one piece.
Building on the previous solution, I think you were looking intuitively for the following algorithm:
A = LCM(n)
p = greatest divisor of A <= sqrt(A)
q = A/p
The algorithms for this should be trivial, (e.g. start with p = floor(sqrt(A)) and count down until mod(A,p) == 0).
The reason you want sqrt is to limit the amount of numbers you check. After all, you will always have one divisor <= sqrt(A) and one >= sqrt(A)
Хороший способ ответить на этот вопрос - использовать алгоритм поиска в ширину. Алгоритм будет пробовать все возможные разрывы всей плитки шоколада. Затем для каждого из этих возможных состояний проблемы попробуйте все возможные разрывы, и это будет продолжаться, отслеживая ровность частей.
Я хотел бы добавить, что правила будут определять, какие разрывы плитки шоколада являются допустимыми, а те возможные состояния, которые не являются законными, исключаются из алгоритма.