ПРОШУ ПОМОЧЬ С С++

Question

ПРОШУ ПОМОЧЬ С С++

Лейла Нуриева Ученик (90), на голосовании 2 дня назад

По данным числам N и K выведите все строки из нулей и единиц длины N, содержащие ровно K единиц, в лексикографическом порядке.

Answer 1

 #include <iostream>  
 
#include <string>  
 
  
 
void generateStrings(int N, int K, std::string s, int idx) {  
 
    if (K == 0) {  
 
        while (s.length() < N) {  
 
            s += '0';  
        }  
 
        std::cout << s << std::endl;  
 
        return;  
    }  
 
  
    if (idx >= N) {  
 
        return;  
    }  
 
    generateStrings(N, K-1, s + '1', idx+1);  
 
    generateStrings(N, K, s + '0', idx+1);  
 
}  
  
 
int main() {  
 
    int N, K;  
 
    std::cout << "Введите число N: ";  
 
    std::cin >> N;  
 
    std::cout << "Введите число K: ";  
 
    std::cin >> K;  
 
    generateStrings(N, K, "", 0);  
 
    return 0;  
 
}

Этот код сначала запрашивает у пользователя числа N и K, затем использует рекурсивную функцию generateStrings для генерации всех строк из нулей и единиц длины N, содержащих ровно K единиц. Все сгенерированные строки выводятся в лексикографическом порядке.

Надеюсь, это поможет! Если у вас есть какие-либо вопросы или нужна дополнительная помощь, пожалуйста, дайте мне знать.

Answer 2

 #include <iostream> 
#include <string> 
#include <vector> 
 
using namespace std; 
 
void generateStrings(int N, int K, int pos, int remainingOnes, string current, vector<string> &result) { 
    if (pos == N) { 
        if (remainingOnes == 0) { 
            result.push_back(current); 
        } 
        return; 
    } 
 
    int positionsLeft = N - pos; 
 
    if (positionsLeft - 1 >= remainingOnes) { 
        generateStrings(N, K, pos + 1, remainingOnes, current + "0", result); 
    } 
 
    if (remainingOnes > 0) { 
        generateStrings(N, K, pos + 1, remainingOnes - 1, current + "1", result); 
    } 
} 
 
int main() { 
    int N, K; 
    cin >> N >> K; 
    vector<string> result; 
    generateStrings(N, K, 0, K, "", result); 
    for (const string &s : result) { 
        cout << s << endl; 
    } 
    return 0; 
}

Answer 3

Да, проще всего генерировать рекурсивно. Но не так, как предложили нейросети (вариант нейросети ААС не обеспечивает лексикографический порядок, а в варианте нейросети resurce глубина рекурсии равна N, а все строки зачем-то объединяются в массив, тратя на это оперативную память).

 #include <iostream>

using namespace std;

void f(string &s, int cnt) {
  if (cnt <= 0) {
    cout << s << "\n";
    return;
  }
  for (int i = s.size() - cnt; i >= 0 && s[i] != '1'; --i) {
    s[i] = '1';
    f(s, cnt - 1);
    s[i] = '0';
  }
}

int main() {
  int n, k;
  cin >> n >> k;
  string s(n, '0');
  f(s, k);
}