• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

djthyrax

Preparação para CPAS

42 mensagens neste tópico

É suposto dar o \n final no output para o CPAS?

Fiz assim o 1o exercício de 2006:

#include <stdio.h>

int power(int base, int exp){
int temp = 1;
for(; exp > 0; exp--) temp *= base;
return temp;
}

int main(){
char buffer[5];	
scanf("%s", &buffer);

int original = 0,
	sum = 0,
	i = -1,
	j;

while(buffer[++i] != '\0')
	original = original*10+((int)buffer[i] -48);

for(j = i-1; j > -1; j--)
	sum += power(((int)buffer[j])-48, i);

if(sum == original)
	printf("SIM");
else printf("NAO");
return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É suposto dar o \n final no output para o CPAS?

Sim. Que queres que veja? Eu só tive a fazer os de 2007.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em relação á resolução do problema 1 do CPAS 2006....

Tu usas-te um vector de caracteres.... Eu resolvi de maneira diferente e penso que seja mais rápida...

Código-fonte:

#include <iostream>
using namespace std;

bool amstrong(int x)
{
     int tmp1=0,
         tmp2=x;
     while ((tmp2%10) || (tmp2%100))
     {
           tmp1+=((tmp2%10)*(tmp2%10)*(tmp2%10));
           tmp2=tmp2/10;
     } 
     if (x==tmp1) return true; else return false;
}

int main()
{
    int x;
    cin >> x;
    (amstrong(x))?cout <<"SIM":cout << "NAO";
    return 0;
}

Usei o método de divisão finita.

Qual dos dois é mais rápido???

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu não vi o problema. Mas

while ((tmp2%10) || (tmp2%100))

é equivalente a

while(tmp2%10)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu não vi o problema. Mas

while ((tmp2%10) || (tmp2%100))

é equivalente a

while(tmp2%10)

Considera o número de armstrong 407  :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Vamos ver o numero de armstrong 407.

Se usasse-mos só tmp2%10, o que ia acontece é que quando o ciclo chegasse ao 2º numero, o zero, o ciclo parava!

Desta forma, verificamos se é possivel extrair o proximo número (tmp2%100), desta forma o zero é interpretado.

No intervalo 0 e 1000 so existem 5 numeros de armstrong:

Armstrong number 1: 0

Armstrong number 2: 1

Armstrong number 3: 153

Armstrong number 4: 370

Armstrong number 5: 371

Armstrong number 6: 407

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

a%b não é: a mod b? aka resto da divisão inteira?

Se resto da divisão inteira por 100 = 0 então resto da divisão inteira por 10 = 0.

Enganei-me. Queria dizer que era equivalente a

while(tmp2%100)

não percebi essa dos números de armstrong

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

não percebi essa dos números de armstrong

Vê o exercício 1 da edição de 2006 do CPAS que o Warrior anexou a um post dele ali atrás.
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Vê o exercício 1 da edição de 2006 do CPAS que o Warrior anexou a um post dele ali atrás.

Mas isso não muda o facto de que:

(tmp2%10 || tmp2%100) é equivalente a (tmp2%100)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pedi ali ao HecKel para fazer split, não estranhem :D

Aqui vai a minha solução para o exercício 2 do CPAS 2006:

#include <stdio.h>

int is_prime(int number, int limit){
for(; limit > 1; limit-=2)
	if(number % limit == 0){
		return 0;
	}
return 1;
}

int main(){
char buffer[5];
scanf("%s", &buffer);

int original = 0,
	limit = 31, // = sqrt(1000), e 32 é múltiplo de 2, logo é excluído.
	i = -1;

while(buffer[++i] != '\0')
	original = original*10+((int)buffer[i] -48);

if(is_prime(original, limit) == 0){
	printf("NAO");
	return 0;
}

original = 0;
while(--i > -1)
	original = original*10+((int)buffer[i] -48);

if(is_prime(original, limit) == 0){
	printf("NAO");
	return 0;
}	

printf("SIM");
return 0;
}

Eu sei que não está muito eficiente, mas não tava com paciência para mais :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Electron++: considera o número 1000. Essa tua verificação não serve. (não estou a ver o enunciado logo não sei os limites)

O que tu queres fazer é while (tmp2)  { ... }

Basicamente, tu fazes o ciclo enquanto tmp2 > 0.

Quanto à solução do djthyrax, não vejo a necessidade de ler tudo para um buffer e converter.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Quanto à solução do djthyrax, não vejo a necessidade de ler tudo para um buffer e converter.

Como farias então? (E estás a falar de qual problema?)
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nos dois problemas. Em vez de leres para uma string e converter para inteiro, lês logo como inteiro.

scanf("%d",&original); pode substituir essa leitura para um buffer e a conversão numa única linha. Alem que é bastante mais eficiente.

Isto se estiveres a usar C, que é o que parece uma vez que usas scanf.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

djthyrax vais participar no CPAS ? Qual é o nome da tua escola e equipa?

Eu sou capaz de aparecer lá no dia do concurso, talvez faça parte dos problem setters :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

djthyrax vais participar no CPAS ? Qual é o nome da tua escola e equipa?

Eu sou capaz de aparecer lá no dia do concurso, talvez faça parte dos problem setters :D

Estou a pensar nisso, tenho é de cravar a minha prof de FQ, que já cravei para as ONI. :)

Nos dois problemas. Em vez de leres para uma string e converter para inteiro, lês logo como inteiro.

scanf("%d",&original); pode substituir essa leitura para um buffer e a conversão numa única linha. Alem que é bastante mais eficiente.

Isto se estiveres a usar C, que é o que parece uma vez que usas scanf.

Mas depois como é que passo, por exemplo, 407 para 704? Isso é que me lixa. :)
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas isso não muda o facto de que:

(tmp2%10 || tmp2%100) é equivalente a (tmp2%100)

Nisso tens razão!

Por acaso no while, o warrior consegui simplificar mais a coisa, usando o while(tmp2)

Nota:

É de salientar que o enunciado do problema 1 do CPAS 2006 está mal formulado!

Um numero de armstrong é aquele que é igual á soma de todos os elementos, sendo que cada elemente é elevado ao numero de elementos do numero.

Exemplo:

153=1^3+5^3+3^3

1=1^1

5=5^1

Segundo o CPAS 2006, seria

2!=2^3=8

mas deveria ser

2=2^1

Logo o código que eu apresentei não se adapta de forma universal so mesmo a este programa.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema do CPAS está simplificado para que vocês apenas tenham que testar com o expoente 3 e não com vários (dispensa a utilização da função pow() por exemplo).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Estou a pensar nisso, tenho é de cravar a minha prof de FQ, que já cravei para as ONI. :)

Tu e eu. 1º dia de aulas: "Stora, posso usá-la como Prof. Responsável para dois concursos de informática?" :D

Mas depois como é que passo, por exemplo, 407 para 704? Isso é que me lixa. :)

Fiz 1 da USACO das capicuas e recebia-a como inteiro e invertia, mas não me lembro, nem estou neste momento em Linux.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É simples:

número  = 704 = 70 * 10 + 4

invertido= 0

número  = 70 = 7 * 10

invertido= 4

número  = 7 = 0 * 10 + 7

invertido= 4 * 10 + 0

...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

eletron, se quiseres o desafio, resolve o problema B da final das ONI do ano passado - http://www.dcc.fc.up.pt/oni/problemas/2007/final/probB.html

É para resolver o problema genérico que falas.

A solução tem de ser bastante eficiente. Coloca aqui a tua resolução para discussão :)

Assim que tiver uns minutitos vou resolver esse exercício, talvez o faço ainda hoje  :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Para tirar a duvida ao djthyrax e ao Tharis...

Pensem numa conversão de um numero decimal para binário....

Temos que fazer uma série de divisões até chegar ao fim. E á medida que fazemos essas divisões vamos pegar nos resultados e adicionar ao resultado final.

Exemplo:

#include <iostream>

using namespace std;

int main()
{
    int numero,
         a;
    cin >> numero;
    
    while(numero)
    {
                 a=a*10+(numero%10);
                 numero=numero/10;    
    }
    
    cout << a;
    
}

So para não terem duvidas na variável a.

Vamo usar o numero 120

a começa com zero

Resto de 120 por 10 = 0

a=0*10+0

Resto de 12 por 10=2

a=0*10+2

a=2

Testo de 1 por 10=1

a=2*10+1

a=21

E assim invertemos o numero 120 para 21, o zero desta valor não conta, por isso mesmo escolhi este valor de proposito.  :)

Isto claro usando um método matemático também podemos criar um vector de caracteres e comparar os elementos desse vector com um for!

#include <iostream>

using namespace std;

int main()
{
    char numero[20];
    cin>>numero;
    for(int i=0;i<(strlen(numero)/2)+1;i++)
    
    {
            if (numero[i]!=numero[strlen(numero)-1-i]) 
            {cout << "Não Capicua";break;}
    } 
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ups, nem me lembrei desse caso quando pus aquelas dicas para inverter um número. Devia ter pensado com mais cuidado...

Assim que tiver uns minutitos vou resolver esse exercício, talvez o faço ainda hoje  :)

Eu demorei cerca de 1h30 a resolve-lo, se bem que perdi quase uma hora por causa dum erro estúpido... acho que é melhor pensares no problema com calma, reservando mais do que alguns minutos :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ups, nem me lembrei desse caso quando pus aquelas dicas para inverter um número. Devia ter pensado com mais cuidado...

O método que ele aplicou foi o mesmo que tu aplicaste, as tuas dicas estão correctas, está descansado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora