De volta à resolução de problemas

ATENÇÃO: Este conteúdo foi publicado há 12 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.


Resultado do Superprime Rib

Hoje, depois de umas férias de dois meses, resolvi um problema lógico do USACO Training Gateway: o Superprime Rib é um problema bem simples em que precisa-se determinar os primos de N dígitos (com N máximo = 8 ) que, tirando o último dígito, continuam sendo primos. A solução é trivial, uma função recursiva bastante simples que se auto-explica no meu código:

//Superprime Rib - USACO Training Gateway - 2005
 
/*
ID: contato1
PROG: sprime
LANG: C
*/
 
#include <stdio.h>
#define NMAX 9
#define INFINITO 100000
 
int primos[NMAX][INFINITO], cont[NMAX];
 
int eh_primo(long int num) {
	int i;
 
	if (num==1||(!(num%2)&&num!=2)) {
		return 0;
	}
 
	for (i=3; i*i<=num; i+=2) {
		if (!(num%i)) {
			return 0;
		}
	}
 
	return 1;
}
 
void funcao(int n) {
	int i, j, num;
 
	cont[n]=0;
 
	if (n>1) {
		funcao(n-1);
 
		for (i=0; i<cont[n-1]; i++) {
			for (j=1; j<=9; j+=2) {
				num=primos[n-1][i]*10+j;
				if (eh_primo(num)) {
					primos[n][cont[n]++]=num;
				}
			}
		}
	} else {
		primos[1][0]=2;
		primos[1][1]=3;
		primos[1][2]=5;
		primos[1][3]=7;
		cont[1]=4;
	}
}
 
int main() {
	int n, i;
 
	FILE *in=fopen("sprime.in", "r");
	FILE *out=fopen("sprime.out", "w");
	fscanf(in, "%d", &n);
	fclose(in);
 
	funcao(n);
 
	for (i=0; i<cont[n]; i++) {
		fprintf(out, "%d\n", primos[n][i]);
	}
	fclose(out);
 
	return 0;
}

O problema passou de segunda porque na primeira, por falta de hábito, eu tinha colocado scanf e printf ao invés de usar o sistema da USACO onde deve-se usar arquivos de entrada e saída.

Agora para eu ir para a seção 2 do USACO Training Gateway falta só o programa Checker Challenge, que parece ser complicado.

Instalei os pacotes do Slackware 10.2, que saiu essa semana, no laptop. Não tem nenhuma grande mudança, mas é sempre bom estar com os programas atualizados…

O Paulo Matias (Thotypous) me convidou para fazer parte da equipe de desenvolvimento da distro Guaranix, consertando alguns bugs do XDirectFB (que eu citei aqui). Acho que irei pegar um trabalho com a Meetweb também (o Hugo Dias, para quem eu fiz o serviço da Coalizão Antituberculose me convidou) e estou acabando o site do Colégio Salesiano, que é totalmente administrável em PHP e usa um banco de dados MySql. Ele deve sair semana que vem…

Dia 24 é a segunda fase da Olimpíada Regional de Matemática. Essa semana fiz a folhinha de treinamento e dos seis problemas, consegui fazer cinco (na verdade, alguns problemas – ou todos – eram repetidos do ano anterior e por isso fica mais fácil, porque eu já lembrava o caminho).

4 comentários sobre “De volta à resolução de problemas

  1. Hey…

    I used a simple recursive function. The solution, implemented in C, is here: sprime.c

    The logic is the following:
    1. The function receives “n”.
    2. If n is greater than 1, we do function(n-1)
    3. If n=1, we just return the four only primes with one digit: 2, 3, 5 and 7.
    4. We have an array called cont, that keep the value of numbers with each number of digits (its index).
    5. After do function(n-1), when n is greater than 1, I do the following loop:

    for i=0 until cont[n-1]; do
    for j=1 until 9, increasing 2; do
    num=prime[n-1][i]*10+j;
    if (is_prime(num)) {
    prime[n][cont[n]++]=num;
    }
    }
    }

    This function, only make num=prime[n-1][i]*10+j, where prime[n-1][i] is a prime with less one algarism and we do it times 10 because we are on decimal system. We do plus “j” because “j” is a odd value that can be the unit of a prime.

    So, we formed all the primes with each n. :)

    Understood? Sorry my bad english, i’m trying to improve it… lol

    Any problem, answer me!

  2. thanks for your interest.
    sorry i forgot to tell you;
    is it in C++ or in C?
    i’m realy bad in this lesson i canT understand the difference between them.
    i need C programming.
    again thanks for your help.
    (my english is not good too no matter:))

Deixe uma resposta