Escrever código porco ajuda a ganhar este prêmio

The International Obfuscated C Code Contest é um concurso em que vence aquele que escrever o código C mais difícil de se ler e que faça uma coisa útil.

Por incrível que pareça não é uma tarefa tão simples, veja um dos ganhadores da última edição (2006)

#define			      q [v+a]
#define			     c b[1]
#define			    O 1 q
#define			   o 0 q
#define			  r(v,a\
)v<0&&(			 v*=-1,		a*=-1);
#define			p(v,m,	    s,w)*c==*#v?2 q\
<m?(c++		       ,d=1,3	   q=0,5      q=m,main\
(a+3,b)		      ,o=o*s	 q,O=O*		 w q):0:
static		     d,v[99	];main		  (int a,
char**b		    ){d=7;     if(*c?!		  (p(+,3
,4 q+O*		   3,4)p(			   -,(o?3
:(O=1,6		  )),4 q			  -O*3,4)
p(*,4,3		 ,4)p(/				  ,5,4,3)
p((),d,		0+3,0+				 04)*c==
')'?2 q	       <02?(c				++,0):0
:(o=012	      *o+*c-			      '0',c++
,O=1)):	     2 q?3-			   2:printf(
"%d/%d"	    "\n",o		       ,O))return
1;d=a,r    (o,d)r		     (O,d)3 q
=o<O?(4	  q=o,O)		   :(4 q=O,
	 o);r(d,		 o)a+=3;O?
				 1:(O=1,2
				q=1);while
				(2 q=o%1 q)a++;v[d]/=O;d[
				v+1]/=O;return main(d,b);}

Acho que pode ser divertido …

Números primos e algoritmos – Parte I

Um dos fundamentos da criptografia e dos sistemas de assinatura digital são os números primos. O princípio que rege a criptografia assimétrica (RSA) é o fato de ser rápido descobrir se um número é primo e é lento fatorar um número.

O RSA fica para outro post, agora queria focar na pergunta: como faz para saber se um número é primo?

int isPrimo (int x) {
   if (x < 4) return 1;
   for (int i=0; i < x; i++) {
      if (x%i == 0) return 0;
   }
   return 1;
}

Obviamente esta função não é a melhor, ela roda em O(n) ou seja o tempo de execução cresce linearmente com o tamanho do número em questão.

Uma otimização que alguns alunos espertos no curso de Computação I fazem é a seguinte:

int isPrimo (int x) {
   if (x < 4) return 1;
   for (int i=0; i =< x/2; i++) {
      if (x%i == 0) return 0;
   }
   return 1;
}

Isto diminui o tempo de execução pela metade mas não muda a complexidade do algoritmo, ela continua sendo O(n). Portanto para números grandes isto não ajuda muito.

Uma coisa que podemos usar para melhorar a complexidade (ainda não ajuda muito, mas hoje paramos por aqui) é o fato de que se um número não tem nenhum divisor menor que a raiz quadrada dele ele não tem nenhum divisor (a prova disto é fácil e fica como exercício para o leitor 🙂 )

int isPrimo (int x) {
   if (x < 4) return 1;
   for (int i=0; i =< sqrt(x); i++) {
      if (x%i == 0) return 0;
   }
   return 1;
}

Neste caso a complexidade que era O(n) passa a ser O(√n)

Melhorou? Sim. Mas ainda não é o suficiente. No próximo capítulo desta série, veremos métodos que dizem se um número é provavelmente primo.

Se você achar algum erro nos códigos acima, comente.

Morreu Dennis Ritchie o criador da linguagem C

Dennis MacAlistair Ritchie (09 de setembro de 1941 – 08 outubro de 2011) foi um cientista da computação americano notável pelo desenvolvimento da linguagem C e por ter influênciado em outras linguagens de programação, assim como em sistemas operacionais como o Multics e Unix. Ele recebeu o Prêmio Turing em 1983 e a Medalha Nacional de Tecnologia de 1998 em 21 de abril de 1999. Ritchie era o chefe do Departamento de Pesquisa em Sistemas de Software da Lucent Technologies quando ele se aposentou em 2007.

 

#include <stdio.h>
 
#define DMR "Dennis MacAlistair Ritchie"
 
/* No C do Dennis Ritchie não precisava ser int */
int main (void) { /* dica do Marcelo Barros
    /* RIP Dennis */
      printf (DMR); /* Consertado typo, tks compiler */
      printf (" morreu aos 70 anos depois de uma longa enfermidade\n");
      return 0; /* No C do Dennis Ritchie não precisava retornar int */
}
Dennis Ritchie

Mercado de Trabalho – A dificuldade de arrumar um bom programador

Na empresa em que trabalho estávamos precisando de alguns bons programadores C/C++ ou no caso dos sonhos Objective-C para tocar alguns projetos que estavam emperrados por falta de gente. Passaram a busca deste programador para mim.

Confesso que fiquei surpreso após meses de busca de não encontrar ninguém disponível, acabamos contratando um programador equatoriano que vive em Quito e está trabalhando via home-office. Mas ainda sigo buscando uma solução local.

Tudo isto fez com que eu refletisse a razão desta dificuldade. Em primeiro lugar o mercado de TI está aquecido e os bons profissionais estão empregados e em geral satisfeitos com seu emprego. Há um fator que não pode ser desprezado que é a falta de pessoal qualificado: muitas faculdades de TI/Ciência da Computação/Informática não tem bons cursos, não vou citar nomes para não constranger ninguém, mas creio que todos sabem o que falo.

No entanto há um terceiro ponto: muita gente que se candidata a uma vaga em TI não é geek. É isso mesmo, para ser um bom programador é preciso ter algo de geek, gostar de tecnologia, gostar de desafios de lógica, estar antenado nas novidades.

Bom se você souber de um bom programador pode mandar o curriculum dele no meu gmail (ppaulojr). Enquanto isto continuo a minha busca por um programador Jedi. Pode até ser o Mel 🙂

Real Programmers