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?
NOTE: Once the chain starts the terms are allowed to go above one million.
cevap: 837799
c++ kodu:
#include <stdio.h>
#include <stdlib.h>
// sorudaki 1000000 degeri icin init_value degiskeni kullanildi. Baska bir deger icin hesaplama
// yapilacak ise bu degiskenin degeri degistirilebilir.
// project euler sorusu 14
// yasin tasan --> 14 subat 2015
unsigned char even_odd_check(unsigned int value);
unsigned int calculate_chain_length(unsigned int test_value);
#define odd 1
#define even 0
#define init_value 1000000
int main()
{
unsigned int chain_length,i,maximum,array_last_value,test_value;
unsigned int array[init_value];
array_last_value = init_value;
test_value = init_value;
while(test_value>0)
{
chain_length = calculate_chain_length(test_value);
array[test_value-1] = chain_length;
test_value--;
}
maximum = array[0];
for (i = 0; i < array_last_value; i++)
if (array[i] > maximum)
maximum = array[i];
printf("maximum of chain length = %d\n", maximum);
return 0;
}
unsigned char even_odd_check(unsigned int value)
{
unsigned char return_value;
if(value%2 == 1)
{
return_value = odd;
}
if(value%2 == 0)
{
return_value = even;
}
return return_value;
}
unsigned int calculate_chain_length(unsigned int test_value)
{
unsigned int chain_counter = 1;
unsigned char return_value = 0;
while(test_value > 1)
{
return_value = even_odd_check(test_value);
if(return_value == odd)
{
test_value = test_value*3+1;
chain_counter++;
}
return_value = even_odd_check(test_value);
if(return_value == even)
{
test_value /= 2;
chain_counter++;
}
}
return chain_counter;
}
c# kodu:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
// sorudaki 1000000 degeri hesabi icin 999999 degeri kullanildi. bunun kullanildigi
// yerler init_value degiskeninin initial degeri ve array dizisinin uzunlugu.
// istenilen hesaba gore bu 2'si degistirilmeli.
// project euler sorusu 14
// yasin tasan --> 14 subat 2015
namespace ConsoleApplication1
{
class Program
{
public const int even = 0;
public const int odd = 1;
static void Main(string[] args)
{
UInt32 init_value = 999999;
UInt32 chain_length, i, maximum, array_last_value, test_value, location;
UInt32[] array = new UInt32[999999];
array_last_value = init_value;
test_value = init_value;
while(test_value>0)
{
chain_length = calculate_chain_length(test_value);
array[test_value-1] = chain_length;
test_value--;
}
maximum = array[0];
location = 0;
for (i = 0; i < array_last_value; i++)
{
if (array[i] > maximum)
{
maximum = array[i];
location = i + 1;
}
}
Console.WriteLine("maximum of chain length = {0}",maximum);
Console.WriteLine("producer of the max chain length = {0}",location);
Console.ReadKey();
}
static UInt32 calculate_chain_length(UInt32 test_value)
{
UInt32 chain_counter = 1;
byte return_value = 0;
while(test_value > 1)
{
return_value = even_odd_check(test_value);
if(return_value == odd)
{
test_value = test_value*3+1;
chain_counter++;
}
return_value = even_odd_check(test_value);
if(return_value == even)
{
test_value /= 2;
chain_counter++;
}
}
return chain_counter;
}
static byte even_odd_check(UInt32 value)
{
byte return_value = 0;
if(value%2 == 1)
{
return_value = odd;
}
if(value%2 == 0)
{
return_value = even;
}
return return_value;
}
}
}
c# kodunda fonklar static olmak zorunda degildir. Yukarda main fonku static oldugundan digger alt fonklar da static oldu. Main static olmasaydi alt fonklar da static olmayabilirdi.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
// sorudaki 1000000 degeri hesabi icin 999999 degeri kullanildi. bunun kullanildigi
// yerler init_value degiskeninin initial degeri ve array dizisinin uzunlugu.
// istenilen hesaba gore bu 2'si degistirilmeli.
// project euler sorusu 14
// yasin tasan --> 14 subat 2015
namespace ConsoleApplication1
{
class Program
{
public const int even = 0;
public const int odd = 1;
void Main(string[] args)
{
UInt32 init_value = 999999;
UInt32 chain_length, i, maximum, array_last_value, test_value, location;
UInt32[] array = new UInt32[999999];
array_last_value = init_value;
test_value = init_value;
while(test_value>0)
{
chain_length = calculate_chain_length(test_value);
array[test_value-1] = chain_length;
test_value--;
}
maximum = array[0];
location = 0;
for (i = 0; i < array_last_value; i++)
{
if (array[i] > maximum)
{
maximum = array[i];
location = i + 1;
}
}
Console.WriteLine("maximum of chain length = {0}",maximum);
Console.WriteLine("producer of the max chain length = {0}",location);
Console.ReadKey();
}
UInt32 calculate_chain_length(UInt32 test_value)
{
UInt32 chain_counter = 1;
byte return_value = 0;
while(test_value > 1)
{
return_value = even_odd_check(test_value);
if(return_value == odd)
{
test_value = test_value*3+1;
chain_counter++;
}
return_value = even_odd_check(test_value);
if(return_value == even)
{
test_value /= 2;
chain_counter++;
}
}
return chain_counter;
}
byte even_odd_check(UInt32 value)
{
byte return_value = 0;
if(value%2 == 1)
{
return_value = odd;
}
if(value%2 == 0)
{
return_value = even;
}
return return_value;
}
}
}
fakat kodun main fonklari static olsalar daha iyi olur. Main fonkunu static yapmak alt fonklari static yapmamak istersek de alt fonklari class’lar icine atmaliyiz. Bu da asagidaki sekilde:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
// sorudaki 1000000 degeri hesabi icin 999999 degeri kullanildi. bunun kullanildigi
// yerler init_value degiskeninin initial degeri ve array dizisinin uzunlugu.
// istenilen hesaba gore bu 2'si degistirilmeli.
// project euler sorusu 14
// yasin tasan --> 14 subat 2015
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
ABC sample = new ABC();
UInt32 init_value = 999999;
UInt32 chain_length, i, maximum, array_last_value, test_value, location;
UInt32[] array = new UInt32[999999];
array_last_value = init_value;
test_value = init_value;
while (test_value > 0)
{
chain_length = sample.calculate_chain_length(test_value);
array[test_value - 1] = chain_length;
test_value--;
}
maximum = array[0];
location = 0;
for (i = 0; i < array_last_value; i++)
{
if (array[i] > maximum)
{
maximum = array[i];
location = i + 1;
}
}
Console.WriteLine("maximum of chain length = {0}", maximum);
Console.WriteLine("producer of the max chain length = {0}", location);
Console.ReadKey();
}
}
class ABC
{
public const int even = 0;
public const int odd = 1;
public UInt32 calculate_chain_length(UInt32 test_value)
{
UInt32 chain_counter = 1;
byte return_value = 0;
while (test_value > 1)
{
return_value = even_odd_check(test_value);
if (return_value == odd)
{
test_value = test_value * 3 + 1;
chain_counter++;
}
return_value = even_odd_check(test_value);
if (return_value == even)
{
test_value /= 2;
chain_counter++;
}
}
return chain_counter;
}
public byte even_odd_check(UInt32 value)
{
byte return_value = 0;
if (value % 2 == 1)
{
return_value = odd;
}
if (value % 2 == 0)
{
return_value = even;
}
return return_value;
}
}
}