C ++ में लूप के लिए कई का कॉम्पैक्ट रूप
मेरे पास निम्नानुसार कोड का एक टुकड़ा है, और for
छोरों की संख्या निर्धारित n
होती है, जिसे संकलन समय पर जाना जाता है। प्रत्येक for
लूप मान 0 और 1. से अधिक होता है। वर्तमान में, मेरा कोड कुछ इस तरह दिखता है
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);
}
}
// ...
}
}
}
अब मेरा सवाल यह है कि क्या कोई इसे अधिक कॉम्पैक्ट रूप में लिख सकता है।
जवाब
n
बिट्स in_k
पूर्णांक से कम एक का प्रतिनिधित्व के रूप में व्याख्या की जा सकती 2^n
।
यह आसानी से 1-डी सरणी (वेक्टर) के साथ काम करने की अनुमति देता है d[.]
।
व्यवहार में, एक अंतराल से j
मेल खाती है
j = in[0] + 2*in[1] + ... + 2^n-1*in[n-1]
इसके अलावा, एक सीधा कार्यान्वयन हे (NlogN) है। (एन = 2 ^ एन)
उदाहरण के लिए, एक पुनरावर्ती समाधान संभव है
f(val, n) = updown(val%2) + f(val/2, n-1) and f(val, 0) = 0.
यह एक O (N) जटिलता के अनुरूप होगा, इस शर्त पर कि इसे यहां लागू नहीं किया जाएगा।
परिणाम:
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) जटिलता को प्राप्त करने के लिए, एक सरल पुनरावृत्त दृष्टिकोण का उपयोग किया जाए।
(यहां एन कुल आंकड़ों की संख्या का प्रतिनिधित्व करता है)
#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;
}
आप अपने कोड को इस तरह से रिफलेक्टर कर सकते हैं:
for(int in=0;in<2;in++) {
auto& dn = d[in];
auto updown_n = updown(in);
for(int in_1=0;in_1<2;in_1++) {
// dn_1 == d[in][in_1]
auto& dn_1 = dn[in_1];
// updown_n_1 == updown(in)+updown(in_1)
auto updown_n_1 = updown_n + updown(in_1);
for(int in_2=0;in_2<2;in_2++) {
// dn_2 == d[in][in_1][in_2]
auto& dn_2 = dn_1[in_2];
// updown_n_2 == updown(in)+updown(in_1)+updown(in_2)
auto updown_n_2 = updown_n_1 + updown(in_2);
.
.
.
for(int i2=0;i2<2;i1++) {
// d2 == d[in][in_1][in_2]...[i2]
auto& d2 = d3[i2];
// updown_2 = updown(in)+updown(in_1)+updown(in_2)+...+updown(i2)
auto updown_2 = updown_3 + updown(i2);
for(int i1=0;i1<2;i1++) {
// d1 == d[in][in_1][in_2]...[i2][i1]
auto& d1 = d2[i1];
// updown_1 = updown(in)+updown(in_1)+updown(in_2)+...+updown(i2)+updown(i1)
auto updown_1 = updown_2 + updown(i1);
// d[in][in_1][in_2]...[i2][i1] = updown(in)+updown(in_1)+...+updown(i1);
d1 = updown_1;
}
}
}
}
}
और इसे अब एक पुनरावर्ती कार्य में बनाएँ:
template<std::size_t N, typename T>
void loop(T& d) {
for (int i = 0; i < 2; ++i) {
loop<N-1>(d[i], updown(i));
}
}
template<std::size_t N, typename T, typename U>
typename std::enable_if<N != 0>::type loop(T& d, U updown_result) {
for (int i = 0; i < 2; ++i) {
loop<N-1>(d[i], updown_result + updown(i));
}
}
template<std::size_t N, typename T, typename U>
typename std::enable_if<N == 0>::type loop(T& d, U updown_result) {
d = updown_result;
}
यदि आपका प्रकार है int d[2][2][2]...[2][2];
या int*****... d;
, आप मैन्युअल रूप से निर्दिष्ट N
(या जो कुछ भी प्रकार d[0][0][0]...[0][0]
है) के बदले सरणी या सूचक नहीं होने पर भी रोक सकते हैं
यहाँ एक संस्करण है कि एक पुनरावर्ती भेड़ के बच्चे के साथ है:
auto loop = [](auto& self, auto& d, auto updown_result) -> void {
using d_t = typename std::remove_cv<typename std::remove_reference<decltype(d)>::type>::type;
if constexpr (!std::is_array<d_t>::value && !std::is_pointer<d_t>::value) {
// Last level of nesting
d = updown_result;
} else {
for (int i = 0; i < 2; ++i) {
self(self, d[i], updown_result + updown(i));
}
}
};
for (int i = 0; i < 2; ++i) {
loop(loop, d[i], updown(i));
}
मैं यह मान रहा हूं कि यह एक बहुआयामी मैट्रिक्स है। आपको इसे पहले गणितीय रूप से हल करना पड़ सकता है और फिर कार्यक्रम में संबंधित समीकरण लिख सकते हैं।