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

vbmaster

Project Euler Problem17

6 mensagens neste tópico

Boas,

Estava aqui eu a tentar resolver este problema:

http://projecteuler.net/index.php?section=problems&id=17

em c++...

(para quem não consegue aceder o problema é:

If the numbers 1 to 5 are written out in words: one, two, three, four, five; there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters.)

Tendo feito o seguinte código:

#include <iostream>
using namespace std;

int main ()
{
  int dezenas = 0;
  int numbers = 0;
  int sets_of_hundred = 0;
  int sets_of_thousand = 0;
  int result = 0;

  int integer_nums[10] = {0, 3, 3, 5, 4, 4, 3, 5, 5, 4};

  int sets_of_ten[10] = {0, 0, 6, 6, 5, 5, 5, 7, 6, 6};

  int hundred = 7;

  while (sets_of_thousand < 1)
    {
      result += integer_nums[numbers] + sets_of_ten[dezenas] + integer_nums[sets_of_hundred] + ((sets_of_hundred > 0) ? (((dezenas != 0) || (numbers != 0)) ? hundred + 3 : hundred) : 0);

      if ((numbers == 9) && (dezenas == 0))
{
  numbers = 0;
  dezenas = 2;
  result += ((sets_of_hundred == 0) ? 61 : 61 + (3 + integer_nums[sets_of_hundred] + hundred)* 9);
}
      else 
{
  if (numbers == 9)
    {
      if (dezenas == 9)
	{
	  if (sets_of_hundred == 9)
	    {
	      ++sets_of_thousand;
	    }
	  ++sets_of_hundred;
	  dezenas = 0;
	  numbers = 0;
	}
      else
	{
	  ++dezenas;
	}
      numbers = 0;
    }
  else
    {
      ++numbers;
    }
}
}
  cout << result + 11 << endl;
  return 0;
}

Parece-me estar tudo a funcionar bem, no entanto não é dado como a resposta certa... alguém vê o erro?

Basicamente o meu código tem variáveis para a casa das unidades, dezenas, centenas e milhar...

Quando as unidades são iguais a 9 e as dezenas também, há uma adição de valor às centenas e um reset às unidade e às dezenas.

Como a regra foge na numeração inglesa do 10 ao 20 eu salto essa parte e adiciono o valor em letras correspondente....

Alguém vê alguma coisa?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não tenho tempo agora para ler o código, mas estás a tomar em conta o 'and'?

Se quiseres tenho aqui guardada a solução que eu fiz em Python, pode ser que te ajude em alguma coisa, apesar de eu ter usado um método diferente.

Se estiveres interessado, pede por PM. :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Epah, não...

quero ver o que há de errado com o algoritmo que me parece tão certo... :\

E sim, tou a tomar em conta o and sempre que centenas > 0 && (unidade != 0 || dezenas !=0)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Também não olhei com muita profundidade para o código, mas tiveste em atenção o facto de na dezena 1 o 1 (eleven), o 2 (twelve), o 3 (thirteen) e o 5 (fifteen) se escreverem de um modo particular?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tive... é a tal exceptação de que falava que está garantida nesta parte do código:

if ((numbers == 9) && (dezenas == 0))

{

  numbers = 0;

  dezenas = 2;

  result += ((sets_of_hundred == 0) ? 61 : 61 + (3 + integer_nums[sets_of_hundred] + hundred)* 9);

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já corrigi o erro..

estava a somar ali num certo lado 61 em vez de 70 (não me perguntem o que é pois não me apetece explicar o algoritmo), mas o resultado já está certo...

Código:

#include <iostream>
using namespace std;

int main ()
{
  int dezenas = 0;
  int numbers = 0;
  int sets_of_hundred = 0;
  int sets_of_thousand = 0;
  int result = 0;

  int integer_nums[10] = {0, 3, 3, 5, 4, 4, 3, 5, 5, 4};

  int sets_of_ten[10] = {0, 0, 6, 6, 5, 5, 5, 7, 6, 6};

  int hundred = 7;

  while (sets_of_thousand < 1)
    {
      result += integer_nums[numbers] + sets_of_ten[dezenas] + integer_nums[sets_of_hundred] + ((sets_of_hundred > 0) ? (((dezenas != 0) || (numbers != 0)) ? hundred + 3 : hundred) : 0);

      if ((numbers == 9) && (dezenas == 0))
{
  numbers = 0;
  dezenas = 2;
  result += ((sets_of_hundred == 0) ? 70 : 70 + (3 + integer_nums[sets_of_hundred] + hundred)* 10);
}
      else 
{
  if (numbers == 9)
    {
      if (dezenas == 9)
	{
	  if (sets_of_hundred == 9)
	    {
	      ++sets_of_thousand;
	    }
	  ++sets_of_hundred;
	  dezenas = 0;
	  numbers = 0;
	}
      else
	{
	  ++dezenas;
	}
      numbers = 0;
    }
  else
    {
      ++numbers;
    }
}
    }
  cout << result + 11 << endl;
  return 0;
}

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