Algoritmus pro substituci – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Algoritmus pro substituci – C / C++ – Fórum – Programujte.comAlgoritmus pro substituci – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Sprinter
~ Anonymní uživatel
102 příspěvků
17. 1. 2013   #1
-
0
-

Ahoj,

prosím o pomoc - potřeboval bych vymyslet s jednou funkcí v jazyku C. Jedná se v podstatě o algoritmus představující substituci.

Mám buffer, který má například tyto prvky: {S:aS S:a}

Já potřebuji provést substituci na {S:aA A:S A:@} (S se přepíše na A, tudíž v dalším řádku je A = S, v dalším řádku se A nemá na co přepsat, tak se tam dá symbol @)

Příklady substitucí:

{A:bxc A:yc A:bxzd A:yzd} -> {A:bxB A:yC B:c B:zd C:c C:zd}

{A:aB A:aCB} -> {A:aX A:bBB X:B X:CB}

{X:a X:abCa C:c C:cBC} -> {X:aD D:@ D:bCa C:cF F:@ F:BC}

Co se týče písmenek, které mají nahradit původní, je na ně pouze požadavek, aby byla velká a nebyla stejná jako ty které už jsou použita.

Děkuji

Nahlásit jako SPAM
IP: 147.228.209.–
Reklama
Reklama
Sprinter
~ Anonymní uživatel
102 příspěvků
19. 1. 2013   #2
-
0
-

Tak už sem něco vyřešil, zasekl jsem se ale u cyklu, který má porovnávat slova.

Mám například tyto slova {A:bxc A:yc A:bxzd A:yzd}. Jedná se o výběr slov, která mají stejný znak na první a třetí pozici.

No a cyklus by měl umět vytisknout v každým kroku slova, která jsou shodná na třetí až n-té pozici (a vypsat, index, kam až jsou prvky shodné).

1. krok = A:bxc A:bxzd (shoda: bx = až k čtvrté pozici)

2. krok = A:yc A:yzd (shoda: y = až ke třetí pozici)

Pokud by nastal případ, že slova by byla tyto {A:a A:abc A:abx}, tak by krok měl vypadat:

1. krok = A:a A:abc A:abx (shoda: a = až ke třetí pozici)

Zatím mám udělané procházení mezi slovy.. ale nevím jak udělat to porovnávání "do N"

int i;
	char temp_buffer [strlen(buffer)+1];
	char working_buffer [strlen(buffer)+1];
	strcpy(temp_buffer, buffer);
	strcpy(working_buffer, buffer);
	for (token_b = strtok_r(temp_buffer, " ", &next_token_b); token_b; token_b = strtok_r(NULL, " ", &next_token_b))
	{
		for (token_c = strtok_r(working_buffer, " ", &next_token_c); token_c; token_c = strtok_r(NULL, " ", &next_token_c))
		{
			if (token_b[2] == token_c[2])
			{
				printf("TOken {%s}\n", token_b);
			}
		}	
	}
Nahlásit jako SPAM
IP: 78.102.208.–
zlz
~ Anonymní uživatel
634 příspěvků
20. 1. 2013   #3
-
0
-

To "do N" bude další cyklus. Nevím, jestli to bude dělat přesně to, co chceš, ale zhruba takhle:

int N = ?;

for (token_b...
{
    for (token_c...
    {
        int shoda = 0;
        for (int i = 2/*0*/; i < N-1 && token_b[i] && token_c[i] && token_b[i] == token_c[i]; i++)
        {
            shoda = i;
        }
        if (shoda > 2)
        {
            printf("{%s}{%s}{%d}\n", token_b, token_c, shoda);
        }
    }
}
Nahlásit jako SPAM
IP: 80.188.216.–
Sprinter
~ Anonymní uživatel
102 příspěvků
20. 1. 2013   #4
-
0
-

#3 zlz
A k čemu je tam to N? Nepochopil jsem jakou hodnotu mám za něj dosadit..

Nahlásit jako SPAM
IP: 147.228.209.–
Sprinter
~ Anonymní uživatel
102 příspěvků
20. 1. 2013   #5
-
0
-

#4 Sprinter
Jo jasný, délka slova :-)

Nahlásit jako SPAM
IP: 147.228.209.–
zlz
~ Anonymní uživatel
634 příspěvků
20. 1. 2013   #6
-
0
-

Já nevím, ty jsi psal o nějakém N  

Nahlásit jako SPAM
IP: 80.188.216.–
Sprinter
~ Anonymní uživatel
102 příspěvků
20. 1. 2013   #7
-
0
-

No myslel jsem jako procházení slovem po znacích tak dlouho, dokud jsou znaky stejné.

Pro vstup: {A:bxc A:yc A:bxzd A:yzd} by to tedy mělo vytisknout:

{A:bxc}{A:bxzd}{4}

{A:yc}{A:yzd}{3}

Momentálně to vypisuje toto:

S tím, že kód jsem upravil o ten for cyklus s podmínkou

int N;
char temp_buffer [strlen(buffer)+1];
char working_buffer [strlen(buffer)+1];
strcpy(temp_buffer, buffer);
strcpy(working_buffer, buffer);
for (token_b = strtok_r(temp_buffer, " ", &next_token_b); token_b; token_b = strtok_r(NULL, " ", &next_token_b))
{
	N = strlen(token_b);
	for (token_c = strtok_r(working_buffer, " ", &next_token_c); token_c; token_c = strtok_r(NULL, " ", &next_token_c))
	{
		int shoda = 0;
		for (int i = 2/*0*/; i < N-1 && token_b[i] && token_c[i] && token_b[i] == token_c[i]; i++)
		{
			shoda = i;
		}
		if (shoda > 2)
		{
			printf("{%s}{%s}{%d}\n", token_b, token_c, shoda);
		}
	}	
}
Nahlásit jako SPAM
IP: 147.228.209.–
zlz
~ Anonymní uživatel
634 příspěvků
20. 1. 2013   #8
-
0
-
  • test konce tokenů tam je, to N nepotřebuješ
  • strtok vrací ukazatel uvnitř původního řetězce, takže do něj taky vkládá ukončovač tokenu
  • shoda je poslední shodný index - počítaný od 0 - při výpisu přičti 1
  • testuje se všechno se vším, asi tam budeš chtít přidat ještě nějakou logiku, co s čím testovat. Např. netestovat token se sebou samým (pokud tam nebudou duplicity, tak stačí porovnat obsah), nebo já nevím co...
for (token_b...
{
    strcpy(working_buffer, buffer);
    for (token_c...
    {
        if (!strcmp(token_b, token_c))
            continue;

        int shoda = 0;
        for (int i = 2/*0*/; token_b[i] && token_c[i] && token_b[i] == token_c[i]; i++)
        {
            shoda = i;
        }
        if (shoda >= 2)
        {
            printf("{%s}{%s}{%d}\n", token_b, token_c, shoda + 1);
        }
    }
}
{A:bxc}{A:bxzd}{4}
{A:yc}{A:yzd}{3}
{A:bxzd}{A:bxc}{4}
{A:yzd}{A:yc}{3}

Nahlásit jako SPAM
IP: 80.188.216.–
Sprinter
~ Anonymní uživatel
102 příspěvků
20. 1. 2013   #9
-
0
-

#8 zlz
Jojo děkuju. To testování všechno se vším bych mohl udělat tak, že bych ty shodný ukládal do pomocného pole a pak prorovnával obsah...

Akorát teď když testuju ten kód, tak vypisuje jen:

{A:bxc}{A:bxzd}{4}

{A:bxzd}{A:bxc}{4}

Něvíte, kde by mohla být chyba?

Nahlásit jako SPAM
IP: 147.228.209.–
zlz
~ Anonymní uživatel
634 příspěvků
20. 1. 2013   #10
-
0
-

To nevím. Nemáš tam něco jinak? Třeba to >= 2 ?

A tykej...

Nahlásit jako SPAM
IP: 80.188.216.–
Sprinter
~ Anonymní uživatel
102 příspěvků
20. 1. 2013   #11
-
0
-

#10 zlz
Ok :-) No kód jsem zkopíroval, takže by to mělo být stejné.

Buffer = {A:bxc A:yc A:bxzd A:yzd}

char temp_buffer [strlen(buffer)+1];
	char working_buffer [strlen(buffer)+1];
	strcpy(temp_buffer, buffer);
	strcpy(working_buffer, buffer);
	for (token_b = strtok_r(temp_buffer, " ", &next_token_b); token_b; token_b = strtok_r(NULL, " ", &next_token_b))
	{
		for (token_c = strtok_r(working_buffer, " ", &next_token_c); token_c; token_c = strtok_r(NULL, " ", &next_token_c))
		{
			if (!strcmp(token_b, token_c))
			continue;

			int shoda = 0;
			for (int i = 2/*0*/; token_b[i] && token_c[i] && token_b[i] == token_c[i]; i++)
			{
				shoda = i;
			}
			if (shoda >= 2)
			{
				printf("{%s}{%s}{%d}\n", token_b, token_c, shoda + 1);
			}
		}	
	}
Nahlásit jako SPAM
IP: 147.228.209.–
Sprinter
~ Anonymní uživatel
102 příspěvků
21. 1. 2013   #12
-
0
-

Tak jsem to nakonec udělal takto:

int accord;
int last;
int length = strlen(buffer)+1;
int shift = 0;
bool computation;
char temp_buffer [length];
char help [length];
char used_rules [length];
	
help[0] = '\0';
used_rules[0] = '\0';
strcpy(temp_buffer, buffer);
for (token_b = strtok_r(temp_buffer, " ", &next_token_b); token_b; token_b = strtok_r(NULL, " ", &next_token_b))
{		
	char working_buffer [length];
	strcpy(working_buffer, buffer);
	for (token_c = strtok_r(working_buffer, " ", &next_token_c); token_c; token_c = strtok_r(NULL, " ", &next_token_c))
	{
		if (strstr(used_rules ,token_b)) computation = false;
		else
		{
			accord = 0;
			for (int i = 2; token_b[i] && token_c[i] && token_b[i] == token_c[i]; i++)
			{
				accord = i;
			}	
			if (strlen(help) == 0)
			{
				strcpy(help, token_b);
				strcat(help, " ");
			}
			if (accord >= 2 && !strstr(help, token_c))
			{
				strcat(help, token_c);
				strcat(help, " ");
				last = accord;
			}
			computation = true;
			
		}
	}
	strcat(used_rules, help);
	if (computation == true)
	{
		printf("Vysledek: {%s}{%i}{%c}\n", help, last, elements[shift]);
		shift++;
	}
	help[0] = '\0';
}

Potřeboval jsem ještě aby mi to v jednom kroce vypsalo všechny shodné slova (takže třeba i tři - ne jen vždy dvě)..

Nahlásit jako SPAM
IP: 147.228.209.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 81 hostů

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý