24/04/2015, 10:51
int dfs(string s, int n, vector < string >&D, vector <int> &M, string i, int k, int modi){
if (D.size() == modi)
M[n] = M[n] + 1;
for(int j=0; j< D.size(); j++){
int cur = (k-1);
if( (s.substr(cur, D[j].size())==D[j]))
dfs(s, n, D, M, i + D[j], cur+D[j].size()+1,j+1); //ANCORA LA RICORSIONE QUINDI E' UNA MER.....INA
}
return M[n]; // Stampa OK il num di modi ma VIC mi mena perché fa pietà (faccina cry)
}
25/04/2015, 09:37
25/04/2015, 17:42
25/04/2015, 20:07
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int dfs(vector<string> &D, string P);
int main()
{
string X;
vector<string> P;
int N;//numero di primitive
cout << "Inserisci il numero di primitive: \n";
cin >> N;
string temp;
cout << "Inserisci le primitive (separate da uno spazio): \n";
for (int i = 0; i < N; i++){
cin >> temp;
P.push_back(temp);
}
cout << "Inserisci la stringa: \n";
cin >> X;
cout << "Numero: " << dfs(P, X) << endl;
}
int dfs(vector<string> &D, string P)
{
int const Ps = P.length();
vector<int> M(Ps+1, 0);
M[0] = 1;
for(int i=1; i<= Ps; ++i)
{
int const Ds = D.size();
for(int j=0; j < Ds; ++j)
{
int const Djs = D[j].length();
if(Djs <= i)
{
if(M[i - Djs] != 0)
{
int k = 0;
for(; (k < Djs)&&(D[j][k] == P[i-Djs+k]); ++k);
if(k == Djs)
M[i] += M[i - Djs];
}
}
}
}
return M[Ps];
}
25/04/2015, 22:58
vict85 ha scritto:Io non ho eliminato la ricorsione dalla tua, ho proposto un algoritmo che usa la memoization (o era la programmazione dinamica non ricordo bene la differenza)
26/04/2015, 15:17
26/04/2015, 15:54
27/04/2015, 08:57
27/04/2015, 09:16
27/04/2015, 11:21
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.
Powered by phpBB © phpBB Group - Privacy policy - Cookie privacy
phpBB Mobile / SEO by Artodia.