C Otimizar este código - exercício quadrado perfeito

Jessé P. de Melo · 17 de maio de 2018

Boa noite. Estou estudando para programar em microcontroladores, esses aparelhos tem recursos bem limitados, ou seja quanto mais otimizado melhor.

Fiz o exercício:

Faça uma função para verificar se um numero é um quadrado perfeito. Um quadrado perfeito e um numero inteiro não negativo que pode ser expresso como o quadrado de outro numero inteiro. Ex: 1, 4, 9... (Definição mais completa).

Quero otimizar esse código.

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

int main(void){//2,3,5,7
    int num;
    int quadrado_perfeito(int x);

    printf("Digite um numero para saber se e um quadrado perfeito: ");
    scanf("%i",&num);
    quadrado_perfeito(num);
}
int quadrado_perfeito(int x){
   int exp_n2=0;
   int exp_n3=0;
   int exp_n5=0;
   int exp_n7=0;
   int teste1=0;
   int teste2=0;
   int teste3=0;
   int teste4=0;

    while(x>1){
        while (x%2==0){
            x=x/2;
            exp_n2++;
        }
        while (x%3==0){
            x=x/3;
            exp_n3++;
        }
        while (x%5==0){
            x=x/5;
            exp_n2++;
        }
        while (x%7==0){
            x=x/7;
            exp_n7++;
        }
    }
    if(exp_n2==0||exp_n2%2==0){
        teste1=1;
    }
    if(exp_n3==0||exp_n3%2==0){
        teste2=1;
    }
    if(exp_n5==0||exp_n5%2==0){
        teste3=1;
    }
    if(exp_n7==0||exp_n7%2==0){
        teste4=1;
    }

    if(teste1&&teste2&teste3&&teste4==1){
        printf("E' um quadrado perfeito");
    }
    else{
        printf("Nao e' um quadrado perfeito");
    }
}

.

Davi Silva Santos · 17 de maio de 2018

Tem como só fazer por inteiros e usando um algoritmo básico para achar raiz. Mas se quiser uma maneira rápida tenho esse código:

#include <stdio.h>
#include <math.h>

void is_square_num(unsigned int S)
{
	unsigned int tmp = sqrt(S);
    if (tmp*tmp == S)
        puts("É quadrado");
    else
        puts("Não é quadrado");
}

int main(void)
{
	unsigned int num, raiznum;
	puts("Digite número: ");
	scanf("%u", &num);
	is_square_num(num);
	return 0;
}

Lembrando que ele usa a biblioteca `math.h` então deve ser compilado com o parâmetro `-lm`.

isrnick · 17 de maio de 2018

@Davi Silva Santos Sim, mas acho que o desafio é fazer sem usar a biblioteca math.h .

@Jessé P. de Melo O método de fatoração limita ao conjunto de números primos usados para verificar, e vai fazer sua função parar de funcionar conforme o número cresce.

A propriedade de quadrados perfeitos que uso para fazer uma função simples que funciona para qualquer número, é a de que todo quadrado perfeito é uma soma de números ímpares sequenciais, começando em 1.

Veja:

1² = 1 = 1

2² = 1 + 3 = 4

3² = 1 + 3 + 5 = 9

4² = 1 + 3 + 5 + 7 = 16

5² = 1 + 3 + 5 + 7 + 9 = 25

Tente fazer essa função usando essa propriedade.

(A função não é muito eficiente, pois demora mais tempo calculando quanto maior for o número, mas funciona para qualquer número. Existem outros métodos mais eficientes, mas são mais complexos, e não é necessário para o que o exercício pede.)

Jessé P. de Melo · 17 de maio de 2018

@isrnick Esse método parece bom. Eu pensei que ao fazer a verificação com números 2,3,5,7 seria o suficiente por que todos os que vem apos desses na fatoração poderiam ser divididos entre esses principais, se der você poderia ser mais claro ? porque fiz testes com o numero 81, depois (81*81)=6561 e depois com (6561*6561)=43046721 deram certo, no entanto o 43046720 ficou travado consumindo processador.

Mas vejo isso só amanha, estou desde as 12:00 estudando.

isrnick · 17 de maio de 2018

@Jessé P. de Melo Quaisquer números que contenham números primos que não sejam 2, 3, 5 e 7 como divisores falhariam no seu programa.

Quadrados perfeitos de outros números primos são os mais fáceis de verificar, teste 121 por exemplo, que é 11². Seu programa vai ficar num loop infinito.

O mesmo ocorre com 26 = 2 * 13.

Jessé P. de Melo · 18 de maio de 2018

Desculpe a demora. Disse que começaria estudar as 12:00 mas comecei depois da 13:00, alem do mais por algum motivo que eu não lembro qual eu queria desenvolver um bloco só para números compostos e números primos. Enfim só aumentei isso na função para realizar cálculos para números primos:

int quadrado_perfeito(int x){
int soma_impares=1;
while(soma_impares<x){
        soma_impares+=2;
    }
    if(soma_impares==x){
        printf("E' quadrado perfeito");
    }
}

O código completo ficou:

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

int main(void){//2,3,5,7
    int num;
    int quadrado_perfeito(int x);

    printf("Digite um numero para saber se e um quadrado perfeito: ");
    scanf("%i",&num);
    quadrado_perfeito(num);
}
int quadrado_perfeito(int x){
    int soma_impares=1;
    int exp_n2=0;
    int exp_n3=0;
    int exp_n5=0;
    int exp_n7=0;
    int teste1=0;
    int teste2=0;
    int teste3=0;
    int teste4=0;

    while(soma_impares<x){
        soma_impares+=2;
    }
    if(soma_impares==x){
        printf("E' quadrado perfeito");
        exit(0);
    }

    while(x>1){
        while (x%2==0){
            x=x/2;
            exp_n2++;
        }
        while (x%3==0){
            x=x/3;
            exp_n3++;
        }
        while (x%5==0){
            x=x/5;
            exp_n2++;
        }
        while (x%7==0){
            x=x/7;
            exp_n7++;
        }
    }
    if(exp_n2==0||exp_n2%2==0){
        teste1=1;
    }
    if(exp_n3==0||exp_n3%2==0){
        teste2=1;
    }
    if(exp_n5==0||exp_n5%2==0){
        teste3=1;
    }
    if(exp_n7==0||exp_n7%2==0){
        teste4=1;
    }

    if(teste1&&teste2&teste3&&teste4==1){
        printf("E' um quadrado perfeito");
    }
    else{
        printf("Nao e' um quadrado perfeito");
    }
}

isrnick · 18 de maio de 2018

Esse código não está somando os ímpares, está apenas obtendo números ímpares:

int quadrado_perfeito(int x){
int soma_impares=1;
while(soma_impares<x){
        soma_impares+=2;
    }
    if(soma_impares==x){
        printf("E' quadrado perfeito");
    }
}

O que resulta que seu código vai responder que qualquer número ímpar é um quadrado perfeito.

E use "return 0;" no lugar de onde você colocou "exit(0);", a função exit() serve para finalizar o programa imediatamente, enquanto return retorna a execução do programa para o escopo que chamou esta função.

Jessé P. de Melo · 18 de maio de 2018

Depois de muita luta terminei.

Estava quase desistindo do exercício, fiquei gastando tempo e paciência tentando readequar meu código a solução proposta.

21 horas atrás, isrnick disse:

A propriedade de quadrados perfeitos que uso para fazer uma função simples que funciona para qualquer número, é a de que todo quadrado perfeito é uma soma de números ímpares sequenciais, começando em 1.

Veja:

1² = 1 = 1

2² = 1 + 3 = 4

3² = 1 + 3 + 5 = 9

4² = 1 + 3 + 5 + 7 = 16

5² = 1 + 3 + 5 + 7 + 9 = 25

Sendo que era muito mais simples começar a função do zero. Aparentemente esta funcionando e ficou assim:

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

int main(void){//2,3,5,7
    int num;
    void quadrado_perfeito(int x);

    printf("Digite um numero para saber se e um quadrado perfeito: ");
    scanf("%i",&num);
    quadrado_perfeito(num);
}
void quadrado_perfeito(int x){
    int n1=1;
    int n_total=1;
    int valida=0;

    while(n1<x){
        n1+=2;
        n_total=n_total+n1;
        if (n_total==x){
            valida=1;
        }
    }
    if (valida==1){
        printf("E' quadrado perfeito");
    }
    else{
        printf("Nao e' quadrado perfeito");
    }
}

isrnick · 18 de maio de 2018

A lógica está correta, agora só está errando em 2 casos, 0 e 1 são quadrados perfeitos, mas seu programa responde que não são, o motivo é que que seu programa começa testando a partir do número 4.

Vou fazer algumas mudanças na sua função e comentar o que fiz:

void quadrado_perfeito(int x){
    int n1=1;
    int n_total=1;
    //Não precisaremos dessa variável de validação
    //int valida=0;
    
    //Queremos comparar o total com x, não os número ímpares:
    //while(n1<x){
    while(n_total < x){
        n1+=2;
        n_total=n_total+n1;
        
        //Não é necessário checar dentro do while e usar
        //uma variável para verificar, pois podemos comparar
        //n_total com x após o ciclo, e já imprimir a mensagem
        //if (n_total==x){
        //    valida=1;
        //}
    }
    
    //Retirei este if:
    //if (valida==1){
    //Pois podemos comparar n_total com x aqui diretamente,
    //e já adicionei para também checar o caso específico do 0
    //assim todas as possibilidades estão cobertas:
    if (x == n_total || x == 0){ 
        printf("E' quadrado perfeito");
    }
    else{
        printf("Nao e' quadrado perfeito");
    }
}

Lembre-se também de colocar o return 0; na última linha do main(), pois o main() uma função do tipo int, logo espera-se que retorne um valor inteiro e finalizar a função (quando o main() retorna 0 está indicando para sistema operacional que o programa foi concluído corretamente, e retorna algo diferente de 0 se ocorrer um erro durante a execução).