Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: backtracking pe cuvinte  (Citit de 1370 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
sabbath
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« : Februarie 27, 2012, 20:14:50 »

Buna

trebuie sa generez toate posibilitatile de aranjare a cuvintelor unui text dupa niste proprietati:
primul sa fie palindrom
ultimul sa aiba numarul de vocale mai mare decat nr de consoane
celelalte au nr de voc impar si numar de cons par
Cod:
#include <iostream>
#include<string.h>
//primul cuv sa fie palindromic
//cuv sa aiba fiecare numar par de consoane si nr impar de vocale
//ultimul sa aiba nr de vocale mai mare de cat numarul de consoane
using namespace std;
char s[1000], cuvinte[10][100], st[10], n;

void afisare(int k)
{
    for(int i=1;i<=k;i++)
    {
        cout<<cuvinte[st[k]]<<" ";
    }
    cout<<"*************8"<<endl;
}
void voc_cons(char x[100], int &v, int &c)
{
    int l = strlen(x);
    for(int i=0;i<l;i++)
    {
        if(strchr("aeiou", x[i]))
            v++;
        if(!(strchr("aeoiu", x[i])))
            c++;
    }
}
void citire()
{
    cin.getline(s, 1000);
    char *p = strtok(s, " ");
    while(p)
    {
        n++;
        strcpy(cuvinte[n], p);
        int l = strlen(p);
        cuvinte[n][l] = 0;
        p = strtok(NULL, " ");
    }
}


int pali(char x[100])
{
    if(strcmp(x, strrev(x)) == 0)
        return 1;
    return 0;
}

int valid(int k)
{
    for(int i=1;i<k;i++)
        if(st[k] == st[i])
            return 0;
    return 1;
}
int solutie(int k)
{
    if(k <3)
        return 0;
    if(!pali(cuvinte[st[1]]))
        return 0;
    for(int i=2;i<k;i++)
    {
        int v=0, c=0;
        voc_cons(cuvinte[st[i]], v, c);
        if(v%2 != 1 || c%2 != 0)
            return 0;
    }
    int v=0, c=0;
    voc_cons(cuvinte[st[k]], v, c);
    if(v<=c)
        return 0;
    return 1;

}

void back(int k)
{
    for(int i=1;i<=n;i++)
    {
        st[k] = i;
        cout<<cuvinte[st[k]]<<endl;
        if(valid(k))
        {
            if(solutie(k))
                afisare(k);
            back(k+1);
        }
    }
}

int main()
{
    citire();
    back(1);
    return 0;
}

Multumesc anticipat pentru indicatii.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines