Problemi matematikor 3n+1

Ky problem ka te beje me nje algoritem, por ju duhet qe te perdorni kete algoritem qe te zgjidhni te gjithe problemin.

Nese ju jipet ky Algoritem:





1. marrja e [n]
2. printo [n]
3. nese(if) [n] = 1 atehere(then): NDAL
4. nese(if) [n] eshte tek atehere(then): n = 3n+1
5. tjeter(else): n = n/2
6. Shko te (GOTO) [2]

Nese ju jipet hyrja: 22, pra numri 22. Atehere kjo sekuence e numrave duhet te gjenerohet: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Sipas algoritmit me siper shihet se sekuence nderprehet kur numri [n] arrine numrin [1] per cdo numer [n] qe i jipet. Eshte verifikuar se ky algoritem funksionon per keta numra te [n]: 0 < n < 1,000,000.

Nese ju jipet numri [n], eshte e mundshme qe ju mund te llogartini numrin e numrave te krijuar deri tek numri nje. P.Sh ne shembull me larte per numrin 22, ne kemi 16 numra te krijuar. Kjo quhet gjatesia e ciklit.

Per cdo dy numra [ i ] edhe [ j ] ju duhet qe te dini se cili numer ne mes te tyre ka gjatesine e ciklit me te madhin. Pra duhet qe te gjeni maksimumin e cikleve ne mes numrave [ i ] edhe [ j ].

- Hyrja eshte kjo: [hyrja.txt]

Hyrja do te kete nje cifte integjeresh (numra te plote) per cdo rresht. Keta dy numra do te jene ne mes zero [0] edhe nje milion [1,000,000].

Ju duhet qe ti llogartini ciklin maksimal per cdo cifte.

- Dalja duhet te jete keshtu: [dalja.txt]

Per cdo [ i ] edhe [ j ], pra cifte integjeresh, ju duhet qe ne dalje te printoni ciftin edhe pas ciftit numrin maksimal te ciklit per numrat ne mes [ i ] dhe [ j ]. Keto tri numra duhet te jena te ndara me nje haperesire (one space) shkronje. Tri numrat duhet te jene ne nje rreshte. Pra per cdo rreshte hyrje, ju duhet te keni nje rreshte daljeje. Integjeret [ i ] dhe [ j ] duhet te jene te renditura ashtu sikur se kane qene ne hyrje; pas tyre vjen numri maksimal ciklor.

Hyrja.txt [shembull]




1 10
100 200
201 210
900 1000


Dalja.txt [shembull]




1 10 20
100 200 125
201 210 89
900 1000 174




Zgjidhja

Zgjidhja e problemit ne Perl
vepro keshtu ne shell.




$ chmod +x mat.pl
$ ./mat.pl


mat.pl




#!/usr/bin/perl -w

######################################################################
# Problemi i zgjidhur ne Perl
# Skedari: mat.pl
# Autor: Betim Deva
# Data: 22/07/2004
#
# Programi gjen se cili eshte cikli me i gjati i te gjithe numrave ne
# mes te $n1 dhe $n2
######################################################################

#Hyrja
$n1 = $ARGV[0];
$n2 = $ARGV[1];

#Valido hyrjet
die("Error tek hyrja\n") if(!(0 < $n1 && $n1 < 1000000));
die("Error tek hyrja\n") if(!(0 < $n2 && $n2 <1000000> $n2
if($n1 > $n2){
$temp = $n1;
$n1 = $n2;
$n2 = $temp;
}

#Shiqo numrat ne mes te $n1 dhe $n2
$max_cikli=0;
for(my $i=$n1; $i<= $n2; $i++){
$cikli = 1;
&llogarit($i);
$max_cikli = $cikli if($cikli > $max_cikli);

}

#Shtyp rrezultatet
print "$n1 $n2 $max_cikli\n";

#3*n+1 nenrutina e cila llogarit se sa numra jane ne cikel
sub llogarit{
my $n = $_[0];
while($n > 1){
$cikli++;
if ($n%2 == 1){
$n = (3*$n + 1);
}
else{
$n = $n/2;
}
}
}