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

gold_dark

Ajuda em algoritmia

26 mensagens neste tópico

amigos eu precisava de exemplos de alguritmia para eu estudar sera que me podem ajudar??  :cheesygrin::P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas!

Exemplos de algoritmia?

Nada melhor que ordenação, pelo menos para começar :cheesygrin: Arranja uma lista de palavras e tentar ordenar as mesmas :P

Se procurares por algoritmos de ordenação, vais encontrar bastantes, vê como funcionam :P Testa-os manualmente.

HecKel

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ou encontrar o maior e mais pequeno elemento de um conjunto de 3 usando somente if's (um problema típico de secundário).

Ou, caso estejas mais avançado, ordenar um vector em espiral (exemplo):

21 22 23 24 25

20  7  8  9  10

19  6  1  2  11

18  5  4  3  12

17 16 15 14 13

Depende do nível em que estás mesmo..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Warrior, tive agora de volta desse do vector com o PHP e tenho esta "solução":

$s = "21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13";

// <passar a "espiral" para um vector>
$linhas = explode("\n", str_replace("  ", " ", $s));
$final = array();

for($i=0;$i<count($linhas);$i++){
$linhas[$i] = explode(" ", $linhas[$i]);
}
// </passar a "espiral" para um vector>

$meioh = ceil((count($linhas)-1)/2);
$meiov = ceil((count($linhas[$meioh])-1)/2);


$pos = array("v" => $meiov, "h" => $meioh);
$min = array("v" => $meiov, "h" => $meioh);
$max = array("v" => $meiov, "h" => $meioh);
$stop = array("min" => array("v" => 0, "h" => 0), "max" => array("v" => count($linhas)-1, "h" => count($linhas[$meiov])-1)); // limites do vector da espiral

$sentido = "r"; // r = right; l = left; u = up; d = down
$final[]=$linhas[$pos["v"]][$pos["h"]];
$max["h"]++;

while($max["h"]-1 != $stop["max"]["h"] || $max["v"]-1 != $stop["max"]["v"] || $min["h"] != $stop["min"]["h"] || $min["v"] != $stop["min"]["v"]){
if($sentido == "r"){
	if($pos["h"]<$max["h"]){ // posição actual ainda não é a máxima
		$pos["h"]++;
	}else{ // não podemos andar mais para a direita por agora
		$sentido = "d";
		$max["v"]++;
	}
}
if($sentido == "d"){
	if($pos["v"]<$max["v"]){
		$pos["v"]++;
	}else{
		$sentido = "l";
		$min["h"]--;
	}
}
if($sentido == "l"){
	if($pos["h"]>$min["h"]){
		$pos["h"]--;
	}else{
		$sentido = "u";
		$min["v"]--;
	}
}
if($sentido == "u"){
	if($pos["v"]>$min["v"]){	
		$pos["v"]--;
	}else{
		$sentido = "r";
		$max["h"]++;
	}
}

$i=$linhas[$pos["v"]][$pos["h"]];
if($i === NULL) break; // já está fora do array já que o $max["h"] é > $stop["max"]["h"]
$final[] = $i;
}

var_dump($final);

O problema é que qd eu estou a ir para cima e quero mudar para a direita (ie. no vértice esquerdo), ele repete-me o elemento e o vector fica assim:

array(27) {

  [0]=>

  string(1) "1"

  [1]=>

  string(1) "2"

  [2]=>

  string(1) "3"

  [3]=>

  string(1) "4"

  [4]=>

  string(1) "5"

  [5]=>

  string(1) "6"

  [6]=>

  string(1) "7"

  [7]=>

  string(1) "7"

  [8]=>

  string(1) "8"

  [9]=>

  string(1) "9"

  [10]=>

  string(2) "10"

  [11]=>

  string(2) "11"

  [12]=>

  string(2) "12"

  [13]=>

  string(2) "13"

  [14]=>

  string(2) "14"

  [15]=>

  string(2) "15"

  [16]=>

  string(2) "16"

  [17]=>

  string(2) "17"

  [18]=>

  string(2) "18"

  [19]=>

  string(2) "19"

  [20]=>

  string(2) "20"

  [21]=>

  string(2) "21"

  [22]=>

  string(2) "21"

  [23]=>

  string(2) "22"

  [24]=>

  string(2) "23"

  [25]=>

  string(2) "24"

  [26]=>

  string(2) "25"

}

Ou seja, o vector tem 2 elementos a mais, o 7 e o 21 que "curiosamente" são os vértices que falei acima.

O que tenho mal no algoritmo?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

w00t, já consegui resolver. o problema é que qd ele devia fazer o 1o "r" qd passava de "u" para "r", eu não tinha o if lá. Aqui está o código final:

<?php

$s = "111 112 113 114 115 116 117 118 119 120 121
110 73 74 75 76 77 78 79 80 81 82
109 72 43 44 45 46 47 48 49 50 83
108 71 42 21 22 23 24 25 26 51 84
107 70 41 20  7  8  9 10 27 52 85
106 69 40 19  6  1  2 11 28 53 86
105 68 39 18  5  4  3 12 29 54 87
104 67 38 17 16 15 14 13 30 55 88
103 66 37 36 35 34 33 32 31 56 89
102 65 64 63 62 61 60 59 58 57 90
101 100 99 98 97 96 95 94 93 92 91";

// <passar a "espiral" para um vector>
$linhas = explode("\n", str_replace("  ", " ", $s));
for($i=0;$i<count($linhas);$i++) $linhas[$i] = explode(" ", $linhas[$i]);
// </passar a "espiral" para um vector>

$final = array(); // vector final

$meioh = floor(count($linhas)/2);
$meiov = floor(count($linhas[$meioh])/2);


$pos = array("v" => $meiov, "h" => $meioh);
$min = array("v" => $meiov, "h" => $meioh);
$max = array("v" => $meiov, "h" => $meioh);
$stop = array("min" => array("v" => 0, "h" => 0), "max" => array("v" => count($linhas)-1, "h" => count($linhas[$meiov])-1)); // limites do vector da espiral

$sentido = "r"; // r = right; l = left; u = up; d = down
$final[]=$linhas[$pos["v"]][$pos["h"]];
$max["h"]++;

while($max["h"]-1 != $stop["max"]["h"] || $max["v"]-1 != $stop["max"]["v"] || $min["h"] != $stop["min"]["h"] || $min["v"] != $stop["min"]["v"]){
if($sentido == "r"){
	if($pos["h"]<$max["h"]){ // posição actual ainda não é a máxima
		$pos["h"]++;
	}else{ // não podemos andar mais para a direita por agora
		$sentido = "d";
		$max["v"]++;
	}
}
if($sentido == "d"){
	if($pos["v"]<$max["v"]){
		$pos["v"]++;
	}else{
		$sentido = "l";
		$min["h"]--;
	}
}
if($sentido == "l"){
	if($pos["h"]>$min["h"]){
		$pos["h"]--;
	}else{
		$sentido = "u";
		$min["v"]--;
	}
}
if($sentido == "u"){
	if($pos["v"]>$min["v"]){	
		$pos["v"]--;
	}else{
		$sentido = "r";
		if($pos["h"]<$max["h"])	$pos["h"]++; // <- era esta a linha que faltava!
		$max["h"]++;
	}
}

$i=$linhas[$pos["v"]][$pos["h"]];
if($i === NULL) break; // já está fora do array já que o $max["h"] é > $stop["max"]["h"]
$final[] = $i;
}

var_dump($final);
?>

[me=djthyrax]wantz zeh cookie!!1one1one!one1one!!1[/me]

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema costuma ser mais ao contrário, dado um vector transformá-lo numa espiral, mas o grau de dificuldade permanece o mesmo, portanto well done.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema costuma ser mais ao contrário, dado um vector transformá-lo numa espiral, mas o grau de dificuldade permanece o mesmo, portanto well done.

Como como? Pegar no vector final ali e pô-lo como no início?
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isto é para o pessoal que diz que que implementar algoritmos em php não é "o mais indicado" ou coisas parecidas. Bem jogado djthyrax  :D , mais uma pagina a ser adicionada ao nosso wiki, vou por na lista.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isto é para o pessoal que diz que que implementar algoritmos em php não é "o mais indicado" ou coisas parecidas. Bem jogado djthyrax  :D , mais uma pagina a ser adicionada ao nosso wiki, vou por na lista.

Eheh, obrigado :P Eu tenho resolvido o Euler sempre com PHP também. :P Se quiseres, também arranjo as soluções para a wiki. :P
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

mmmm... oeuler... não percebi...

claculaste o numero de neper em php?

anyway, o que for afixa aí para o pessoal. Quanto mais exmeplo de códiog melhor.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

mmmm... oeuler... não percebi...

claculaste o numero de neper em php?

anyway, o que for afixa aí para o pessoal. Quanto mais exmeplo de códiog melhor.

http://projecteuler.net

e isto responde à questão inicial, estão aqui muito problemas para serem resolvidos, embora uma grande parte exija sobretudo conhecimentos de Teoria de Números.

PS: devias ter mais atenção aos erros ortográficos :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

anyway, o que for afixa aí para o pessoal. Quanto mais exmeplo de códiog melhor.

<?php
header("Content-Type: text/plain");
function microtime_float(){
   list($usec, $sec) = explode(" ", microtime());
   return ((float)$usec + (float)$sec);
}

$time_start = microtime_float();

/******************************************/
## Problema 1
/*
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.
*/


$fives=array();
$threes=array();
$i=1;
while(1){
$five=5*$i;
if($five>=1000) break;
$fives[]=$five;
$i++;
}

$i=1;
while(1){
$three=3*$i;
if($three>=1000) break;
$threes[]=$three;
$i++;
}

foreach($threes as $value){
if(!in_array($value,$fives)) $fives[]=$value;
}
echo array_sum($fives);


/********************************************/
## Problema  6

/*
The sum of the squares of the first ten natural numbers is,
1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
*/

$i = 1;
$sumofsq=array();
while(1){
if($i>100) break;
$sumofsq[] = pow($i,2);
$i++;
}
$sumofsq = array_sum($sumofsq);

$i = 1;
$sqofsum = 0;
while(1){
if($i>100) break;
$sqofsum = $sqofsum + $i;
$i++;
}
$sqofsum = pow($sqofsum,2);

$diff = $sqofsum - $sumofsq;
echo "sqofsum - sumofsq = $diff";

/********************************************/
## Problema 2

/*
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even terms in the sequence below one million.
*/


$sequence=array(1,2,3,5,8);
while(1){
if($sequence[count($sequence)-1]>1000000){ unset($sequence[count($sequence)-1]); break; }
$sequence[] = $sequence[count($sequence)-1] + $sequence[count($sequence)-2];
}

$newsequence=array();
foreach($sequence as $value){
if($value % 2 == 0) $newsequence[]=$value;
}
echo array_sum($newsequence);

/***********************************************/
## Problema 4

/*
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91*99.

Find the largest palindrome made from the product of two 3-digit numbers.
*/


$arr=array();

for($i=999;$i>99;$i--){
for($ii=999;$ii>99;$ii--){
	$x = $i*$ii;
	$a = array($i, $ii);
	asort($a);
	if($x == strrev($x) && !in_array($x,$arr)) $arr[implode("*", $a)]=$x;
}
}

arsort($arr);

foreach($arr as $x => $y){
echo "$x = $y";
break;
}


/***********************************************/

$time_end = microtime_float();
$time = $time_end - $time_start;

echo "\n\n\n\n$time seconds\n";	

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

mmmm... oeuler... não percebi...

claculaste o numero de neper em php?

anyway, o que for afixa aí para o pessoal. Quanto mais exmeplo de códiog melhor.

http://projecteuler.net

e isto responde à questão inicial, estão aqui muito problemas para serem resolvidos, embora uma grande parte exija sobretudo conhecimentos de Teoria de Números.

PS: devias ter mais atenção aos erros ortográficos :D

Eu não gosto muito deste site porque só tem problemas de teoria dos números. E estes problemas são, na minha opinião, dos menos importantes na programação.

Para mim, em termos de algoritmos, não há melhor do que a USACO. Também tem exercícios sobre teoria dos números e sobre diversas áreas.

Mas para começar na USACO convem já dominar uma linguagem.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Coool! aí está o um grande passatempo! Acho que me vou agarrar a isto, aida estou a pensar e devo usar python ou php.

Quanto a teoria de numero ta-se, até é uma coisa que eu gosto e costumo ler umas coisas sobre isso quando me apetece relaxar :D

Não são bem erros ortograficos, são mais gralhas de dactilografia. Dêm-me um desconto, tenho que alternar entre layouts de teclado: portugues, sueco e ingles. E para complicar ainda mais, nem sempre este coincide com o teclado fisico. Mas vou tentar ter mais cuidado sim.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isto é para o pessoal que diz que que implementar algoritmos em php não é "o mais indicado" ou coisas parecidas. Bem jogado djthyrax  :D , mais uma pagina a ser adicionada ao nosso wiki, vou por na lista.

e agora olha para o código do djthyrax e diz-me se achas que aquilo está bem estruturado? eu pessoalmente não acho. como é habitual em php e noutras linguagens de scripting, as funções são raras e não há qualquer separação entre camada computacional e camada de interface. como os problemas são pequenos, não é crítico, mas mesmo assim dificulta a compreensão do código.


Eu não gosto muito deste site porque só tem problemas de teoria dos números. E estes problemas são, na minha opinião, dos menos importantes na programação.

a questão da importância é relativa, em criptografia, por exemplo, são muito importantes.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

ROTFL, mogers, nesse site tem lá um mp3 do famoso "the knack" do dilbert.

há uma solução, fazer os dois :D

mas para responder a este ultimo tópico.

Eu seria mais poupadinho sim, mas acho que sim, está bem feito.

A separação das camadas computacional e de interface foi respeitada por ele, não sei ao que te estas a referir no código dele, as está bem estruturado nesse aspecto.

Ok, podia ter sido mais poupadinho no código em algumas partes, mas isso depende do dominio tecnico da linguagem. Nao acho que é valido classificar negativamente o código por usar sintaxes mais extensas. Quem é obcecado por isso só devia usar python e nunca scheme por exemplo, ou mesmo C, java, por essa ordem de ideias.

Tambem não concordo com o "pouco uso de funções".

As funções devem ser usadas quando são precisas e/ou facilitam a compreensão do código e não como um must have só porque é bem. Se pensares bem, depois de ler a a presentação do projecto neper, que é bem resumida, facilmente se conclui que não será muito necessario o recurso a funções.

Ja agora aqui fica uma que é pode dar que pensar:

Um professor meu estava sempre a implicar que não usavamos muitas funções e que a função main ( C++ ) tinha muita coisa que nao devia ter. Uma vez, num projecto tivemos esta maravilhosa ideia no meu grupo:

na função main colocar apenas uma chamada para outra função, nada mais. Ele quando viu aquilo fartou-se de elogiar, estava todo contente. Acho que não é preciso explicar.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isto é para o pessoal que diz que que implementar algoritmos em php não é "o mais indicado" ou coisas parecidas. Bem jogado djthyrax  :D , mais uma pagina a ser adicionada ao nosso wiki, vou por na lista.

e agora olha para o código do djthyrax e diz-me se achas que aquilo está bem estruturado? eu pessoalmente não acho. como é habitual em php e noutras linguagens de scripting, as funções são raras e não há qualquer separação entre camada computacional e camada de interface. como os problemas são pequenos, não é crítico, mas mesmo assim dificulta a compreensão do código.

? How's that? Eu só faço output 1 vez por exercício. :P
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

ROTFL, mogers, nesse site tem lá um mp3 do famoso "the knack" do dilbert.

:D:P :P

Ja agora aqui fica uma que é pode dar que pensar:

Um professor meu estava sempre a implicar que não usavamos muitas funções e que a função main ( C++ ) tinha muita coisa que nao devia ter. Uma vez, num projecto tivemos esta maravilhosa ideia no meu grupo:

na função main colocar apenas uma chamada para outra função, nada mais. Ele quando viu aquilo fartou-se de elogiar, estava todo contente. Acho que não é preciso explicar.

Eu assino por baixo. Apesar de nunca ter feito isso  :-[  lol

Os códigos que já vi assim, em que o main() só chama outras funções, são sempre programas muito bem estruturados e onde é fácil encontrar os eventuais erros do programa.

Nunca programo assim, porque normalmente estou a programar em estilo "concurso" onde cada segundo é precioso, e prefere-se fazer tudo no main em vez de estruturar o programa  :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu seria mais poupadinho sim, mas acho que sim, está bem feito.

A separação das camadas computacional e de interface foi respeitada por ele, não sei ao que te estas a referir no código dele, as está bem estruturado nesse aspecto.

Ok, podia ter sido mais poupadinho no código em algumas partes, mas isso depende do dominio tecnico da linguagem. Nao acho que é valido classificar negativamente o código por usar sintaxes mais extensas. Quem é obcecado por isso só devia usar python e nunca scheme por exemplo, ou mesmo C, java, por essa ordem de ideias.

Tambem não concordo com o "pouco uso de funções".

As funções devem ser usadas quando são precisas e/ou facilitam a compreensão do código e não como um must have só porque é bem. Se pensares bem, depois de ler a a presentação do projecto neper, que é bem resumida, facilmente se conclui que não será muito necessario o recurso a funções.

Ja agora aqui fica uma que é pode dar que pensar:

Um professor meu estava sempre a implicar que não usavamos muitas funções e que a função main ( C++ ) tinha muita coisa que nao devia ter. Uma vez, num projecto tivemos esta maravilhosa ideia no meu grupo:

na função main colocar apenas uma chamada para outra função, nada mais. Ele quando viu aquilo fartou-se de elogiar, estava todo contente. Acho que não é preciso explicar.

não critiquei a extensão da sintaxe!

quanto à separação das camadas, sem funções e/ou utilização de diferente módulos, não me parece que fique bem feita.

agora quanto à utilização de funções, acho isso essencial na estruturação e compreensão do código, e facilita a detecção de erros, a reutilização do código, etc.

e acho que não é preciso explicar por que é que acho que o teu prof não batia bem da cabeça...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

não critiquei a extensão da sintaxe!

quanto à separação das camadas, sem funções e/ou utilização de diferente módulos, não me parece que fique bem feita.

agora quanto à utilização de funções, acho isso essencial na estruturação e compreensão do código, e facilita a detecção de erros, a reutilização do código, etc.

O objectivo não é propriamente ter código pronto a reutilizar mas sim código o mais rápido possível. E aquilo é instantâneo.
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O objectivo não é propriamente ter código pronto a reutilizar mas sim código o mais rápido possível. E aquilo é instantâneo.

mas nesse caso, tens aí uma razão para não usares PHP, o desempenho (é claro que isso para mim não é uma razão válida, pois acho que o objectivo é a complexidade do algoritmo e não o tempo de execução).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O objectivo não é propriamente ter código pronto a reutilizar mas sim código o mais rápido possível. E aquilo é instantâneo.

mas nesse caso, tens aí uma razão para não usares PHP, o desempenho (é claro que isso para mim não é uma razão válida, pois acho que o objectivo é a complexidade do algoritmo e não o tempo de execução).

Oh, mas antes de me aventurar a fazer em C, faço em PHP que para mim é mais simples. :D E, mesmo em php, em 1 segundo percorro a espiral e faço output.
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu acho que te devias aventurar em C, vais ver que passado o choque inicial é um prazer programar este tipo de problemas nessa linguagem.

Quanto à estruturação do código, eu sempre que programo uso um main praticamente identico:

ler();

go();

output();

Por vezes coloco um init(); ou um transform(); se a solução necessitar pre-computação, mas não fujo muito a isto. (Por vezes dou-lhes outros nomes, depende do espírito.)

Uma das coisas que eu faço que irrita mais gente é que as variáveis e as funções ora aparecem em inglês ora em português, é conforme me lembro..


Não gosto muito do euler porque o acho limitado. É engraçado resolver alguns quando se está a começar, mas os problemas rapidamente se transformam em problemas de matemática e não de programação.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

warrior, por isso é que é fixe, eu adoro matemática :D

warrior, se pensares bem, usar essa estrutura só té dá uma dica de quao não-moderno é o C. Digo eu que é uma das linguagens que uso.  O C e afins foram escritos numa altura em que as limitações de um computador não se podiam comparar às de agora.

Não estou a dizer que o C não presta, C/C++ são a linguagem de excelencia para aplicações de grande porte, ou para programar hardware. Quase todos os sistemas operativos são ecritos nestas linguagens, e mesmo quase todas as outras linguagens só podem ser utilizadas em mais altos niveis.

A não ser que ele use computação massiva, que nao é o caso dos problemas do euler, não necessita de uma linguagem com performance de pico.

Como tal deve usar uma coisa simples. Agora que me lembrei acho que vou resolver o euler em matlab :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Agora que me lembrei acho que vou resolver o euler em matlab :(

experimenta antes o pari/gp. ao contrário do MatLab, este foi pensado sobretudo para problemas ligados à teoria de números.

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