Java Problemi

[SpiderS_DangeR]

Soru şu:

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

2 farklı kod yazdım ilkinde de 113383'e gelince hata falan vermiyo ama kalıyo öyle, ikincisinde yine 113383'e gelince
Exception in thread "main" java.lang.StackOverflowError
at problem14.collatz(problem14.java:18)
at problem14.collatz(problem14.java:18)
at problem14.collatz(problem14.java:18)...... hatası veriyor. Kodlar şu şekilde:

ilk kod

	public class problem14_2 {

	static int counter = 0;

	static int number;

		public static void main(String[] args) {	

			

			for(int i = 1; i<1000000; i++)

			{		

				System.out.println(i);

				int temp = 1;

				int n = i;

				while(n != 1)

				{				

					if(n%2 == 0)				

						n = n/2;								

					else				

						n = 3*n+1;

					temp++;						

				}

				if(temp>counter)

				{

					counter = temp;

					number = i;				

				}					

			}

			System.out.println(counter);

			System.out.println(number);	

		}

	

	}

	

	

2. kod

	public class problem14 {

		static int counter = 0;	

		static int temp = 1;

	        static int number;

	

		public static void collatz(int n)

		{		

			if(n != 1)

			{

				if(n%2 == 0)			

					n = n/2;			

				else			

					n = 3*n+1;				

				temp++;			

				collatz(n);			

			}

			if(temp>counter)		

				counter = temp;			

			temp = 1;		

		}	

		public static void main(String[] args) {		

			

			for(int i = 1; i<1000000; i++)

			{				

				collatz(i);			

			}

			System.out.println();

			System.out.println(counter);		

		}

	}

	

Sorunu bir türlü bulamadım.

[SpiderS_DangeR]

yukarı

[Deacon]

abi ikincide fonksiyonu recursive gibi kendi içinde çağırmışsın. memoryde yer kalmıyor stackoverflow veriyor o yüzden.

[Deacon]

bir de bu soruyu yapmak için BigInteger sınıfını kullanman lazım. Java bilmiorm ama bu soruyu java ile çözen arkadaşlar o sınıfı kullanarak çözdü.

[SpiderS_DangeR]

for döngüsünü BigInteger'la nasıl yaparım ki?

[SpiderS_DangeR]

long yapınca düzeldi teşekkürler

[Gladmir]

Herhangi bir noktada kullanabilirsin BigInteger ı, ha long ha bu aynı şey.

Tabi long primitive, BigInteger ise obje, üzerinde istediğin gibi oynarsın.

[SpiderS_DangeR]

Yav şimdi başka bi problemde takıldım yine integerın limiti yetmediği için. long'da yemedi bu sefer, ama BigInteger'ı for döngüsüne falan uyarlamak çok kasış.
atıyorum
for(int i=0; i<5; i++) diyeceğine

	for(BigInteger i = new BigInteger("0"); i.compareTo(blablabla

	

demek zorunda kalıyorum, ve genellikle de olmuyo veya ben bilmiyorum kullanımını fdsgs

[Mum_Chamber]

recursive cagirdigi icin stackoverflow olmaz, yeni instance yaratmiyor ki kaynak harcasin.

n=3*n + 1 satiri hata veriyor. n 1 milyona yaklasinca 3*n+1 > 2^31 oluyor o yuzden stackoverflow aliyorsun. BigInteger ya da long yapman gereken de i degil, n degiskeni. long yaparsan daha rahat edersin hatta

[SpiderS_DangeR]

Mum_Chamber said:

recursive cagirdigi icin stackoverflow olmaz, yeni instance yaratmiyor ki kaynak harcasin.

n=3*n + 1 satiri hata veriyor. n 1 milyona yaklasinca 3*n+1 > 2^31 oluyor o yuzden stackoverflow aliyorsun. BigInteger ya da long yapman gereken de i degil, n degiskeni. long yaparsan daha rahat edersin hatta

evet aynen n değişkenini long yapınca stackoverflow vermedi hatta çalıştı kod. Ama şu BigInteger olayı çok kafamı karıştırıyo.
Mesela 500den fazla böleni olan en küçük triangle numberı bulmaya çalışıyorum kod şöyle:

	public class problem12 {	

		

		public static long divisor_finder(long n)

		{

			long counter = 0;

			for(long i = 1; i<n+1; i++)

			{

				if(n%i == 0)

				{

					counter++;

				}

			}

			return counter;

		}	

		public static void main(String[] args) {

			

			long divisor_counter = 0;

			long counter = 0;

			long number = 0;

			

			while(true)

			{

				

				number = number + counter;

				counter++;	

				if(divisor_finder(number)>divisor_counter)

					divisor_counter = divisor_finder(number);

				

				//System.out.println(number+" "+divisor_counter);

				

				if(divisor_counter>500)

					break;

			}

			System.out.println(number);

			System.out.println(divisor_counter);

			

				

		}

	

	}

	

ama long yetmediği için bu sefer yine BigInteger yapmam lazım number değişkenini ama beceremedim

[Mum_Chamber]

javada operator overloading vardi galiba tam emin degilim. varsa sadece long number =0 satirini senin bir onceki tanimladigin gibi BigInteger number =new BigInteer("0"); seklinde degistireceksin iste. onun disinda int gibi davranir operatorler overload edildilerse.

yok edilmedilerse cok tatsiz olur =)

[aquila]

yoh

[Mirage]

Evet operator overloading yok.

Mum_Chamber said:

recursive cagirdigi icin stackoverflow olmaz, yeni instance yaratmiyor ki kaynak harcasin.

n=3*n + 1 satiri hata veriyor. n 1 milyona yaklasinca 3*n+1 > 2^31 oluyor o yuzden stackoverflow aliyorsun.

Bu arada yanlış anlaşılmasın Mum'un yazdığı. Stackoverflow bu tür durumlarda rekursiv çağrıların sayısı yüksek rakamlara ulaşınca olabilir. 32 bit sistemlerde her thread için default stack boyutu 256KB.

Çağırdığınız her metod için stack'te bir frame ayrılıyor. Bu frame'lerin belli bir sabit boyutu var, üstüne metod içindeki her local değişken için 4B falan yer ayrıldığını düşünürsek. Değişken sayısına göre 5000 civarı rekursiv çağrıda bile stackoverflow almak mümkün.

Çok rekursiyon kullanılması gereken algoritmalarda 5000-10000 falan çok küçük rakamlar. Bu durumda ya JVM argümanlarıyla stack boyutunu arttırmak gerekiyor ya da rekursiyon yapısını iterasyon ile değiştirmek gerekiyor.

Ama senin durumunda stack'in dolması çok rekursiyon kullanmaktan değil. Mum'un dediği gibi integer sınırını aştığın için sınırsız rekursiyona girmenden kaynaklanmış.

[Mum_Chamber]

ee sey tabi, ben de tam onu seyetmek istedim. evet iste stack thread flow filan iste :P

eki eki =)

[SpiderS_DangeR]

Bu arada bu BigIntegerlarla ilgili operatorlerin kolay kullanımı falan hakkında yapılabilicek hiçbişey yok mu cidden?

[aquila]

sanmam, class methodlarini kullanican.