Pomógłby ktoś z takim zadaniem z rekurencji? Naprawdę już nie mam pomysłu..

Question

Pewien algorytm rekurencyjny działa w następujący sposób: - wstaw literę a - w kolejnych krokach przestaw litery pierwszą z ostatnią i dopisz na końcu kolejną literę alfabetu - w przypadku wyczerpania liter alfabetu (małe litery) rozpocznij od początku alfabetu. Rozwiązanie dla podanego n zapisz w pliku alfabet.txt.

 

Przykładowe rozwiązania: 

n
0	a
1	ab
2	bac
3	cabd
4	dabce

Answer 1

Drobiazg...

#include <iostream>
#include <utility>
#include <string>

void f(int n, std::string& s)
{
    if (n > 0)
    {
        std::swap(s.front(), s.back());
        s.push_back(s.front() < 'z' ? s.front() + 1 : 'a');
        f(n - 1, s);
    }
}

std::string f(int n)
{
    std::string s = "a";
    f(n, s);
    return s;
}

int main()
{
    std::cout << f(4) << '\n';
}

To rozwiązanie zakłada, że litery w zestawie znaków są po kolei i bez żadnych przerw, co nie zawsze jest prawdą.

Answer 2

rekurencja.cpp

//https://forum.pasja-informatyki.pl/399943/pomoglby-ktos-z-takim-zadaniem-z-rekurencji-naprawde-juz-nie-mam-pomyslu

#include <iostream>
#include <vector>
#include <cstdlib>
#include <stdio.h>
using namespace std;

void generate(vector<char> *v, int alphabetIndex, int reqiredLength){
	
	for(vector<char>::const_iterator i = v->begin(); i != v->end(); ++i){
		printf("%c", *i);
	}
	printf("\n");
	
	if(alphabetIndex + 'a' > 'z'){
		alphabetIndex = 0;
	}
	
	char tmp = v->at(0);
	v->at(0) =v->at(v->size()-1);
	v->at(v->size()-1) = tmp;
	
	v->push_back(alphabetIndex + 'a');
	
	if(v->size() < reqiredLength){
		generate(v, alphabetIndex+1, reqiredLength);
	}
	
}

int main(int argc, char *argv[]){
	
	int reqiredLength = atoi(argv[1]);
	
	if(reqiredLength <= 0){
		printf("Podaj liczbę naturalną dodatnią.");
		return 0;
	}

	vector<char> *v = new vector<char>();
	v->push_back('a');
	generate(v, 1, reqiredLength);
	
	return 0;
	
}

kompilacja: g++ rekurencja.cpp -o rekurencja

przykładowe wykonanie: ./rekurencja 10 > wynik