Witam!
Mam problem z pewnym zadaniem, które musi być wykonane rekurencyjnie. Co to jest rekurencja i jak jej używać dokładnie wiem ale w tym przypadku wszystkie moje wysiłki zawiodły, dlatego też proszę Was o pomoc i wskazanie błędu w poniższym kodzie. Pełna treść zadania:
Dla danego łańcucha znaków input długości n, chcemy wypisać każdy kombinację w łańcuch u
danej długości k <= n na wyjście konsoli. Na przykład, jeżeli input jest równy abcd i k = 3, to program
wypisze do konsoli (kolejność wierszy jest nieważna):
abc
abd
acd
bcd
Piszemy taki program lancuchy, gdzie input i k są czytane wtedy, gdy program jest
uruchamiany. To znaczy, że użytkownik może np. napisać w konsoli:
> ./lancuchy abcd 3
Zadanie. Proszę zdefiniować rekurencyjną funkcję print poniżej, gdzie **mamy** zawiera
pierwsze litery naszego łańcuchu znaków, **potem** zawiera część danego łańcuchu, której
jeszcze można użyć, i **i** liczy, ile znaki jeszcze można dodać do mamy.
#include <iostream>
#include <string>
#include <stdlib.h> /* atoi */
using namespace std;
void print(string mamy, string potem, unsigned int i) {
// tutaj dodać linijki, używając rekurencji
}
int main(int argc, char **argv)
{
if ( argc<3 )
return 1; // za mało argumentów
std::string input = argv[1];
unsigned int k = atoi (argv[2]); // ASCII to int
if ( k > input.length() )
return 1; // k za duży
print ("", input, k );
}
Moja próba poradzenia sobie z problemem:
#include "stdafx.h"
#include <iostream>
#include <string>
void print(std::string mamy, std::string potem, unsigned int i);
int main(int argc, char **argv)
{
if (argc < 3)
{
return 1;
}
std::string input = argv[1];
unsigned int k = atoi(argv[2]);
if (k > input.length())
{
return 1;
}
print("", input, k);
return 0;
}
void print(std::string mamy, std::string potem, unsigned int i)
{
std::string left_branch(potem.begin(), potem.end());
std::string right_branch(potem.begin() + 1, potem.end());
std::string temp;
if (i != 0)
{
potem = left_branch;
mamy += potem[0];
potem.erase(0, 1);
print(mamy, potem, i - 1);
}
else
{
std::cout << mamy << std::endl;
return;
}
if (i != 0)
{
potem = right_branch;
mamy += potem[0];
potem.erase(0, 1);
print(mamy, potem, i - 1);
}
else
{
std::cout << mamy << std::endl;
return;
}
}