COMPLEXITY

[kwdikosno8]

exoume auto to problem

http://online-judge.uva.es/p/v1/100.html

mporei kapios na mou pei thn poliplokothta ths lishs pou parathetw katw?

an einai dinaton tha ithela na kserw ta bhmata sthn euresh ths lishs!

euxaristw prokatabolika

 

#include "stdio.h"

void main(){

long n,i,temp,n0,n1,master_number,c=1;

while (scanf("%ld %ld",&n0,&n1)!=EOF)

{

 

printf ("%ld %ld ",n0,n1);

 

master_number=1;

 

if (n0>n1)

{

temp=n0;n0=n1;n1=temp;

}

for (i=n0;i<=n1;i++)

 

{

c=1;n=i;

while(n>1)

{

n=(n%2)?(3*n+1):(n/2);

c++;

}

if (c>master_number)

{

master_number=c;

}

}

printf ("%ld\n",master_number);

}

}

[bilco]

Από τη στιγμή που δεν μπορούμε να αποδείξουμε ότι αυτός ο βρόγχος

while(n>1)

{

n=(n%2)?(3*n+1):(n/2);

c++;

}

τερματίζει για κάθε n, δεν νομίζω να μπορούμε να βρούμε την πολυπλοκότητα.

[kwdikosno8]

nomizw einai O(n log n)

alla d eimai sigouros...

kaneis?

[Lomar]

Ακόμη δεν έχω κάνει στη σχολή μου υπολογισιμότητα, αλγόριθμους και πολυπλοκότητα κτλ, αλλά μια μικρή παρατήρηση: #include "stdio.h", την πρότυπη βιβλιοθήκη γτ την έχεις σε "" κ όχι σε <>;

 

Αφού δεν είναι δημιουργημένη απο κάποιον άσχετο αλλά αντίθετα μέσα στο πρότυπο ANSI C...

[myle]

Τα "" είναι πιο γενικά από τα <>

Μιας και βγήκαμε off topic... στην main πάει καλύτερα να επιστρέφει int.

[eirinikp]

Loipon o while brogxos termatizei otan to n ginei dinami tou 2. Oi epanalipseis e3artwntai apo to poses fores 8a kaneis n = (3*n+1) / 2 (to "/2" paei stin periptwsi pou den brikes dunami tou 2 kai fusika isws na ginei prin kaneis 3*n+1, alla auta einai leptomereies). Prepei na skefteis ti morfi 8a exei o ari8mos pou exei san xeiristi periptwsi to max ari8mo epanalipsewn mexri na pesei se dunami tou 2. Akoma ki an den to breis, grapse tis skepseis sou opws kanw ki egw twra gia na doume an mporesoume na broume mia akribi lusi.

Fusika ton ari8mo pou 8a broume parapanw 8a ton pol/soume me (n1-n0) pou einai o ari8mos epanalipsewn tou for gia na bre8ei i poluplokotita!