Генерация всех значений N, вложенных в циклы
Я хотел бы написать функцию, чтобы сделать следующее, учитывая два аргумента функции int K а также int nest_level генерировать все возможные точки, которые возникают в результате создания nest_level вложенные циклы, где каждый цикл варьируется от -K в K, Например, если k = 5 а также nest_level = 3 функция печатает последовательности чисел, которые получаются из следующего:
for(int i = -k; i <= k; ++i)
for(int j = -k; j <= k; ++j)
for(int m = -k; m <= k; ++m)
print(i, j, k)
Это должно работать для любого K а также nest_level
Исходя из моих исследований, я понимаю, что это должно быть рекурсивное решение, но мне трудно реализовать его специально на C++.
5 ответов
Использовать std::vector, Передайте это по ссылке. В цикле i от -k до k:
От себя
iвнутрь.Если длина вектора равна уровню гнезда, выведите.
В противном случае, recurse, передавая вектор по ссылке.
Теперь вытолкните последний элемент из конца вектора и продолжите цикл.
Другой способ решения этой проблемы заключается в том, что вы работаете с числом, каждая цифра которого находится в диапазоне от -K до K. Вы можете увеличивать (-K) (-K) (-K)... (-K) (-K) (- K) до KKK... KKK и выведите промежуточные результаты.
#include <iostream>
#include <vector>
bool increment(int K, std::vector<int> & vals) {
int position = vals.size()-1;
while (vals[position] == K) {
vals[position] = -K;
--position;
if (position == -1) {
return false;
}
}
++vals[position];
return true;
}
void count(int K, int nest_level) {
std::vector<int> vals;
for (int n=0; n<nest_level; ++n) {
vals.push_back(-K);
}
do {
for (auto v : vals) {
std::cout << v << " ";
}
std::cout << "\n";
} while (increment(K, vals));
}
int main()
{
count(1, 2);
return 0;
}
Я не уверен, какой путь лучше, но я подумал, что это была аккуратная параллель.
Из моего исследования я понимаю, что это должно быть рекурсивное решение
Не за что.
Обратите внимание, что если вы не используете излишнюю рекурсию, вы можете избежать определенных потенциальных проблем (уровней рекурсии и роста стека на уровень), и зачастую легче понять код.
Давайте посмотрим на то, что вы делаете. Если мы игнорируем отрицательные числа на данный момент, вы в основном генерируете следующую последовательность (для k=2, n=4):
0 0 0 0 0 1 0 0 0 2 0 0
0 0 0 1 0 1 0 1 0 2 0 1
0 0 0 2 0 1 0 2 0 2 0 2
0 0 1 0 0 1 1 0 0 2 1 0
0 0 1 1 0 1 1 1 0 2 1 1
0 0 1 2 0 1 1 2 0 2 1 2
0 0 2 0 0 1 2 0 0 2 2 0
0 0 2 1 0 1 2 1 0 2 2 1
0 0 2 2 0 1 2 2 0 2 2 2
Если бы k было 9, вы бы просто считали в десятичном виде. Из всех детей, которых я видел, учатся считать, я никогда не знал, чтобы кто-либо делал это с помощью рекурсии.;) Если вы сделаете шаг назад и подумаете о том, как вы научились считать большие числа, вы должны найти гораздо более простое решение... Но я оставлю это на потом.
Если считать в двоичном виде, это будет выглядеть следующим образом:
0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110
7 = 111
Или считать с k=1 а также n=3 (используя -k к k):
0 = -1 -1 -1 9 = 0 -1 -1 18 = 1 -1 -1
1 = -1 -1 0 10 = 0 -1 0 19 = 1 -1 0
2 = -1 -1 1 11 = 0 -1 1 20 = 1 -1 1
3 = -1 0 -1 12 = 0 0 -1 21 = 1 0 -1
4 = -1 0 0 13 = 0 0 0 22 = 1 0 0
5 = -1 0 1 14 = 0 0 1 23 = 1 0 1
6 = -1 1 -1 15 = 0 1 -1 24 = 1 1 -1
7 = -1 1 0 16 = 0 1 0 25 = 1 1 0
8 = -1 1 1 17 = 0 1 1 26 = 1 1 1
Так что, если вы чувствуете себя предприимчивым, вы можете:
- легко рассчитать количество перестановок для вывода
- используйте простой цикл для циклического изменения диапазона
- преобразовать каждое число в базу k*2+1
- смещение каждой цифры путем вычитания k
Конечно, есть и более простой подход, на который намекали ранее. Вызов Counter(k, nest_level); в коде ниже. (Объяснение после)
void WriteVector(const std::vector<int>& v)
{
for (const auto i : v)
std::cout << i << " ";
std::cout << std::endl;
}
bool VectorInc(const int k, std::vector<int>& v)
{
for (auto it = v.rbegin(); it != v.rend(); it++)
{
if ((*it) < k) {
(*it)++;
return true;
}
(*it) = -k;
}
return false;
}
void Counter(const int k, const int n)
{
std::vector<int> v(n, -k);
WriteVector(v);
while (VectorInc(k, v))
WriteVector(v);
}
Counterинициализирует вектор сsize == nest_levelи каждый элемент, содержащий-k,- В цикле это вызывает
VectorIncдля имитации добавления 1 (или подсчета). VectorIncэто очень простая функция, которая перебирает элементы вектора справа налево до тех пор, пока ей необходимо выполнить "перенос".- Обновляет текущий элемент, добавляя 1.
- Но если текущий элемент это на максимуме
k, он должен вернуться к-kи "перенос" +1 к цифре слева. - Когда вектор в конечном итоге достигает
{k, k, k, ..., k}, добавив 1 рулон каждую цифру обратно к-kа такжеVectorIncвозвращает ложь, указывающую на переполнение.
Плюсы: просто, без рекурсии, и будет работать практически со всеми значениями k & n.
Минусы: будет работать практически со всеми значениями k & n. Попробуйте, казалось бы, безобидный звонок, как Counter(10, 80) и вы будете долго ждать, пока ваша программа подсчитает атомы во вселенной.
because both parameters are int type, so ,first you should get their abs value.
//pseud0-code
{
k = abs(k);
nest_level = abs(nest_level);
while(nest_level--){
for(int i = -k; i < k; i++){
printf("%d,%d", nest_level, i);
}
printf("\r\n");
}
}
Как то так, нужен контейнер для хранения номера
#include "iostream"
#include "vector"
void print(const std::vector<int>& v) {
for (auto i : v) {
std::cout << i << ' ';
}
std::cout << std::endl;
}
void genImpl(int K, int level, std::vector<int>& cache) {
if (level == 1) {
for (int i = -K; i <= K; ++i) {
cache.push_back(i);
print(cache);
cache.pop_back();
}
} else {
for (int i = -K; i <= K; ++i) {
cache.push_back(i);
genImpl(K, level - 1, cache);
cache.pop_back();
}
}
}
void gen(int K, int level) {
std::vector<int> cache;
genImpl(K, level, cache);
}
int main() {
gen(2, 3);
return 0;
}