Jump to content

Desafio para programador C/C++ ( oferta de emprego)


pedrix21

Recommended Posts

Boas pessoal, esta no netEmprego e encontrei isto :P

Um desafio para o pessoal ;)

#define N    (1 << 25)
#define F(a,b)  { (a) ^= (b); (b) ^= (a); (a) ^= (b); }

uint32_t d[N];

int main(void)
{
   uint64_t h, i, j;

   for (i = 1; i < N; i++)
       d[i] = d[i-1] * 69069 + 1;

   for (i = 0; i < N; i++)
       for (j = 1; j < N; j++)
           if (d[j] < d[j-1])
               F(d[j-1], d[j])

   h = 0;

   for (i = 0; i < N; i++)
       h = h * 13 + d[i];

   h ^= 0x8678ADF24D4F64EFULL;

   printf("Please, mail your CV to %8.8s@grupopie.com\n", &h);

   return 0;
}

Ver Oferta de Emprego: http://www.net-empregos.com/1164427/desafio-para-programador-c/#ixzz1BjGlma3a

www.net-empregos.com - O maior site português de ofertas de emprego

@Pedro Lopes

Link to post
Share on other sites

Então, mais ninguém consegui resolver?

Como já passou algum tempo e me pediram como explicar aqui fica:

SPOILER ALERT (Não ler o resto se querem tentar resolver):

A primeira coisa que devem fazer é compilar o código. Adicionar os devidos includes necessários. Depois reparar que o código implementa um LCG, um algoritmo simples para geração de números pseudo-aleatórios, embora mesmo sem reconhecer o algoritmo desse para resolver.

Depois meti uns prints antes e depois dos loops (podem mudar o valor de N para facilitar este passo). Vão reparar que um loop ali no meio está a ordenar o array da pior maneira possível. Basicamente a macro F é um in-place XOR swap. Substituam por um algoritmo eficiente para ordenação de números como radix sort ou qsort, et voilá.

<3 life

Link to post
Share on other sites
selicerin

Em primeiro lugar peço desculpa por reavivar este tópico, mas nao fazia muito sentido criar um exactamente igual.

Estou a aprender C/C++ e dei com este anuncio por acaso (e uma pesquisa no google direccionou-me para aqui). Fiz o sugerido no post anterior, alterar o algoritmo de ordenação, mas o resultado que obtenho é uns caracteres estranhos (pontos de interrogação com fundo preto e por aí).

Nao estou interessado em responder ao anuncio, é apenas por curiosidade, mas agradecia se alguem me pudesse dar uma ajuda no porque de os prints saírem estranhos

Link to post
Share on other sites

Se bem me lembro é mesmo só fazer o que disse em cima que se chegava à reposta facilmente, mas como já passou tanto tempo já não me lembro de detalhes concretos.

<3 life

Link to post
Share on other sites
soniculture

eu tenho um problema com este código!

Implementei o qsort direitinho mas no printf tenho problemas :cheesygrin:

aqui vai o warning:

warning: format '%8.8s' expects type 'char *', but argument 2 has type 'uint64_t *'

estou a utilizar o xcode!

Obrigado ;)

Link to post
Share on other sites

eu tenho um problema com este código!

Implementei o qsort direitinho mas no printf tenho problemas :cheesygrin:

aqui vai o warning:

warning: format '%8.8s' expects type 'char *', but argument 2 has type 'uint64_t *'

O codigo original tem muitas coisas que podem ser melhoradas. Uma delas e o abuso do tipo "uint64_t" na impressao.

O que se passa e que o valor final da variavel h vai ser qualquer coisa como "0x4142434445464748" que pode ser uma representacao da string "HGFEDCBA" (em formato little-endian).

No codigo original eles passam o endereco desse valor para o printf e tudo funciona como esperado, embora seja errado.

Podes fazer um cast e esperar que continue a funcionar (se funciona sem cast, tambem funciona com cast), mas mesmo com o cast continua a ser errado.

    printf("Please, mail your CV to %8.8s@grupopie.com\n", (char*)&h);

ou isolas cada elemento do valor e imprime-lo isoladamente

    printf("Please, mail your CV to ");
    putchar((h >> 0) & 0xFF);
    putchar((h >> 8) & 0xFF);
    putchar((h >> 16) & 0xFF);
    putchar((h >> 24) & 0xFF);
    putchar((h >> 32) & 0xFF);
    putchar((h >> 40) & 0xFF);
    putchar((h >> 48) & 0xFF);
    putchar((h >> 56) & 0xFF);
    printf("@grupopie.com\n");

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to post
Share on other sites
soniculture

Fiz debug do qsort e ele ordena o array mas como que troca a parte direita com a esquerda!

Por exemplo o d[0] deveria ser o d[50] e vice-versa!

É normal o qsort fazer isto?

Concordo contigo com o abuso do int64_t... nem percebo qual a necessidade!

Deixo-te o meu código:

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

#define N 100

uint32_t d[N];

int sort(const void *x, const void *y)

int main (void) {

uint64_t i,h;
char palavra[64];

d[0]=0;

for (i=1;i<N;i++){
	d[i]=d[i-1]*2+1;
	printf("%u\n",d[i]);
	getchar();
}

qsort(d,N,sizeof(int32_t),sort);

for (i=0;i<N;i++){
	printf("i= %llu, d[i] = %lu\n",i,(long unsigned int)d[i]);

}


h=0;
for (i=0;i<N; i++) {
	h=h*13+d[i];
}

        h ^=0x8678ADF24D4F64EFULL;

printf("%8.8s",(char*)&h);

return 0;
}

int sort(const void *x, const void *y) {
return (*(int32_t*)x - *(int32_t*)y);
}

Link to post
Share on other sites
soniculture

Cheguei a este resultado:

c\216\362\253 \316\334@grupopie.com

é possível?

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

#define N (1<<25)

uint32_t d[N];

int sort(const void *x, const void *y) {
return (*(int32_t*)x - *(int32_t*)y);
}

int main (void) {

uint64_t i,h;
uint32_t temp=0;

d[0]=0;

for (i=1;i<N;i++){
	d[i]=d[i-1]*69069+1;
	//printf("i= %llu, d[i] = %lu\n",i,(long unsigned int)d[i]);
	}

qsort(d,N,sizeof(int32_t),sort);

for (i=0;i<(N/2);i++){
	temp=d[i];
	d[i]=d[i+N/2];
	d[i+N/2]=temp;
}

h=0;
for (i=0;i<N; i++) {
	h=h*13+d[i];
}

h ^=0x8678ADF24D4F64EFULL;

printf("Please, mail your CV to %8.8s@grupopie.com\n", (char*)&h);

return 0;
}

Link to post
Share on other sites

Cheguei a este resultado:

c\216\362\253 \316\334@grupopie.com

é possível?

A tua funcao de comparacao tem 1 bug ...

Estas a converter de "uint32_t" para "int32_t" e a subtrair os valores com sinal.

Na versao original, nao ha conversao.

Por exemplo, se os valores originais fossem "x = 0xFFFFFFFF" e "y = 0x00000001", x e maior que y ... mas depois de convertido para valor com sinal "x = -1" e "y = 1" e x NAO e maior que y.

Alem disso o codigo original assume uma implementacao com valores "little endian". Nao sei como se porta a tua implementacao, mas tem atencao a este ponto!

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to post
Share on other sites

Se so mudaste os casts, continuas a ter problema na funcao de comparacao ...

Supoe que "x" e "y" sao respectivamente 1 e 2. Quando subtrais um do outro (1 - 2) com valores de tipo "uint32_t" ("unsigned") o resultado e 4294967295. Se o "int" no teu computador for de 32 bits (faz "#include <limits.h>" e ve "sizeof (int) * CHAR_BIT") a conversao deste valor para tipo "int" nao e fiavel (mas provavelmente da o resultado esperado -1); se o "int" for de 64 bits, o resultado e um valor positivo ... indicando que 1 e maior que 2!!!!

Alem disso, depois de compores a funcao de comparacao, precisas de remover a parte do codigo que troca as metades do array.

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to post
Share on other sites
soniculture

O código que fiz foi:

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

#define N (1<<25)

uint32_t d[N];

int sort(const void *x, const void *y) {
return (*(uint32_t*)x - *(uint32_t*)y);
}

int main (void) {

uint64_t i,h;
uint32_t temp=0;

d[0]=0;

for (i=1;i<N;i++){
	d[i]=d[i-1]*69069+1;
	}

qsort(d,N,sizeof(uint32_t),sort);

for (i=0;i<(N/2);i++){
	temp=d[i];
	d[i]=d[i+N/2];
	d[i+N/2]=temp;
}


h=0;

for (i=0;i<N; i++) {
	h=h*13+d[i];
}
h ^=0x8678ADF24D4F64EFULL;


printf("Please, mail your CV to %8.8s@grupopie.com\n", (char*)&h);

	getchar();

return 0;
}

Estás a dizer que tenho que mudar o tipo que devolve a função, certo?

Ou seja uint32_t sort(const void *x, const void *y) 

Link to post
Share on other sites

Nao! A funcao tem que ter o prototipo "int foo(const void *, const void *);" senao pode dar faisca com o "qsort".

O que tens a fazer e nao misturar alhos com bugalhos ... OH! ... nao misturar numeros "signed" e "unsigned".

int sort(const void *x, const void *y) {
  const uint32_t *xx = x;
  const uint32_t *yy = y;
  if (*xx < *yy) return -1;
  if (*xx > *yy) return 1;
  return 0;
}

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to post
Share on other sites

Boas

Estava a tentar resolver com base no que foi dito pelo @pmg mas dá-me erro na conversão const void*' to const uint32_t*

O que será?

int sort(const void *x, const void *y) {
  const uint32_t *xx = x;
  const uint32_t *yy = y;
  if (*xx < *yy) return -1;
  if (*xx > *yy) return 1;
  return 0;
}

Agradeço a ajuda!

Link to post
Share on other sites

A linguagem C++ e diferente da linguagem C. O meu codigo foi feito em C, mais propriamente C99.

Para funcionar em C++ precisa de ser convertido ... e eu nao sei C++

Experimenta assim

int sort(const void *x, const void *y) {
  const uint32_t *xx = (const uint32_t *)x;
  const uint32_t *yy = (const uint32_t *)y;
  if (*xx < *yy) return -1;
  if (*xx > *yy) return 1;
  return 0;
}

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to post
Share on other sites

Boas

Obrigado pela ajuda. Eu também apenas sei C e C#, mas gostava de resolver isto em C++ porque estou a tentar batalhar um bocado nesta linguagem. Vou ver se consigo por a funcionar em C++.

Mais uma vez obrigado.

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.