Jump to content
Sign in to follow this  
aalmeid

Recursividade de decomposição

Recommended Posts

aalmeid

Boas pessoal, tenho um problema em mãos. Basicamente é fazer a decomposição de nºs de forma recursiva

ex:

4 = 2*2

6 = 2*3

12 = 2*2*3

16 = 2*2*2*2

25 = 5 * 5

...

Basicamente fiz o seguinte, e funciona perfeitamente

import static java.lang.System.*;

public class FactorsIterativo
{
   public static void main(String[] args)
   {
   if (args.length == 0)
	   exit (0);
      
      for(int i = 0; i < args.length; i++) {
         out.print(args[i]+" = "+factors(Integer.parseInt(args[i])));

	 int valor = Integer.parseInt(args[i]);
	 int divisor = factors (Integer.parseInt (args[i]));
         int calc = valor / divisor;

	 do{
		if (calc == valor || calc == 1)
			break;
		out.print (" * "+factors(calc));
		divisor = factors(calc);
		calc = calc / divisor;
	}while (true);
	out.println();
  }
   }
   
   public static int factors (int temp) {
   if (temp % 2 == 0) {
	   return 2;
   }
   
   if (temp % 3 == 0) {
	   return 3;
   }
   
   if (temp % 5 == 0) {
	   return 5;
   }
   else
	return temp;
   }
}

Problema é que não é recursivo.

Estive voltas e voltas com isto e não consegui pensar numa forma recursiva para fazer isto.

Basicamente a condição é simples mas não estou mesmo a ver como fazer com que os nºs sejam retornados dentro da função "factors"

Queria que me explicassem como fazer e não o código sff.

cumps

Share this post


Link to post
Share on other sites
HappyHippyHippo
public static void recur(int valor) {
  int temp = 0;

  if ((temp = factors(valor)) == valor) {
    out.print (valor);
  } else {
    recur(valor/temp);  
    out.print (" * "+temp);
  }
}


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
KTachyon

public static int factors (int temp) {
   if (temp % 2 == 0) {
	   return 2;
   }
   
   if (temp % 3 == 0) {
	   return 3;
   }
   
   if (temp % 5 == 0) {
	   return 5;
   }
   else
	return temp;
   }

Tendo em conta este método, presumo que só queiras decompor números inferiores a 49, certo? É que sem testares com outros números primos, não vais muito longe.

Repara que se testares a divisão a partir do valor mais pequeno (2) e fores incrementando, consegues obter sempre a decomposição em números primos. Claro que existem outros métodos mais eficientes, mas isso é uma coisa que podes optimizar depois.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
aalmeid

Tendo em conta este método, presumo que só queiras decompor números inferiores a 49, certo? É que sem testares com outros números primos, não vais muito longe.

Repara que se testares a divisão a partir do valor mais pequeno (2) e fores incrementando, consegues obter sempre a decomposição em números primos. Claro que existem outros métodos mais eficientes, mas isso é uma coisa que podes optimizar depois.

Boas, com este método, consigo decompor nº superiores (e bem superiores) a 49...

Executei o programa com nºs grandes e devolveu:

1500 = 2 * 2 * 3 * 5 * 5 * 5

2495 = 5 * 499

36987 = 3 * 12329

165254 = 2 * 82627

...

Parece estar realmente a funcionar.

Já agora, obrigado HappyHippyHippo vou analizar essa função para poder estudar melhor a recursividade

cumps

Share this post


Link to post
Share on other sites
HappyHippyHippo

Boas, com este método, consigo decompor nº superiores (e bem superiores) a 49...

experimenta 88


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
KTachyon

Tipo... Não consegues decompor o 49... Só por aí já falha.

Queres mais exemplos?

77

91

119

121

143

E garanto-te que podia passar aqui o dia a gerar números...

E, já agora, podes decompor 82627 (em 53 * 1559).


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
aalmeid

Tipo... Não consegues decompor o 49... Só por aí já falha.

Queres mais exemplos?

77

91

119

121

143

E garanto-te que podia passar aqui o dia a gerar números...

E, já agora, podes decompor 82627 (em 53 * 1559).

ah já entendi... já percebi. Obrigado ;)

Share this post


Link to post
Share on other sites
aalmeid

btw alguém sabe/arranja problemas de recursividade? tenho alguns mas já os fiz e andei a pesquisar no google e maior parte é para calcular os nº de fibonacci, nº de Lucas, factorial, ...

Se alguém souber onde posso arranjar mais exercícios, se puder dizer agradecia ;)

cumps

Share this post


Link to post
Share on other sites
HappyHippyHippo

podes alterar 90% das soluções iterativas para recursivas ...

mas tenho um intrinsecamente recursivo : quicksort


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
aalmeid

Uma dúvida que me surgiu agora.

A recursividade começa do fim para o inicio. Por exemplo

3! = 3 * 2!

2! = 2 * 1!

e depois lança o valor de 1! = 1, 2! = 2 * 1; 3 ! = 3 * 2 = 6

Se quisesse imprimir estes passos, ele iria imprimir do fim para o inicio. Ou melhor, iria imprimir o 1, depois o 2 e só depois o 6.

Como faço para alterar essa ordem?

Não queria colocar aqui directamente o código pq o problema não é bem sobre factorial mas sim sobre a listagem de ficheiros, mas no meu caso faz do fim para o início. Existe alguma forma de imprimir "correctamente"?

Share this post


Link to post
Share on other sites
HappyHippyHippo

depende da ordem que chamas as funções:

nao testei mas acho que da diferente

int fact1(int i) {
  int result = 0;
  printf(" %d ", i);
  if (i == 1) {
    return 1;
  } else {
    return i * fact1(i-1);
  }
}

int fact2(int i) {
  int result = 0;
  if (i == 1) {
    printf(" %d ", i);
    return 1;
  } else {
    printf(" %d ", i);
    return i * fact1(i-1);
  }
}


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
aalmeid

Já consegui. Fiz desta forma:

public static void nFiles (File fin) {
	File [] list = null;
	int file = 0;

	if (fin.isDirectory())
		list = fin.listFiles();

	for (int i = 0; i < list.length; i++)
	{
		if (list[i].isFile() || list[i].isDirectory())
			file++;

		if (i == list.length)
			break;
	}
	System.out.println (fin.getPath()+": "+file+" files");

	for (int i = 0; i < list.length; i++)
		if (list[i].isDirectory())
			nFiles(list[i]);
}

Share this post


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
Sign in to follow this  

×
×
  • 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.