C ++中许多循环的紧凑形式 [英] compact form of many for loop in C++

问题描述

我有一段代码，如下所示， for 循环的数量由编译时已知的 n 决定.每个 for 循环都在值0和1上进行迭代.目前，我的代码看起来像这样

I have a piece of code as follows, and the number of for loops is determined by n which is known at compile time. Each for loop iterates over the values 0 and 1. Currently, my code looks something like this

for(int in=0;in<2;in++){
    for(int in_1=0;in_1<2;in_1++){
        for(int in_2=0;in_2<2;in_2++){
          // ... n times
            for(int i2=0;i2<2;i2++){
               for(int i1=0;i1<2;i1++){
                   d[in][in_1][in_2]...[i2][i1] =updown(in)+updown(in_1)+...+updown(i1);
               }
            }
          // ...
        }
    }
}

现在我的问题是，是否可以用一种更紧凑的形式编写它.

Now my question is whether one can write it in a more compact form.

推荐答案

n 位 in_k 可解释为小于 2的一个整数的表示形式^ n .

这可以轻松地使用一维数组(向量) d [.] .

This allows easily to work with a 1-D array (vector) d[.].

实际上，整数 j 对应于

j = in[0] + 2*in[1] + ... + 2^n-1*in[n-1]

此外，直接实现是O(NlogN).(N = 2 ^ n)

Moreover, a direct implementation is O(NlogN). (N = 2^n)

例如，可以使用递归解决方案

A recursive solution is possible, for example using

f(val, n) = updown(val%2) + f(val/2, n-1) and f(val, 0) = 0.

在引入记忆的条件下，这对应于O(N)复杂度，此处未实现.

This would correspond to a O(N) complexity, at the condition to introduce memoization, not implemented here.

结果:

0 : 0
1 : 1
2 : 1
3 : 2
4 : 1
5 : 2
6 : 2
7 : 3
8 : 1
9 : 2
10 : 2
11 : 3
12 : 2
13 : 3
14 : 3
15 : 4

#include <iostream>
#include <vector>

int up_down (int b) {
    if (b) return 1;
    return 0;
}

int f(int val, int n) {
    if (n < 0) return 0;
    return up_down (val%2) + f(val/2, n-1);
}

int main() {
    const int n = 4;
    int size = 1;
    for (int i = 0; i < n; ++i) size *= 2;
    std::vector<int> d(size, 0);
    
    for (int i = 0; i  < size; ++i) {
        d[i] = f(i, n);
    }
    for (int i = 0; i < size; ++i) {
        std::cout << i << " : " << d[i] << '\n';
    }
    return 0;
}

---

如上所述，在实现记忆的条件下，递归方法允许O(N)复杂性.

---

As mentioned above, the recursive approach allows a O(N) complexity, at the condition to implement memoization.

另一种可能性是使用一种简单的迭代方法，以获得这种O(N)复杂性.
(这里N代表数据总数)

Another possibility is to use a simple iterative approach, in order to get this O(N) complexity.
(here N represents to total number of data)

#include <iostream>
#include <vector>

int up_down (int b) {
    if (b) return 1;
    return 0;
}
int main() {
    const int n = 4;
    int size = 1;
    for (int i = 0; i < n; ++i) size *= 2;
    std::vector<int> d(size, 0);
    
    int size_block = 1;
    for (int i = 0; i  < n; ++i) {
        for (int j = size_block-1; j >= 0; --j) {
            d[2*j+1] = d[j] + up_down(1);
            d[2*j] = d[j] + up_down(0);
        }
        size_block *= 2;
    }
    for (int i = 0; i < size; ++i) {
        std::cout << i << " : " << d[i] << '\n';
    }
    return 0;
}

这篇关于C ++中许多循环的紧凑形式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！