Witam serdecznie wszystkich!
Jestem wciąż początkującą osobą w C++, aczkolwiek znam już podstawy (zmienne, stale, pętle, wyrażenia warunkowe, tablice,wskaźniki w miarę ogarniam (tylko musiałbym je sobie powtórzyć ;) ), funkcje, zmienne tekstowe, zasięgi zmiennych itp.). Przygotowuję się do konkursu i próbuję powoli ogarniać różne algorytmy. Rozwiązywałem zadanie, które polegało na tym, by wypisać ilość możliwych kombinacji łańcucha znaków. Od razu skojarzyłem to z permutacjami i zacząłem pisać program, który korzysta ze wzoru zaprezentowanego na tym filmiku: (
).
Wyszło mi coś takiego (zaopatrzyłem wszystko w komentarze, by wyjaśnić moje pokrętne rozumowanie ;) ):
#include <iostream>
#include <string>
using namespace std;
int silnia(int dlu);
int main()
{
int i,j,dl,licznik=0,wynik=1,wynik2;
string wyraz;
cin>>wyraz; //wpisanie wyrazy, którego mamy obliczyć ilość różnych kombinacji
dl=wyraz.length(); //zapisanie dlugosci w zmiennej dl
for( i= 0; i < dl; i++) //rozpoczecie petli, która analizuje po kolei kazda litere wyrazu
{
if(wyraz[i] != '.') //sprawdzenie, czy dana literka nie byl juz zliczana
{
licznik++; //nadanie biezacej literce statusu, ze wystapila w wyrazie jeden raz
for( j=i+1; j<dl; j++) //rozpoczecie petli, ktora ma zadanie sprawdzic, czy w dalszej czesci wyrazu nie wystepuje ponownie biezaca literka
{
if(wyraz[j]==wyraz[i]) //w przypadku powtorzenia
{
licznik++; //dajemy o tym znac licznikowi
wyraz[j]='.';//oraz w miejsce literki wstawiamy '.', by nie musieć drugi raz analizować tej samej literki i uniknąć błędów
}
}
wynik=wynik*silnia(licznik); //nastepnie korzystujac ze wzoru !n / (!n1 * !n2 ...) obliczamy dzielnik mnozac po kolei !n1*!n2 przy poszczególnych obrotach petli
}
licznik=0; //zerujemy licznik powtorzen
}
wynik= silnia(dl)/wynik; //ocliczamy wynik ze wzoru !n / (!n1 * !n2 ...)
cout<<wynik<<endl; //podaejmy wynik
return 0;
}
/*************Funkcja obliczajaca Silnia****************************/
int silnia(int dlu)
{
int silnia=1;
for(int i = 2; i <= dlu; i++)
{
silnia*=i;
}
return silnia;
}
Wszystko w nim działa jak należy, ale niestety nie działa on w każdym przypadku (możliwe, że przy dłuższych łańcuchach znaków). Czy moje rozumowanie jest odpowiednie, czy może istnieje jakieś prostsze rozwiązanie? (mam na myśli przede wszystkim rozwiązanie oparte o możliwości początkującego programisty)
PS. Zastanawiam się, czy by nie zmienić funkcji obliczającą Silnię na wersje rekurencyjną, czy to by mogło coś przyspieszyć, czy wręcz przeciwnie.
PS2. Jeśli zauważycie, że mój kod przedstawia jakieś złe nawyki (dot. przejrzystości kodu lub dot. wydajności kodu), proszę mi je wytykać, bo im szybciej się o takowych złych praktykach dowiem, tym lepiej.