C Recursividade. Comparar Caracteres De Duas Strings.

jcgs98 · 25 de novembro de 2020

Em 14/11/2020 às 12:40, arfneto disse:
Testou mesmo essa solução anes de marcar como tal?

Pois é. Você respondeu:

Para responder a si mesmo não se usa um forum. E não foi você que perguntou nesse caso: eu perguntei qual o sentido da afirmação

Você não precisa responder nem para mim nem para o forum, claro. Mas postar uma resposta que encontrou para si mesmo é curioso

A pergunta era "que tem a ver um for em uma função recursiva com o fato de ela ser recursiva ou não? Que significa a expressão "não vale" por exemplo?

E a sua solução

Muito bem. Parabéns. E já foi marcada como solução! É certo que foi marcada pelo próprio autor, você mesmo, mas está claro lá que é a solução.

E a solução resolve?

Curiosamente eu te mostrei um programa e uma função para testar isso e expliquei até porque usar. E você preferiu claro seguir seu caminho resoluto e que levou à solução final ótima e elegante.

No entanto rodando o mesmo programa que te mostrei e você poderia ter copiado se vê na tela:
A versao que "nao vale" segundo voce

        ==> 5 testes:

01/05  "azul" vs "aazz uull" retornou 8
02/05  "azul" vs "azul" retornou 4
03/05  "azul" vs "" retornou 0
04/05  "" vs "azul" retornou 0
05/05  "uma string" vs "uma strinG" retornou 9


A versao "Solucao" e "resposta" segundo voce

        ==> 5 testes:

01/05  "azul" vs "aazz uull" retornou 6
02/05  "azul" vs "azul" retornou 3
03/05  "azul" vs "" retornou 0
04/05  "" vs "azul" retornou 0
05/05  "uma string" vs "uma strinG" retornou 8
E os resultados não batem.

Você pode responder qual está correto apenas lendo acima ou rodando esse programa aqui abaixo:
#include <ctype.h>
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int     comparaString(const char*, const char*);
int     comparaString2(const char*, const char*);
int     comparaStringA(const char*, const char*);

void testaF(unsigned, const char* [][2],
    int(*)(const char*, const char*), const char*);

int main()
{
    const char* teste[][2] =
    {
        { "azul", "aazz uull" },
        { "azul", "azul" },
        { "azul", "" },
        { "", "azul" },
        { "uma string", "uma strinG" }
    };

    int n = sizeof(teste) / (2 * sizeof(char*));

    testaF(n, teste,
        comparaStringA,
        "A versao que \"nao vale\" segundo voce");


    testaF(n, teste,
        comparaString,
        "A versao \"Solucao\" e \"resposta\" segundo voce");

    return 0;
};


void        testaF(
    unsigned n, const char* teste[][2],
    int(*f)(char*, char*), const char* msg)
{
    if (msg != NULL)
        printf("\n\n%s\n\n\t==> %d testes:\n\n", msg, n);
    else
        printf("\n\n==> %d testes:\n\n", n);

    for (unsigned i = 0; i < n; i++)
    {
        printf("\
%02d/%02d  \"%s\" vs \"%s\" retornou %d\n",
1 + i, n, teste[i][0], teste[i][1],
f((char*)teste[i][0], (char*)teste[i][1]));
    }; // for()
};
Ou teste a "solução" digitando no teclado os valores um por um, do modo bem moderno.

Mas pode usar a função que eu postei no tópico #2 e o programa de teste que eu coloquei lá junto para te ajudar. Ela serve apara testar qualquer número de funções.

Ainda sobre a solução

O erro que cometeu é o clássico one-off e é o trivial para pegar quando

se testa mecanicamente

quando tem um patrão ou orientador rigoroso.

quanto se tem menos auto-confiança e acha que é melhor testar mais

Acredito que possa fazer funcionar ainda, mas é uma ideia mínima apoiada em uma "muleta" deixa na alínea (ii). O alvo do seu desafio é:

Desafio

Em português:

Desenvolver uma função recursiva que determine o número de caracteres em comum entre duas string s1 e s2

E tem a "colher de chá"

Em português:

ii. Se a mesma letra aparecer N vezes em uma certa string não será considerado um erro se sua solução acumular essa letra N vezes

E a restrição:

Em português:

Se sua solução for dividida em mais de uma função (de modo que a função principal, que resolve o problema proposto - chama outras funções auxiliares), todas as funções devem ser recursivas

Uma vez que funcione você terá feito o mínimo do mínimo.

Se ninguém resolveu antes de mim, por que não posso marcar a minha solução como solução. Se você tivesse resolvido eu marcaria a sua. Simples.

agora, Comunista.RJ disse:

Se ninguém resolveu antes de mim, por que não posso marcar a minha solução como solução. Se você tivesse resolvido eu marcaria a sua. Simples.

Pela enésima vez, a sua tem for. Não serve. Obrigado mesmo assim e até a próxima.

arfneto · 25 de novembro de 2020

O que você escreveu sequer funciona ... teste com o exemplo que te mostrei.

ter ou não ter um comando ou outro não define a função como recursiva ou não.

Se funcionasse, e não funciona, o que você tentou escrever é uma fração do enunciado, apoiada em uma concessão.

Bom que encontrou uma solução, a seu modo afinal. E está errada

jcgs98 · 25 de novembro de 2020

@arfneto Se não funciona no seu compilador... paciência. você querendo ou não está certa. Abraços.

arfneto · 25 de novembro de 2020

@Comunista.RJ um erro é um erro. A "solução" que está acima marcada como tal "come" a última letra da string. Usando o compilador de qualquer um

jcgs98 · 25 de novembro de 2020

@arfneto

String1...:
abcdefghija

String2...:
a

Existem 2 caracteres comuns entre as duas strings

--------------------------------
Process exited after 9.396 seconds with return value 0
Pressione qualquer tecla para continuar. . .

String1...:
a a a

String2...:
a

Existem 3 caracteres comuns entre as duas strings

--------------------------------
Process exited after 3.472 seconds with return value 0
Pressione qualquer tecla para continuar. . .

String1...:
bbb

String2...:
ab

Existem 3 caracteres comuns entre as duas strings

--------------------------------
Process exited after 6.962 seconds with return value 0
Pressione qualquer tecla para continuar. . .

agora, Comunista.RJ disse:

@arfneto

String1...:
abcdefghija

String2...:
a

Existem 2 caracteres comuns entre as duas strings

--------------------------------
Process exited after 9.396 seconds with return value 0
Pressione qualquer tecla para continuar. . .

String1...:
a a a

String2...:
a

Existem 3 caracteres comuns entre as duas strings

--------------------------------
Process exited after 3.472 seconds with return value 0
Pressione qualquer tecla para continuar. . .

String1...:
bbb

String2...:
ab

Existem 3 caracteres comuns entre as duas strings

--------------------------------
Process exited after 6.962 seconds with return value 0
Pressione qualquer tecla para continuar. . .

String1...:
bbb

String2...:
bab

Existem 6 caracteres comuns entre as duas strings

--------------------------------
Process exited after 2.625 seconds with return value 0
Pressione qualquer tecla para continuar. . .

2 minutos atrás, Comunista.RJ disse:

@arfneto

String1...:
abcdefghija

String2...:
a

Existem 2 caracteres comuns entre as duas strings

--------------------------------
Process exited after 9.396 seconds with return value 0
Pressione qualquer tecla para continuar. . .

String1...:
a a a

String2...:
a

Existem 3 caracteres comuns entre as duas strings

--------------------------------
Process exited after 3.472 seconds with return value 0
Pressione qualquer tecla para continuar. . .

String1...:
bbb

String2...:
ab

Existem 3 caracteres comuns entre as duas strings

--------------------------------
Process exited after 6.962 seconds with return value 0
Pressione qualquer tecla para continuar. . .

String1...:
bbb

String2...:
bab

Existem 6 caracteres comuns entre as duas strings

--------------------------------
Process exited after 2.625 seconds with return value 0
Pressione qualquer tecla para continuar. . .

String1...:
MATRIX

String2...:
MATRISX

Existem 6 caracteres comuns entre as duas strings

--------------------------------
Process exited after 9.389 seconds with return value 0
Pressione qualquer tecla para continuar. . .

arfneto · 25 de novembro de 2020

teste como eu te expliquei

jcgs98 · 25 de novembro de 2020

23 minutos atrás, arfneto disse:

teste como eu te expliquei

Eita!

Custa você admitir que não sabe?
Segue:

String1...:
azul

String2...:
aazz uull

Existem 8 caracteres comuns entre as duas strings

--------------------------------
Process exited after 17.12 seconds with return value 0
Pressione qualquer tecla para continuar. . .

4

0

String1...:
uma string

String2...:
uma strinG

Existem 9 caracteres comuns entre as duas strings

--------------------------------
Process exited after 14.53 seconds with return value 0
Pressione qualquer tecla para continuar. . .

Se você conseguir admitir que estou certo, pode me ajudar a não contar as repetições?

aaaa x aa retornar "1".

Pensei em pesquisar e retornar 1 ou 0 se achar.

Daí um "IF".

Se quiser continuar teimando, tudo bem.

arfneto · 25 de novembro de 2020

55 minutos atrás, Comunista.RJ disse:

Se você conseguir admitir que estou certo, pode me ajudar a não contar as repetições?

Uma discussão assim longa já não vai mais ajudar ninguém, porque imagino que as pessoas não tenham paciência de acompanhar esses argumentos, e cansei desse tópico. Eu tinha me esquecido do tanto que eu tentei te explicar muito do que está errado, e desisto. Vou resumir aqui de novo, uma última vez, e recomendo que seja ainda mais humilde e tente entender.

Veja como termina sua função comparaString() por exemplo:

int comparaString(char* str1, char* str2)
{
	if (!str1[0])
	{
		return 0;
	}

	return(comparaString2(str1[0], str2) + comparaString(++str1, str2));
	return (comparaString(++str1, str2));
}

Acha que esse segundo return vai ser executado alguma vez? Não, não vai. Sabe o que é unreachable code? É isso aí acima. Se você tem um patrão ou um professor, melhor não mostrar isso. No forum já mostrou.

Quanto ao primeiro return, o único que vai rodar na prática:

	return(comparaString2(str1[0], str2) + comparaString(++str1, str2));

Entenda que isso está ERRADO. Não é minha opinião. Isso é UB, undefined behavior, comportamento indefinido.

Pelo modo como programa acho que não tem experiência ainda para entender isso e então vou tentar te explicar:

O problema é que você usa str1 duas vezes como parâmetro de chamada para uma função. Na mesma linha., uma soma.

E em uma das vezes você altera o valor. A linguagem C não garante a ordem de execução dessa soma e pode ser que incremente antes ou depois da primeira chamada. Se incrementar antes vai passar o parâmetro alterado já na primeira chamada.

Isso quer dizer que dependendo da ordem de execução seu programa retorna 7, 8 ou 9. Retorna 8 apenas se mantiver a chamada a gets() apesar dos avisos do gcc e do passar dos anos. No Windows não vai aceitar gets() no compilador da Microsoft. E continua sendo UB.

Veja a mensagem do gcc 9.3 por exemplo, com -Wall que é o padrão em muitas escolas e empresas

Mais ainda, em gcc 9.3, Ubuntu, com gets()

Ao menos retornou 8

Mas a essência do problema é o undefined behavior, o uso de uma variável alterada no meio de uma expressão cuja ordem de avaliação não é garantida. E no meio de uma chamada a duas funções recursivas. Isso num ambiente profissional poderia te custar caro.

No forum não importa. Entendo que esse talvez não seja um erro ao alcance de um iniciante perceber e por isso estou escrevendo de novo a respeito. E de todo modo você não deve ter sequer lido os avisos sobre gets() na tela, exceto os que eu te dei, e parece que eu não tenho assim muito crédito, então fica aqui o aviso para ficar atento a isso no futuro.

Nesse compilador online retorna 9

Em gcc em Linux retorna em geral 9:

no windows

No SUSE Linux

Ou no Ubuntu

Mas no Windows com o compilador da Microsoft retorna 7

Isso é esperado, como eu disse: pode acontecer qualquer coisa.

Seu programa no geral não está assim bom.

fflush() não existe para fluxos de entrada em geral.
gets() é marcada como obsoleta há mais de vinte anos e alguns compiladores simplesmente não tem isso
tem dois #include obsoletos e fora do padrão e que sequer estão em uso.
tem dois return em seguida e isso é folclórico
tem uma expressão cujo comportamento é indefinido pelo padrão.

Por outro lado, compare com a saída do programa que te mostrei, e que tem a solução recursiva completa sem se apoiar naquela "deixa" do enunciado e funciona em qualquer plataforma...

Assim é. O código está no tópico.

Abaixo o código usado em todas as plataformas, o que você postou, com os 2 #include removidos e a chamada a gets() trocada por fgets()

Spoiler


#include <string.h>
#include <stdio.h>
#include <stdlib.h>

int comparaString2(char str1, char* str2);

int comparaString(char* str1, char* str2);

int main(void)
{
	int cont = 0;
	char str1[100], str2[100];
	fflush(stdin);
	printf("\nString1...:\n");
	fgets(str1, 100, stdin);
	fflush(stdin);
	printf("\nString2...:\n");
	fgets(str2, 100, stdin);
	cont = comparaString(str1, str2);
	printf("\nExistem %i caracteres comuns entre as duas strings\n", cont);
	return 0;
}

int comparaString(char* str1, char* str2)
{
	if (!str1[0])
	{
		return 0;
	}
	return(comparaString2(str1[0], str2) + comparaString(++str1, str2));
	return (comparaString(++str1, str2));
}

int comparaString2(char str1, char* str2)
{
	if (!str2[0])
	{
		return 0;
	}
	if (str2[0] == str1)
	{
		return (1 + comparaString2(str1, ++str2));
	}
	else
		return comparaString2(str1, ++str2);
}

jcgs98 · 26 de novembro de 2020

4 horas atrás, arfneto disse:
Uma discussão assim longa já não vai mais ajudar ninguém, porque imagino que as pessoas não tenham paciência de acompanhar esses argumentos, e cansei desse tópico. Eu tinha me esquecido do tanto que eu tentei te explicar muito do que está errado, e desisto. Vou resumir aqui de novo, uma última vez, e recomendo que seja ainda mais humilde e tente entender.

Veja como termina sua função comparaString() por exemplo:
int comparaString(char* str1, char* str2)
{
	if (!str1[0])
	{
		return 0;
	}

	return(comparaString2(str1[0], str2) + comparaString(++str1, str2));
	return (comparaString(++str1, str2));
}
Acha que esse segundo return vai ser executado alguma vez? Não, não vai. Sabe o que é unreachable code? É isso aí acima. Se você tem um patrão ou um professor, melhor não mostrar isso. No forum já mostrou.

Quanto ao primeiro return, o único que vai rodar na prática:
	return(comparaString2(str1[0], str2) + comparaString(++str1, str2));
Entenda que isso está ERRADO. Não é minha opinião. Isso é UB, undefined behavior, comportamento indefinido.

Pelo modo como programa acho que não tem experiência ainda para entender isso e então vou tentar te explicar:

O problema é que você usa str1 duas vezes como parâmetro de chamada para uma função. Na mesma linha., uma soma.

E em uma das vezes você altera o valor. A linguagem C não garante a ordem de execução dessa soma e pode ser que incremente antes ou depois da primeira chamada. Se incrementar antes vai passar o parâmetro alterado já na primeira chamada.

Isso quer dizer que dependendo da ordem de execução seu programa retorna 7, 8 ou 9. Retorna 8 apenas se mantiver a chamada a gets() apesar dos avisos do gcc e do passar dos anos. No Windows não vai aceitar gets() no compilador da Microsoft. E continua sendo UB.

Veja a mensagem do gcc 9.3 por exemplo, com -Wall que é o padrão em muitas escolas e empresas

Mais ainda, em gcc 9.3, Ubuntu, com gets()

Ao menos retornou 8

Mas a essência do problema é o undefined behavior, o uso de uma variável alterada no meio de uma expressão cuja ordem de avaliação não é garantida. E no meio de uma chamada a duas funções recursivas. Isso num ambiente profissional poderia te custar caro.

No forum não importa. Entendo que esse talvez não seja um erro ao alcance de um iniciante perceber e por isso estou escrevendo de novo a respeito. E de todo modo você não deve ter sequer lido os avisos sobre gets() na tela, exceto os que eu te dei, e parece que eu não tenho assim muito crédito, então fica aqui o aviso para ficar atento a isso no futuro.

Nesse compilador online retorna 9

Em gcc em Linux retorna em geral 9:

no windows

No SUSE Linux

Ou no Ubuntu

Mas no Windows com o compilador da Microsoft retorna 7

Isso é esperado, como eu disse: pode acontecer qualquer coisa.

Seu programa no geral não está assim bom.

fflush() não existe para fluxos de entrada em geral.

gets() é marcada como obsoleta há mais de vinte anos e alguns compiladores simplesmente não tem isso

tem dois #include obsoletos e fora do padrão e que sequer estão em uso.

tem dois return em seguida e isso é folclórico

tem uma expressão cujo comportamento é indefinido pelo padrão.

Por outro lado, compare com a saída do programa que te mostrei, e que tem a solução recursiva completa sem se apoiar naquela "deixa" do enunciado e funciona em qualquer plataforma...

Assim é. O código está no tópico.

Abaixo o código usado em todas as plataformas, o que você postou, com os 2 #include removidos e a chamada a gets() trocada por fgets()
Ocultar conteúdo
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

int comparaString2(char str1, char* str2);

int comparaString(char* str1, char* str2);

int main(void)
{
	int cont = 0;
	char str1[100], str2[100];
	fflush(stdin);
	printf("\nString1...:\n");
	fgets(str1, 100, stdin);
	fflush(stdin);
	printf("\nString2...:\n");
	fgets(str2, 100, stdin);
	cont = comparaString(str1, str2);
	printf("\nExistem %i caracteres comuns entre as duas strings\n", cont);
	return 0;
}

int comparaString(char* str1, char* str2)
{
	if (!str1[0])
	{
		return 0;
	}
	return(comparaString2(str1[0], str2) + comparaString(++str1, str2));
	return (comparaString(++str1, str2));
}

int comparaString2(char str1, char* str2)
{
	if (!str2[0])
	{
		return 0;
	}
	if (str2[0] == str1)
	{
		return (1 + comparaString2(str1, ++str2));
	}
	else
		return comparaString2(str1, ++str2);
}

O segundo return que botei na comparaString é desnecessário...

arfneto · 26 de novembro de 2020

1 hora atrás, Comunista.RJ disse:

O segundo return que botei na comparaString é desnecessário...

E um erro simples. Mas o primeiro return está mais errado. Espero que tenha entendido o problema.

5 horas atrás, arfneto disse:

return(comparaString2(str1[0], str2) + comparaString(++str1, str2));

Em qualquer linguagem isso está errado: não há como saber qual das operações vai ser executada primeiro, ++str1 pode acontecer antes de de chamar comparaString2() usando str1[0] como argumento e aí vai perder uma letra.

Espero que tenha entendido isso.

jcgs98 · 1 de dezembro de 2020

@arfneto Tá errado não, tá certo.

"não há como saber qual das operações vai ser executada primeiro" ???????????????????????????

Em 25/11/2020 às 20:29, arfneto disse:

Acha que esse segundo return vai ser executado alguma vez?

Leu a parte que escrevi que é desnecessário? Enfim...

Em 25/11/2020 às 20:29, arfneto disse:

Quanto ao primeiro return, o único que vai rodar na prática:

Sério???? Se você não me avisa! Caramba...

Em 25/11/2020 às 20:29, arfneto disse:

tem dois #include obsoletos e fora do padrão e que sequer estão em uso.

Sério??? Nossa!

Em 25/11/2020 às 20:29, arfneto disse:

O problema é que você usa str1 duas vezes como parâmetro de chamada para uma função. Na mesma linha., uma soma.

Acho que você deveria estudar mais aritmética de ponteiros.... talvez entenda o que foi feito.

Em 25/11/2020 às 20:29, arfneto disse:

Nesse compilador online retorna 9

Compilador online? Puts...

Em 25/11/2020 às 20:29, arfneto disse:

Por outro lado, compare com a saída do programa que te mostrei, e que tem a solução recursiva completa sem se apoiar naquela "deixa" do enunciado e funciona em qualquer plataforma...

É só admitir que não sabe...