skipping recursion

Question

Первая строка - это номер, int x. Следующие строки m содержат буквы. После m строк вы читаете число, int y.

Цель состоит в том, чтобы найти номер soluiton, int y, из рекурсии 1 буквы из каждой строки.

Проблема заключается в том, что существует гораздо более быстрое решение, которое позволяет избежать каждого возможного пароля. Вот где мой вопрос. Как это может быть сделано? Любая помощь будет принята с благодарностью.

Answer 1

Это не так уж сложно. Вы можете подсчитать количество букв в m строках. Затем вы вычисляете значение для каждой строки букв, которое указывает, сколько допустимых решений пропущено, если одна буква в ссылочной строке пропущена. Визуализация:

abc -> 3 letters 
xy -> 2 letters 
dmnr -> 4 letters 

если вы пропускаете из п-го письма к п + 1-й буквы в строке «ABC», пропустить как можно больше возможных решений как произведение длины каждой следующей строки говорит , поэтому вы пропустите 2 * 4 решения ->8 solutions.

повторите этот шаг для xy ->4 solutions пропущено.

Последняя строка пропускает alwasy 1 solution, потому что это путь рекурсии.

так что теперь вы знаете, сколько решений вы пропустите, если вы перейдете к определенной букве. последнее простое. вы начинаете с 1 и добавляете вычисленное значение каждой строки к числу, пока оно не достигнет ровно r.

означает в C++:

int v = 1, r=10; 
int i1=0, i2=0, i3=0; 

while (v<=r-8) { 
    i1++; 
    v+=8; 
} 
while (v<=r-4) { 
    i2++; 
    v+=4; 
} 
while (v<=r-1) { 
    i3++; 
    v++; 
} 

Теперь i1 является индексом письма, необходимо использовать от линии «ABC», i2 является индексом письма от «х» и i3 от «dmnr " :) это все. алгоритм должен заканчиваться на i1 = 1, i2 = 0, i3 = 1 -> "b" + "x" + "m"

Надеюсь, это поможет. Он удаляет рекурсию, но это не проблема, не так ли? ;)